### Sereja's blog

By Sereja, 7 years ago, translation,

Hello everyone!

Codeforces Round #215 will take place on Tuesday, November 26th at 19:30 MSK. This is my ninth Codeforces round and I hope not the last.

I'd like to thank Gerald, Berezin, Aksenov239, MikeMirzayanov and Cenadar for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Problem point values div1: 500-1000-1500-2000-2000
Problem point values div2: 500-1000-1500-2000-2500

Gl & hf ! :)

Contest is over, thank you for participation. Sorry for mistake in problem A. Hope, that problems were interesting for you, also I hope that bugs didn't spoil your mood.
Have a nice evening! :)

Also I'd like to congratulate rng_58, he have 3010 rating now!

Tutorial.

• +224

 » 7 years ago, # |   0 This Contest and previous one from the same street as Berezin said :) When I read the previous round post I say to myself yea no recommendation for reading all problems But I found this statementSergii sends greetings and strongly recommend to read ALL tasks. :)
 » 7 years ago, # |   +46 Why another round for Div1 takes place at Tuesday? Sadly I'm not able to take part in any round at Tuesday, I prefer Saturdays/Sundays and I think I'm not alone with that opinion.
•  » » 7 years ago, # ^ |   -6 +1
•  » » 7 years ago, # ^ |   +56 I prefer weekend rounds, too. But it is probably due to NEERC this time.
 » 7 years ago, # |   0 Although I hate the time (19:30 MSK, means 23:30 Peking time) because it means I cannot go to bed until nearly 2:30 am, I still like taking part in the contest.... I hope more contest starting earlier...How about at noon in MSK?
•  » » 7 years ago, # ^ | ← Rev. 4 →   +3 I think this time is chosen by considering most places in the world.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +3 But 19:30 MSK is not rational enough, because most coders don't like contests between 00:00 am and 13:00 pm, but not just between 00:00 am and 8:00 am.
•  » » » » 7 years ago, # ^ |   0 I agree, are there any other suitable time?
•  » » » 7 years ago, # ^ |   +3 right. for this is a russian website actually. thought that if the round can start a little earlier, only 30min is ok...perhaps i'm a little selfish.having contest after having supper isn't a nice thing, right?
 » 7 years ago, # | ← Rev. 2 →   +2 Most probably last round before Dhaka site regional ... :)
 » 7 years ago, # |   +18 I really like your contests than others, thanks a lot.
 » 7 years ago, # |   +5 Project presentation tomorrow ... but sereja's rounds have so interesting questions that I can' leave it :)
•  » » 7 years ago, # ^ |   +3 I have my last presentation for university :3! In 4 hours... Ahh Codeforces habe become a vicious fot me last week xD!
 » 7 years ago, # |   0 Damn!! Cannot participate cause of overtime at work.. Anyway, all the very best to everyone.
•  » » 7 years ago, # ^ |   +3 I took an exception to participate :)
 » 7 years ago, # |   +1 Wow! almost 3 people participated per second! (in the last 3 minutes before end of registration)
 » 7 years ago, # |   +1 Hey! Your not using PHP 5.4 as you state in FAQ. Array short syntax [] causes compilation error. Update PHP or your docs.
 » 7 years ago, # |   0 I spent lots of time trying to use method mentioned here to hack submission 5246996, but failed to generate the anti-hash sequence in time.
 » 7 years ago, # |   0 Whats wrong with my code (5256546) for 367A - Sereja and Algorithm ? I'counting 10e5 steps, but still get time limit exceeded?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +2 Maybe it's because you used "cout" and "scanf". I think I have read one time that "cout and cin" and "printf and scanf" can have problems when used together...I tried with only cin and cout, and it is accepted: http://codeforces.com/contest/367/submission/5259184
•  » » 7 years ago, # ^ |   +4 Actually, its because your solution is O(n^2) and not O(n) as it looks. That's because you're calling strlen(s) in the for loop, for each iteration, which is itself O(n). Call strlen once, keep its value in a variable and use it in the for loop.
 » 7 years ago, # | ← Rev. 3 →   +3 I can not even imagine how author come up these ideas for problems? Sereja Can you please give us some idea about how did you think about setting about these problems, so that it might be good for upcoming setters ??
 » 7 years ago, # |   0 It seems that many people got tricked when solving Problem A,Div.2.I got tricked,too.Although I found it in the last few minutes,I still lost a lot of score.I think it's a good lesson for us who want to solve the easy problems as fast as possible.Nice job,Sereja.
 » 7 years ago, # |   0 Can anybody please tell me how he solved problem C div 1? I tried to count what's the minimum required N to use K different values, so I tried to find the maximum K <= M such that the found N is less than or equal to the given N and pick the largest K costs from input, but I couldn't pass pretests.
