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!
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 statement
Sergii sends greetings and strongly recommend to read ALL tasks. :)
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.
+1
I prefer weekend rounds, too. But it is probably due to NEERC this time.
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?
I think this time is chosen by considering most places in the world.
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.
I agree, are there any other suitable time?
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?
Most probably last round before Dhaka site regional ... :)
I really like your contests than others, thanks a lot.
Project presentation tomorrow ... but sereja's rounds have so interesting questions that I can' leave it :)
I have my last presentation for university :3! In 4 hours... Ahh Codeforces habe become a vicious fot me last week xD!
Damn!! Cannot participate cause of overtime at work.. Anyway, all the very best to everyone.
I took an exception to participate :)
Wow! almost 3 people participated per second! (in the last 3 minutes before end of registration)
Hey! Your not using PHP 5.4 as you state in FAQ. Array short syntax [] causes compilation error. Update PHP or your docs.
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.
Whats wrong with my code (5256546) for 367A - Sereja and Algorithm ? I'counting 10e5 steps, but still get time limit exceeded?
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.net/contest/367/submission/5259184
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.
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 ??
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.
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.
The idea is just like that ... Seems you have got the implementation wrong.
Thank you!
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.
What's the proof?
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.
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) ?
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.
Thanks, nice explanation.
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 :(
We had 3 solutions. All of them were wrong :( Sorry for such situation.
Good thing my D TLEs anyway, I guess ;)
Whole time "debugging" your A ???
you submit it after 12 minute :) :)
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.
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!)
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"...
what a good contest! :D really cool, good problems
Wow, the system judged very fast today.
Integer overflow on Problem B again ARGHHHHH
Finally 3000! :)
Congratulations!
Thank you!
IT'S OVER 3000! (refer to my template:
#define OVER9000 1234567890
:D)Yet another CF target is born.
Congratulation for being second CF TARGET !!! :)
What a good problem A! 7 successful hacks!
Very interesting round, waiting for the tutorial..
Happy being blue : ]]
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?
It is not so easy to make such rounds :) But I will try.
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.
Div1-pB is almost as same as IIUPC 2013 pH which occured on contest of UVa Online Judge today!
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
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!
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.
Run this code. May b this might help you. int main() { map<int,int>M; 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; }
This is my submission of Problems B. Div 2
http://codeforces.net/contest/368/submission/5266990
I 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 :)
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 ?
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
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:
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.
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:
which is really hard to find (at least, just by looking at the code).
Hi everybody, sorry to bother, but I don't understand why I get different outputs between the online judge and my computer
http://codeforces.net/contest/368/submission/5275044
That's my solution, and it works fine when I try it... but it doesn't seem to work in the online judge... Any ideas? :(
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?
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 !!
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.
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?
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.
Thanks a lot!