Codeforces Round #325 will take place on October 12, 2015 at 09:00 UTC for the first and second divisions. Please note that the round will start at unusual time!
The problems of this round are taken from the Regional stage of the All-Russian school team programming olympiad that will be at the same time in Saratov, Russia. Lets wish school teams good luck on competition!
The problemset for school olympiad differs from problems that will be on round. In addition in problemset for school olympiad there will be some problems, which are not included in the round and vice versa. So don't be frightened by the difficulty of problems given for school teams :-)
The process of problems preapring was very interesting: we were reworking problem statements many times, adding tests, changing limits, even managed to change fully prepared problem with another (we had to stop the conveyor already printing problem statements :-)) Let's thank all who were preparing, helping in preparing, reading the problem statements, writing solutions: Adilbek adedalic Dalabaev, Roman Roms Glazov, Vladimir vovuh Petrov, Oleg Oleg_Smirnov Smirnov, Alexey Perforator Ripinen, Maxim Neon Mescheryakov, Ilya IlyaLos Los, Vitaliy gridnevvvit Gridnev, Danil danilka.pro Sagunov, Alexander fcspartakm Frolov, Pavel HolkinPV Kholkin, Igor Igor_Kudryashov Kudryashov, Elena elena Rogacheva, Dmitriy Nerevar Matov, Vitaliy kuviman Kudasov. Chairman of the jury of the Olympiad is Mikhail MikeMirzayanov Mirzayanov (also he is the author of some of tasks). I (Edvard Edvard Davtyan) prepared some tasks and coordinated the work of the authors. So we are a large team of writers (I hope I did not forget anyone)!
Also let's thank Max Akhmedov (Zlobober), The-One-Who-Must-Not-Be-Named (if I am not wrong, he or she is right now solving the round problems) for their help in problems preparing, Maria Belova (Delinur) for translating problems in English and again Mikhail Mirzayanov (MikeMirzayanov) for the Codeforces and Polygon systems.
You will have only two hours to solve six problems. The scoring distribution will be anounced a little before the round. I wish high rating to all participants! Good luck and have fun!
P.S.: Also I want to wish good luck to the participants of the ACM ICPC Southern Subregional Programming Contest that will be held on Wednesday.
UPD Due to technical reasons round is delayed by 10 minutes.
UPD: In problem Subway roller there were tests with trains of length one. At this moment authors are discussing how much it troubled the round results. We are apologize to participants who had problems with that. We will announce our decision about this problem soon.
UPD2: There were trains with length equal to one in tests for problem Subway Roller. Jury decided to accept the first right solution of each user that passed all tests except the wrong, also other submissions were ignored. In addition we accept all successed hacks, although the hack is not correct and the hacked solution passed all other tests. Contest will be rated, but any user who think that this situation is cardinally affected to his/her result can send me in 24 hours a message and jury will discuss the question to make round unrated only for that participant. We are apologize to participants one more time for this situation.
What a large team! Maybe it is the largest team for a contest in CF up to now. Isn't it?
LARGE team = LARGE amount of troubles?
Perhaps they are still busy discussing now? Just wait is OK~
acm/icpc rules or codeforces rules?
Why can't I see this post on my homepage?
Only before the contest 1 hour,we can see it on the homepage.So strange.
Because it's not there :))
We should expect quality problems, since so many people are involved in the preparation.
Score distribution ?
Why delayed again?
where is the scoring distribution ?!
seriously what is the reason behind cf round delays!?
I think it is related to the sudden massive requests. They prepare slave servers based on the number of initial massive requests and they will be ready after the delay.
what is this? 10 mints delay again :v
It wouldn't be a normal codeforces round if there is no delay :)
the contest start at a special time and we have delay 10 min -_-
I'd be 10 mins late if that didn't happen :p
i will be 10 min late because this happened :D
its time to revolution of delays . 2 hours !
Pleople like me.
Hope, that this thing will not be in system tests...
No need to worry. It will because popular hacks are included to systests
so lucky contest for me )) -_- #rank666 #C hacked ...
C kills me today -_- how to solve C?
Just model everything in O(n^2).
I think that this round should be unrated for div 2.
I was trying to specify a valid input in task B: 1
In output specification there was no constraint that the 2 routes must be different (it was mentioned in the task only, but output specification is more important). And I was getting invalid input message.
Well you cannot make the whole contest unrated just because you did not read the problem statement properly. WTH
The output specification will mention what to print, not the whole problem statement.
How can you solve the problem if not by printing what are you supposed to print? I think that the task B should be judged correctly without this information about 2 different routes but there was no explanation during the whole contest. Besides valid hack input was considered invalid.
It was clearly given n>=2.
The Sample Input Tests show you exactly what you need to print.
Sample test(s) input 4 1 2 3 3 2 1 3 2 2 3 output 12
Did you not see this ?
1 1 is not valid.
2 ≤ n ≤ 50
The last sentence of the statement says :
The boy would get bored if he had to walk the same way again, so he wants the way home to be different from the way to the store in at least one crossing.
Read carefully next time, it's your fault.
I have no idea what goes wrong in my code for C. I wrote a checker for it and ran it on large stresstests, but it seems to work... yet, pretest 8.
For the record, it's based on finding a correct pair of final states of both players using something like extended Euclid, then simulating backwards. The only bugs I have in mind are overflows and flipping A/B, but I thought I should've taken care of it.
Could you describe your solution in more details? At first glance, for me it looked like simulating backwards, because I have seen similar problems, but it seemed to me that this is not a good approach here and it turned out that we can simulate it forward by using geometrical approach.
However, whatever the simplest solution is, this problem seemed pretty hard to me, I'm kinda surprised that 92 people have solved it. Maybe I am missing something easy?
You're missing that this is well-known problem. Here
The link is not working
I found it pretty hard, too.
I made a DP for x, y ≤ 100, found all the final pairs from which it's possible to make such (x, y) (of course, coprime, since two independent vectors will never give two collinear vectors) and noticed that there are exactly two such pairs, which give only one possible decomposition (let's call then (a1, b1) and (a2, b2); a1 + a2 = x, b1 + b2 = y).
Then, I used my magical intuition, looked at a screen full of numbers and noticed that aky - bkx = ± 1 (one sign for k = 0, the other for k = 1). ...because.
Then, I noticed that adding one pair (a, b) to another (c, d) keeps the value ad - bc (cross product, basically) invariant: a(b + d) - b(a + c) = ab + ad - ba - bc = ad - bc. But that's not actually necessary (and a known identity for cross products).
If I have this decomposition, reconstructing the game is easy — it's always just subtracting the smaller pair from the larger one and can be sped up with modulos, just like GCD.
There's just one thing to watch out for: we may reconstruct the game in such a way that the final cross product is - 1 — Alice starts with an apple. Which of the letters A,B we write depends on this.
Implementation, implementation, implementation.
You destroyed the contest by swaping C with D...
Div 1 or Div 2 ?
Just missed by few seconds for submitting working exponential solution for prob e.I hope my solution turned out to be WRONG when I will run on all test cases after system testing..otherwise I will regret whole day that I was not able to solve prob
Look like the constraint checker for hacking of Div 1B is wrong. My friend used the test below and had 3 successful hacks:
Although in the statement: "Each train consists of two or more neighbouring cells in some row of the field."
I spent the last ~20 minutes trying to code something that pass this case, and I failed -_- I have to read the statements more :'(
Yes, it also seems pretest 3 had trains of length 1. I couldn't pass it for half the contest..when I couldn't find bug in my solution I tried allowing such trains and it worked.
Sounds like the contest has to be unrated. Apparently, I only passed due to randomly adding a lucky condition.
My solution fails the above test with trains of length 1, but passed all pretests.
Huh, how is it possible to use this condition in any way?
Checking that ith and i+2nd columns are free in given row
So, the conclusion is "checking ith and i+2nd cols are free is OK because this case is invalid" ?
yeah, I use whole rest time to find bug in these problem. I hope it to be unrated.
Answer should be NO for this testcase, right? My solution prints YES, I am failing system test :(.
This test is incorrect.
The test is wrong, it should not be in system test.
And it should not have been allowed in a hack.
What was purpose of prob a and b...to test programming skills or English knowledge :)
Very interesting problems!
Because of onsite competition, you will not be able to view other's submissions and test details for ~1 hour. Sorry for inconvenience.
По причине официальной олимпиады, около часа будут недоступны просмотр решений и тестов. Приносим извинения за неудобства.
What about systests?
Will we be able to submit our solutions and will the scoreboard be updated in the meanwhile?
А системное тестирование сейчас будет?
What time it will start system testing? It passed 1 hour and 2 minute. I'm still waiting.
Rekt by long long again. I'm so dumb ;_;
I feel pretty silly. The constraints for 2D looked so small that I didn't even think about whether a naive recursive solution would time out. Next time, next time...
Pending system testing.............?
still w8ing for system test !!!!
Oh man, I feel so dumb T_T!, I spent a lot of time implementing a DP Overkill solution for div2B, and then I realized it was easier than that :(
= = ..So do I :(
MikeMirzayanov Sir already said the reason for the late System testing. So keep waiting and Be patience
The struggle is real, fellow doge.
I´m so sleeping right now!!! ggg I hate starting in "unusual time"! Hurry up please :)
why does the system test still not get started now? is there any technical reasons?
MikeMirzayanov Sir already said the reason for the late System testing. So keep waiting and Be patience
Because of onsite competition, you will not be able to view other's submissions and test details for ~1 hour. Sorry for inconvenience.
I highly suggest that all English problem statements should be read by someone who didn't know the problem before. That is a very easy way to prevent things like this (which are pretty severe of course):
Btw of course lack of word "equal" is most important thing here, but even I am not able to produce sentence which is that bad as second one.
I understood that the numbers are equal, because in this context if the numbers are even between them it means that the numbers are equal. I think it's proper english.
But 'even' has a very clear mathematical meaning already. If anything, the incorrect interpretation is more valid than the intended interpretation.
Lol, I didn't even notice that possibility. It has some sense, but I assigned that "even" to "even after completing" not to "attitude" xD. I thought that this sentence completely lacks any meaning, even wrong one :P. And yes, what rnsiehemt said is also valid.
Well, I'm a bit sad I only have to read this now. First, I interpreted the 'even' as: "The total attitude for each character is even (i.e. not odd; divisible by 2)." This didn't work with the samples, so I decided it meant: "The attitude of each character is TOWARDS the hero, i.e., positive (or maybe non-negative, wasn't sure of that)."
Most of the time these English errors aren't really a problem, but in this case, there are (at least) two other possible interpretations that make at least some sense. Also, the samples shouldn't be necessary to understand the problem, unless the problem explicitly refers to them.
I had the same interpretation! All attitudes to be positive.
what a wonderful contest,but my rating is still falling...
The-One-Who-Must-Not-Be-Named = Lord Voldemort ??? :O :S
I have been waiting for one hour in nervous. Could systests be quicker?
why still waiting for system test? what is happening?
I spent last 20 minutes of competition looking for one error due to "Wrong answer on pretest 3" ... now I´m guessing "this is the reason"!!!
I really beg that the data about trains of length one could be canceled. After all,the problem says that length>=2.
But some people waste time on this problem.So I hope this contest will be unrated.
No No No DONT DO THAT. Its not fair for everyone else who worked so hard.
I think it's better to be unrated.
Both rated and unrated are OK, I don't like "partly unrated".
Why don't you?
Rated is okay:-),but it's to slow......
It would be overkill to not rate the whole competition because of this issue. Yes, some people may have wasted time which would create some noise in the end results, but I think the signal (from a signal processing perspective) would still be very strong. This would at least apply to Div 2 where this was problem D.
I have spent my whole evening waiting for the system test hungry and nervous :(
If this contest started at 0:30 as usual and get a problem like this...
Oh I can't stand it >.<
Div2F's time limit is so strict :(
Lol.!! Hahaha :D
contest is rated or unrated nothing matter to me . But as some people has issue with some problems its better to arrange a complementary contest very soon :D As its Regional time everywhere , everyone should be happy to participate more contest :)
btw am i the only one who have trouble to understand the problem statement clearly :( . Hope for a better translation next time .
yeah the statements were not clear and u had to read the problem 3 4 times to understand it
Yes, statements were bad today.
Am I the only one who misinterpreted B?
With regards to this statement: "First, the hero moves one cell to the right, then one square up or down, or stays idle."
I interpreted it as: either moving right and down, moving right and up, or staying still. Apparently it passes given pretests but not pretest 4.
That is rough. I had not considered that interpretation, but I can see how you could be misled. For me the use of 'First,' clarified the meaning, because this indicates there are at least two steps to a move, while under your interpretation there is only one step (of two possible). But I commiserate!
To be rated or not to be this is problem !
Does anyone have any predictions for the start of system test?
Consider those people as out of competition who got wrong answer in that problem for train length 1
this idea kinda sucks :)
Agree... what if you solved all the problems except D, or if you have a high rating in the contest even without solving problem D.
I must go to sleep now,but system test doesn't start,so I can't wait for it today.
You might wake up before it starts
Also the explanation of sample test in div2 problem d was wrong initially so i don't think rating this round will be fair for someone who wasted his whole time reading the problem statement again and again.
Also I had pp ABCDE in div.2, but I also want it unrated. Cause if not, there will be a godlike people called yuts will be nearly driving me mad!
This round should be unrated for several reasons:
4th is the best reason.
Sorry for 4.
but glad to know that im not the only one who was troubled by the statements...
Only the forth reason is your thinking I guess. -v-
I think this round should be rated.
All the problems & test for everyone is equal..
If your solution can not deal with the train of size 1, your solution may not good enough~~
This suck ... you simple make your code assuming that trains with size 1 are not in the input.
If solution fails, then you spent a lot of time looking for some mysterious error in your solution before you can imagine that limits are wrong and none one noted it during preparation.
UPD: I thinks that contest should be rated for DIV2 contestants, after removing cases for DIV2-D problem which should not be used originally. I guess that all solutions accepted will remains the same.
" If your solution can not deal with the train of size 1, your solution may not good enough~~ "
Different standpoint between pure ACMer and worked people.
Statement: "Program should read two integers up to 1e9 and print their sum."
Your program: "int a, b; scanf(a, b); printf(a + b);"
Verdict: WA for test "1e500 1e500". Your program was not good enough and doesn't deal with big integers.
"may not" in my statement.
I'm just kidding. Why you are so serious..
So we may not like your sense of humor.
can anyone tell me why a naive memorized recursion solution for Div2 D / Div1 B will TLE?
If you handle all the cases properly it won't get tle.
I have to go to sleep now,and I hope I can see "Finished" tomorrow morning.
Please, rated or not, just run system tests.... this delay kill me....
well well well :D RIP System Test -_-
What is happening? When will the system testing be done?
when will the solutions be judged ?? it's already 3 hrs since the contest has ended...
How to solve Div 1 C?
Dont know if my solution is right, but i ran a brute force for small input and observed a pattern in the output based on which i observed the following
Also, if the gcd of A and B is greater than 1, then its Impossible.
I think rating is not very important.
What is important is to test yourself and compare with others.
After The Second Revolution of Colors and Titles, now we got the First revolution of delay in system test... :)
What happened to tests in Div2 D? They changed the pretests !!!(I had pretests passed before, now wrong answer on pretest 4). I think that this is something unjust because if I had seen the WA4 I might have corrected my solution! I know that with this my program would have failed the system tests (or maybe not because that means changed tests, who knows what it would have been), but still — changing the pretests after the competition ends?
The same here. But I guess it's some mistake. Let's say these added tests are normal tests, not pretests. Then everything is ok, right? So it's only a matter of naming.
I think they are running pretest with train of size 1. This is not fair as it is clearly mentioned in the problem statement that train size can be 2 or more. Either rejudge this problem or cancel it.
Nothing reveals that they are testing size 1...
I am assuming that because my code didn't handle train size 1 case.
They are probably trying to detect how much the messed up pretests affected the whole competition to make a decision. Don't worry about those pretests, just wait for systest.
We updated tests and made pretests to be equal to tests. After it we rejudged all attempts and chosen the first passed pretests (that means system tests because they became equal). This trick helped to accept all submissions which are correct. As a side-effect you can see now "Wrong answer on pretest X" rather than before system tests you saw "Pretests passed". It means that your solution anyway would fail on system tests.
Run for the hills!!!
I got pretests passed during the contest for Div 1 B, but now it says that I failed pretest 8. So did the pretests change or something?
Atlast the systest !!! :|
Is there any change on pretest 8 on problem B div 1?
My code went WA and I think it's little unfair to regrade the pretest after the end of the contest, x(
Why the problem D which I passed the pretest before but I got a "Wrong on pretest 4" in the system test?
Testcases in contest were incorrect, so they were replaced.
so will it be unrated contest?
I hope no
Me too !!
I got a good rank after a long time. Now I'm sure this round will be unrated :P
So good problemset, so sad trouble..
In my opinion, the problems themselves were very good, but some of the statements required more scrutiny.
Also, yay — after two failed GCJs, one failed FBHCup and who-knows-how-many failed CF rounds — I didn't trip on 64-bit integers.
You code in C++. Why then you can't use #define int long long to prevent int overflows?
Because this is (in my opinion) not good style. Also, what if you want to define a potentially very large int vector? (Such that 4x as much would exceed the memory limit)
I had MLE only 2-3 times in total, and none of them was on the contest. They were because of algo, not because of the macro. Also, it's way too easy to get tripped with int overflow.
It's better to improve skill, rather than using hacks to hide your imperfection.
Btw, I can guarantee you that I have used > 1/2 memory limit of problems dozens of time, which would lead to MLE if I use #define int long long
Hacks? Oh, really? Competitive programming is about algorithms, not about paying attention to everything (and this "skill" can't be improved, I suppose).
Of course this skill can be improved. It is just 1 amongst dozens of stupid things that can make you fail stupidly, e.g. wrong array bounds, mixup variable names, forgot to memset... Train yourself to pay more attention will solve everything.
Actually, I avoided int overflow trap two times during last 4 contests, so it could be two another fails instead of wins. It's a large trap comparing with other ones. May be, I'm too old, but my attention is my greatest weakness(and, therefore, implementation, I like math problems) and I did not found it improved last two years.
"Next time be more careful" is worst conclusion ever you can draw from problem failed because of a bug. Better question is "What can I do to prevent this in future, so that I don't have to worry about this anymore?". I have created habits which prevent me from failing a problem for every particular reason you mentioned :).
And btw I am a huge fan of #define int long long and I can confirm that it saved me definitely much more times than it caused any harm.
Agree. So, I am trying to prevent bugs, and the best way is to don't allow the bug appear technically. For example, use long long macro or insert sync with stdio in your code template.
No, it's not as simple as what you put "next time be more careful". I believe in "training yourself in most difficult conditions, so you can become perfect". And IMO making yourself believe that you don't have to worry about basic stuff will just slowly make you lose the level of attention needed.
Of course, my belief is probably biased because I was trained by people who could write hundreds lines of code without any bug thanks to perfect attention & other people who could find bugs with just reading code (i.e. no printing stuff / debugger).
I simply don't believe that it could be trained, at least simply by writing more and more programs. Across 6 years of my experience in CP I managed to make less bugs, but that is because my programming skills improved a lot and I think my attention didn't improve at all.
Yeah, it can't be trained simply by writing more code, so we have tricks & habits for attention too :)
That's the problem. People's attention is limited(especially mine) and majority of people just can't focus on big amount of things. I think, you and your trainers are among the minority. What you advice to do for all other people? Find a mistake and abandon to correct it forever? Such approach never will lead to perfection. I like to feel proud because of fast creative elegant solutions, not because of paying attention to tricky moments. I suppose, the majority of competitive programmers are the same. If you are going to play on attention you can find a lot of another games or sports.
I'm glad that this has sparked a constructive debate on approaches.
Honestly, I wasn't trying to say that all approaches other than mine are "wrong". I just find the presumption that whenever I write "int" I could as well have written "long long" to be wrong — exactly for the reasons I_love_Hoang_Yen given — and that's why I would never write that as part of a fixed template.
I even used to take the "more hacky" approach myself early on. Now I'm less of a competitive programmer, more like a computer scientist who likes to keep his algorithmic skills somewhat polished. :)
Interesting. I think my attention / focus on coding has been improving along competitions. In fact, once I told myself that I'll pay more attention to what I'm writing and not just think that whatever I write is going to pass, because it can lead to a lot of penalty during ACM-style contests, and I think it worked.
I've noticed that I have less trouble competing with a lot of activity around me than before after competing more often in such conditions (also, after generally competing more often). It's really that I pay more attention to what I'm doing and not to what joke someone around me is telling or how my place on the scoreboard could be changing.
I'd say it varies from person to person; some people may have an easier time training meta-thinking than others. And it definitely depends on what one's actually tried.
It's not a hack at all because everyone can use that even in ACM
Because of time and memory.
Long longs are much more fat and much more slow to process.
I have used this macro for a long time with C++. But then I decided to use C# and I wrote special "longificator" that substitutes all ints with longs int C# program. I had not problems with time and memory because of it with C++ and even with C#.
What's wrong with div 2C? Quite a lot of people(including me) got WA on main test 12... :|
I failed on that test because I didn't really remove the patients from the queue, resulting in that v_i decreases faster than it should. I fixed it by checking if the patient has been removed from the queue.
Did you use 64-bit integers (long longs) to store intermediate values?
No :| was that the reason?
Probably — the sum of all loudness levels could exceed the range of 32-bit integers.
That too. But you also did not remove children not from the beginning of the queue.
I have hacked 8 solutions which were not removing kids from the queue but tripped on 32-bit overflow myself :) Arghhh :)
Stupid me: noticed the possible overflow but decided to keep using
longand bound the confidence decrease.
However, I forgot the
You should remove patients from the queue when they cry, because then the crying from the cabinet can affect someone behind him, which was not affected before his removal.
Div1D was a nice problem! Thank you for these interesting problems.
What?? This contest will be rated?? Really?
Wow, the slower goes systesting, the faster goes the rating change!
in div 2 pC it says vi, di, pi (1 ≤ vi, di, pi ≤ 10^6)
whats the problem when i use int to store these numbers?
the problem is when u add 4000 numbers each up to 10^6 which is 4e9
The next time I compete, I'm going to get +4 rating.
The Volatility has reduced a lot. In a way a good thing as well. We wont loose our hard earned rating by a few bad performances.
first two-digit rank for me!
Why are there only 9 people mentioned as writers of this contest and not all 16? :D
It's crazy that I got a 'pretests passed' for Div2D during the contest and now what I see is that WA on pretest 4.
Anyone having the same problem?
MikeMirzayanov explained it.
Div 2. Problems A and D solved using regexes: A — 13557081, D — 13577562 (shorter version 13577591)
any editorial ?
Could someone give me D div 2 test 3 third testcase fully, I just can't understand what's wrong with my code, thanks in advance
Test on 2 3 0 ... s.. ... 3 3 AAA sBB CCC
And fix :3
I am happy to see that my relative movement is succeed in Div2.D .I just make the hero 3 steps/second ,and judge during the move:D
I wonder what the usage about the number of trains. = =
Link for editorial is invalid, it should be http://codeforces.com/blog/entry/20898 rather than http://codeforces.com/blog/entry/blog/entry/20898.
¸NICE ROUND!!!!!!!!!!!!!!! VERY NICE PROBLEMS
I think alongside the contest, there should be another way to judge a person's ability or rating, not by the number the acmer accepted, but the number of hard problems the acmer accepted, or the average difficulties, one friend of mine is the best coder I ever see, he is not a quickhand, but he can always solve the hardest problem of a contest, his id is Los_Angelos_Laycurse ,you can checkout the problems he solved. for example http://codeforces.com/gym/100725/attachments Problem J, and his solve it.13485846
Really nice Div1 E! Haven't solve it during the contest and figure out what's wrong in my solution now. Wait to submit it. Oops, WA on #5. Got it right finally.
Just found I post these at a wrong post, LOL.