•  » » 7 years ago, # ^ |   +8 The idea is just like that ... Seems you have got the implementation wrong.
•  » » » 7 years ago, # ^ |   +5 Thank you!
•  » » 7 years ago, # ^ | ← Rev. 2 →   +10 F(K) is the minimum required N to use K different values. If k%2=1 => f[k]=k*(k-1)/2 + 1. If k%2=0 => f[k]=k*(k-1)/2 + k/2.
•  » » » 7 years ago, # ^ |   +6 What's the proof?
•  » » » » 7 years ago, # ^ |   +1 It's about Euler path in Complete Graph. There are K vertices and a edge is a condition, you want to go through all edges. If k%2=1 => k vertices with even degree. If k%2=0 => k vertices with odd degree. You can think about it that way.
•  » » » » » 7 years ago, # ^ |   0 During the contest it looked like a Chinese Postman problem in complete graph to me. In Euler Path edges can't be visited more than once, aren't we allowed to do that here (even in optimal solution) ?
•  » » » » » » 7 years ago, # ^ | ← Rev. 2 →   +6 If k%2=1, all vertices have even degree so we can go through all edges and finish in start vertice. That's why f[k]=number of edge + 1 in this case. If k%2=0, we have k vertices with odd degree, so just add an edge between 2 vertices have odd degree, we add in total k/2 new edges. After that we can go through all edge but not finish in start vertice (be cause the last edge is the added edge and we already go through the original edge).So F[k]=total number of edge (new edges and original edges) for this case.
•  » » » » » » » 7 years ago, # ^ |   0 Thanks, nice explanation.
 » 7 years ago, # |   +12 What's the source of the problem with problem div1-A? How is it even possible to have the judge solution for the first problem in the contest fail pretests? Have you tested the problemset at all?I only saw the announcement around ~30 minutes into the contest (since the popup opens in a random open window of CodeForces, not necessarily the one you're looking at), and spent the whole time "debugging" my A. Then at the end I missed the chance to submit D by seconds :(
•  » » 7 years ago, # ^ |   +32 We had 3 solutions. All of them were wrong :( Sorry for such situation.
•  » » » 7 years ago, # ^ |   +6 Good thing my D TLEs anyway, I guess ;)
•  » » 7 years ago, # ^ |   -15 Whole time "debugging" your A ??? you submit it after 12 minute :) :)
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +2 Yes, and it was correct, but it got WA on pretest 3 then. 3-7 minutes later, the judge solution was corrected, but I only saw the announcement about this (and that my solution now has pretests-passed) 18 minutes later.
 » 7 years ago, # |   +13 why are most of the nowadays contests in Sundays or in Tuesdays? I count and find that there are about five contests in this month that they were in Sunday or Tuesday. Unfortunately I have a class these days and I lost these contests. Is it fair? I wish next contest will not be in Sunday or in Tuesday. I wish ...:) (I want to write this comment before the contest but I arrive home now!)
 » 7 years ago, # |   0 Problem B in Div 2: The question defines the sequence as "li, li + 1, ..., ln" but shouldn't this be "li, li + 1, ..., n" according to the second explanation which says "a(li), a(li + 1), ..., an" I got a WA because of this since I assumed it was "li, li+1 , ..., ln"...
 » 7 years ago, # |   0 what a good contest! :D really cool, good problems
 » 7 years ago, # |   +1 Wow, the system judged very fast today.
 » 7 years ago, # |   +5 Integer overflow on Problem B again ARGHHHHH
 » 7 years ago, # |   +271 Finally 3000! :)
•  » » 7 years ago, # ^ |   +7 Congratulations!
•  » » » 7 years ago, # ^ |   +20 Thank you!
•  » » » » 7 years ago, # ^ |   0 IT'S OVER 3000! (refer to my template: #define OVER9000 1234567890 :D)Yet another CF target is born.
•  » » 7 years ago, # ^ |   0 Congratulation for being second CF TARGET !!! :)
 » 7 years ago, # |   +2 What a good problem A! 7 successful hacks!
 » 7 years ago, # | ← Rev. 2 →   0 Very interesting round, waiting for the tutorial..
•  » » 7 years ago, # ^ |   +1 Happy being blue : ]]
 » 7 years ago, # |   +17 Thanks Sereja! It's a nice round: Solutions are short and clear. And the overall difficulty is not too low as I thought (Because it has some tricks in implementation, I failed 2 tasks by it.).Maybe we can have more rounds like this, do you think so?
•  » » 7 years ago, # ^ |   +11 It is not so easy to make such rounds :) But I will try.
 » 7 years ago, # |   -11 In problem Sereja and Algorithm, here the constrain is "string q, which doesn't equal to either string "zyx", "xzy", "yxz". If q doesn't contain any such subsequence, terminate the algorithm, otherwise go to step 2." But when I see the testcase then I'm confused, because answer is "YES" when q contains such substring like "zyx", "xzy", "yxz". Why? My code is AC after the contest because in contest time I was confused.
 » 7 years ago, # |   +1 Div1-pB is almost as same as IIUPC 2013 pH which occured on contest of UVa Online Judge today!
 » 7 years ago, # |   0 I got AC on Sereja ans Anagrams with this code: 5261631. Yet, I am getting WA with this 5261332. This two codes are virtually same except for in one I am using (WA) if ( good == mp.size() ) // Here mp is a map < long long, int > mp (AC) if ( good == dif ) // Here dif = mp.size() right after inserting things in map. The reason I am getting WA is because the size of mp changes at the end of the process. But it shouldn't since I am not inserting anything after the beginning. Can somebody explain this bizarre situation? It would suck if I ever have to face such situation during contest time!
•  » » 7 years ago, # ^ |   +11 When you use map[num], it will add new element in map if num isn't already in it (example). So, if array A has some elements that B dosen't have, size of map will be changed.
•  » » 7 years ago, # ^ |   +1 Run this code. May b this might help you. int main() { mapM; int sz=M.size(); cout << sz << " " << M.size() << endl; if(M[5]==1)cout << "i m not gonna print" << endl; sz=M.size(); cout << sz << " " << M.size() << endl; return 0; }
 » 7 years ago, # |   0 This is my submission of Problems B. Div 2http://codeforces.com/contest/368/submission/5266990I confused why the output of test 2 was different from it was on my computer and Ideone.com. Any body can help me ? Tks for all :)
•  » » 7 years ago, # ^ |   0 I test your code for test 2 it's WA your program give me 3 2 1 also it's basically seem WA can you explain your solution ?
•  » » » 7 years ago, # ^ |   0 For each l[i], I put a[l[i]] into a Set in C++, and the set only holds distinct numbers, so I simply print the size of this set
•  » » » » 7 years ago, # ^ |   0 In your solution you're only counting the number of different integers amongst alm, alm - 1, ..., al1. Instead, the problem asks you to find the number of distinct numbers amongst ali, ali + 1, ..., an, for each of li.On a side note, I would discourage the use of preprocessor directives like these: #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define FRD(i, a, b) for(int i = a; i >= b; --i) Essentially, the main goal for the majority of participants here is to improve their problem solving skills. Even if less typing saves an extra 3 minutes per match for you or me, it is somewhat unlikely to make any difference. Rather than that, it's all about learning to find the solutions for increasingly harder problems in increasingly smaller amount of time. And especially if you're only beginning to practice solving programming contests, writing a clear code (without macros) will only help you to maintain a better clarity of mind. But that's just my own opinion. I realize some people will disagree, and at some skill level this coding "style" may become more useful.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +14 I like these macros and would recommend them. I think the code is much clearer (for the given participant, at least). Also, you'll never make a mistake like: for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++i) { // ... } } which is really hard to find (at least, just by looking at the code).
 » 7 years ago, # |   0 Hi everybody, sorry to bother, but I don't understand why I get different outputs between the online judge and my computerhttp://codeforces.com/contest/368/submission/5275044That's my solution, and it works fine when I try it... but it doesn't seem to work in the online judge... Any ideas? :(
•  » » 7 years ago, # ^ | ← Rev. 2 →   +1 Aren't you going out of bounds with this line, when your loop enters for the 1st time?arri[i] = arri[i + 1] + 1;so arri[i + 1] will have some random value in the memory, since you declared the array localy?
 » 7 years ago, # |   0 I think there is some problem with Problem C in DIV2 to be fixed or the changes which were made during contest are not being reflected in here !!
•  » » 7 years ago, # ^ |   0 Everything is good with the problem. Just be more careful while reading as statement can be a bit difficult to understand at first. Cost me 5 WAs before finally getting it AC. Hats off to Sereja for the problems though.
 » 7 years ago, # | ← Rev. 2 →   -8 I am confused about a testcase given for Div2-C: Sereja and Algorithm.q=zyxxxxxxyyz (input string) s=zyxx (query substring)The explanation for the says — "...you can get string "xzyx" on which the algorithm will terminate" However, the problem states that 'zyx' should not be present in the query string.In fact, the permutation 'zxyx' would be allowed, but not 'xzyx'.Am I missing something?
•  » » 7 years ago, # ^ |   0 Yes, you're making up additional constraints. There is nothing in the problem statement saying that there can't be 'zyx' present in the input string. It only states that 'zyx' won't be rearranged.
•  » » » 7 years ago, # ^ |   0 Thanks a lot!