### numbertheorist17's blog

By numbertheorist17, history, 5 years ago, ,

Hello, Codeforces!

I am happy to announce Codeforces Round #331 (Div. 2)! The round will be held on November 15th at 7:35 MSK. Div. 1 users can participate out of contest.

The problem set was prepared by me (Girishvar Venkat) and jaina (Jeffrey Zhang). I sincerely thank GlebsHP (Gleb Evstropov) for helping with the preparations of the contest. I also thank thesilione (Bili Sun) for testing this round.

The hero for this round will be Wilbur the pig, after my good friend wilbs43 (Wilbur Li).

Scoring will be 500-1000-1500-2250-2500.

Hope you enjoy this round and wish you high rating!

UPD: Contest is over. Here is a link to editorial: Editorial.

UPD2: Congratulations to all the winners! Results:

Div. 1:

Div. 2:

Hope you all enjoyed this contest! Thanks for participating!

UPD3: Ratings updated.

• +309

 » 5 years ago, # |   0 Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
 » 5 years ago, # |   +57 It's very rare that scoring distribution isn't "announced later".
•  » » 5 years ago, # ^ |   +2 Don't understand what is the profit of knowing the scroring distribution before contest. Almost all participants solve tasks starting from the most easy (= problem A).
•  » » » 5 years ago, # ^ |   +5 If it is dynamic scoring, solving B or C first may be better.
 » 5 years ago, # |   +14 lots of number theory problems ?!?! :)
•  » » 5 years ago, # ^ |   +11 if there is any number theory problem in this contest, there will be many hacks .....
 » 5 years ago, # |   +15 I wonder why it's 19:35 but not 19:30.
•  » » 5 years ago, # ^ |   +5 I think the 5 minutes difference is just that famous DELAY!!
•  » » » 5 years ago, # ^ |   0 thanks for guess!!!
•  » » 5 years ago, # ^ |   +178 We found that in case of 5-10 minutes delay there are many participants who additionally register. It seems it is some kind of psychology: if you see that round will start on 19:30 (and even if you know about 19:25 as deadline for registration), your brain rounds 19:25 to 19:30 and probably you will be near your computer on 19:30, but not on 19:25.
•  » » » 5 years ago, # ^ |   +144 Now my brain rounds 19:30 to 19:35 :D
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +4 Usually, that is happened with me. I thank to MikeMirzayanov for setting this time. So, I could participate next all contests.
•  » » » » 5 years ago, # ^ |   +1 Or just keep in mind the contest's starting time. I think it's not so difficult (only five minutes earlier) :D
•  » » » 5 years ago, # ^ |   0 Hi can you register me please or delay it 5 more minutes
•  » » » » 5 years ago, # ^ |   +5 and here it's :D first testcase
 » 5 years ago, # |   -32 Is round going to be interesting ? Your color says the contest not going to be interesting. Always people with color like your's make contest hard and uninteresing.
•  » » 5 years ago, # ^ |   +9 PrinceOfPersia is in the same color, you know....
•  » » » 5 years ago, # ^ |   -23 No PrinceOfPersia is near to red
•  » » 5 years ago, # ^ |   +21 And your colour says your comments are trash, then?
 » 5 years ago, # | ← Rev. 2 →   +7 as your username it seems we are going to have number theory problems
 » 5 years ago, # |   +49 I know I'm gonna get many downvotes for this comment, but I really hope that problems would be based more on complex algorithms rather than math.
 » 5 years ago, # |   +2 this contest will be rated! yeeee! ^_^
•  » » 5 years ago, # ^ |   +3 Good luck to everyone
 » 5 years ago, # |   +11 I thought I saw Xellos comment in this thread, but now it's disappear. Is that a bug?
 » 5 years ago, # |   -28 I think its going to be a math contest (The handle of Girishvar Venkat :|) Why not changing the name from CodeForces 2 AlgebraForces??
•  » » 5 years ago, # ^ |   0 Did you create a new account for writing this comment? Why are you so afraid of using your original account if you are really thinking this way?
•  » » » 5 years ago, # ^ |   0 Nope! My last account got ruined by my crazy friends, this is a new one..
 » 5 years ago, # |   +11 Wish I can have a good night and a high rating.
 » 5 years ago, # |   0 Hope for maths!
•  » » 5 years ago, # ^ |   +19 we've had enough math in the last few rounds...
 » 5 years ago, # |   +2 just a usual delay !!!
 » 5 years ago, # |   -7 Mathforces instead of codeforces ...
 » 5 years ago, # |   0 C is the most confusing question ever
 » 5 years ago, # |   +6 Really liked the problems! Haven't had such a nice round for a while
 » 5 years ago, # |   +1 Can anyone explain C?
•  » » 5 years ago, # ^ | ← Rev. 22 →   +46 I've come up with the following idea:As you can see, we can associate a list of vertices with an index of an array (or map, if you will).Step 1: create the vertex queuesVertices on the diagonal (0, 0), (1, 1), (2, 2), (3, 3), (4, 4), ... are all map to 0. That means, we can store these particular vertices under the key 0 in some container. I store them like that: map< vector< pair > > vertex_queues; vertex_queues[0].push_back( make_pair(1, 1) ); vertex_queues[0].push_back( make_pair(3, 3) ); vertex_queues[0].push_back( make_pair(2, 2) ); ... vertex_queues[0] now stores the vertices unordered. So, we need to sort them so that we can use them later.Step 2: construct the answer by taking the vertices from the vertex queues in the right orderThe last step is building the answer. We go through the array w[n] from left to right and take the first element from the vertex queue with the index w[i]. So, the i'th vertex must be the one we've just taken from the queue. One by one, we extract all the vertices from the vertex queues in the order dictated by the array w[n].If there are no elements in the w[i]'th vertex queue, the anser is NO. If, lastly, we look though all the vertices in the array that we've constructed and find that the current vertex is less than the previous one, the answer is also NO.Otherwise, we've build the perfectly valid array of vertices which is the solution to the problem :)14288949 — with map14289137 — with vector
•  » » 5 years ago, # ^ |   +4 First you should sort points by their y-x then for each w[i] from last to first set the point with biggest x and y!now we should check that does this greedy algorithm make a aesthetically pleasant! sort points and then for each (x,y) we calculate the mp[ (x,y) ] the maximum index of every point like x' and y' that 0<=x'<=x and 0<=y'<=y in the answer! and we update it with mp[ (x-1,y) ] and mp[ (x,y-1) ] , if one of them was bigger than index of (x,y) print No!now we know answer for each w[i] and it's aesthetically pleasant!
 » 5 years ago, # |   +3 Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
 » 5 years ago, # |   +5 Editorial before finish time ??
•  » » 5 years ago, # ^ |   +29 I had draft ready. Only posted it after contest finished.
 » 5 years ago, # | ← Rev. 3 →   +2 hacked 5 people in problem B in my first hacking attempt on codeforces thanks to this2-1000000000 1000000000
•  » » 5 years ago, # ^ |   0 I also wanted to have my first hacking attempt with such a silly mistake, that I also had made, but I had not found in time where the hacking button is, what a shame...
•  » » » 5 years ago, # ^ |   0 go to room than double click in any submission and hack it , of course you have to lock your problem .
•  » » » » 5 years ago, # ^ |   0 Thank you, but "I had not found in time" means I had done it after contest ends)
•  » » 5 years ago, # ^ |   +9 Nobody in my room was stupid enough not to use long long.
 » 5 years ago, # |   -7 The character "Wilbur" may just as well have not been in the problem statements. All it did was add clutter.
•  » » 5 years ago, # ^ |   +18 But reading the problem through the clutter is a part of the problem. If you would be said like "given array, find sum of absolute differences between i and i+1 for i from 0 to N-1" then it wouldn't be a contest.
•  » » » 5 years ago, # ^ |   -23 The clutter I'm talking about is the crap about Wilbur, not the actual problem itself. The problem could have been simply:You are given an array a of size n which initially consists of all zeroes. In one step, you may choose any index i and either add or subtract 1 to all elements from ai to an. Your goal is to end up with the given array b.What is the minimum number of steps required to reach your goal?Simple and concise. Add a story behind it if you'd like, but don't do it just for the sake of doing it.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +9 It's a trade-off. The problems on Project Euler don't have stories, but that doesn't make them any more boring for me. Personally I actually prefer that approach, but I'm also fine with some characters and a small story to make the problems more fun.The thing with Codeforces is that the English is very difficult to read and often has typos or grammatical mistakes. And sometimes there's just so much stuff. See this older problem for example, would you enjoy reading that when there's pressure to solve the problem in 2-3 minutes? http://codeforces.com/problemset/problem/48/A
 » 5 years ago, # |   +56 I loved the contest — keep it up! Thanks numbertheorist17 and GlebsHP
 » 5 years ago, # | ← Rev. 2 →   +1 This comment was written before final results. I didn't know that they will be same
 » 5 years ago, # |   0 Problem E was nice but pretty hard to implement in a short time,it would have been better if the input was a tree instead of matrix(because it wouldn't have cycles and make things easier)
 » 5 years ago, # | ← Rev. 2 →   +3 Super fast system testing this time
 » 5 years ago, # | ← Rev. 4 →   +98 > when you hack someone and then fail on your own hack during systestEDIT: The funny thing is, if I hardcode the answer to my hack test, I get AC. Meaning if I didn't hack, maybe I wouldn't have failed systest... worst feeling ever :'(
 » 5 years ago, # |   0 I don't know how to deal with the problem D? Is this a dp problem?
•  » » 5 years ago, # ^ |   0 Seems like it. dp[left/right][start][end] precompute two arrays to determine the first tree that will be available to cut if ith tree is cut and falls on left, and right respectively.
 » 5 years ago, # |   0 Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
 » 5 years ago, # |   +4 What a bad day! I did my computer component principle homework about how cpu work the whole day and didn't finish it. That made me not think strictly in round and get a bad rank. I'm so sad. :(
•  » » 5 years ago, # ^ |   0 This straight line in your curve looks pretty cool though.
•  » » 5 years ago, # ^ |   +4 On the other hand, you got the 228th place, Bredor_228_Jaguar_Turnik is very proud of you!
•  » » 5 years ago, # ^ |   0 The computer component principle is a nightmare!!
 » 5 years ago, # |   0 Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
 » 5 years ago, # |   0 why the main test 18 in problem A gives wrong answer but when i run this program in my ide it give me correct answer 0
•  » » 5 years ago, # ^ |   0 The correct answer for that test is 227504, and yours is 0
•  » » 5 years ago, # ^ |   0 Correct answer isn't 0. Its 227504. I failed at the same due to a stupid mistake. Should have tested more rather then racing against time.
 » 5 years ago, # |   +37 tourist is BACK for a contest! :D
•  » » 5 years ago, # ^ |   -30 Maybe he decided that Div.1 contests are too complicated for him and will participate only in Div.2?
•  » » » 5 years ago, # ^ |   +7 you must be kidding.
•  » » » » 5 years ago, # ^ |   -9 Ofc no. I was just trying to figure out, why hadn't he taken part in theeeeeeese Div.1 contests instead of boasting in front of Div.2 users? The answer was quite evident.
 » 5 years ago, # |   +3 Why this code getting TLE? Its complexity is O(n^2) :( I really don't have any idea why.14287878
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 I think it is because while loop in your find function.
•  » » » 5 years ago, # ^ |   0 Oh, I didn't notice that >< Btw, thanks!
 » 5 years ago, # | ← Rev. 2 →   +12 Weak Test cases in C. 8 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 0 1 2 -1 0 1 -1 -2 Solutions giving YES followed by wrong sequence gets AC. Correct Answer: NO AC Buggy code: 14287550
•  » » 5 years ago, # ^ | ← Rev. 2 →   0
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 My AC algorithm fails it tooUPD: And also the winner's solution
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 Sorry, my mistake, w is negative not x,y
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 My submission is also wrong! :)
•  » » 5 years ago, # ^ |   0 my submission works good even on this test (however I solved the question after contest !!)
•  » » 5 years ago, # ^ |   +14 You just made my day pretty sad T_T
 » 5 years ago, # |   0 We always see in codeforces, the output is judged by special judge. that means if the output is 1 then if you print 1.000 there is no problem. Even sometimes Lower case uppercase does not matter. Today I wrote problem A with double variable got WA. For output printing the problem says, "Print the area of the initial rectangle if it could be uniquely determined by the points remaining. Otherwise, print  - 1." There is no instruction that the output should be integer. But it causes me wrong answer and finally I have a devastating contest. 14274647
•  » » 5 years ago, # ^ |   0 Your answer does not actually specify the last significant digit of the answer
•  » » » 5 years ago, # ^ |   0 Thanks, I get it. It's my fault not to specify the setprecision. Default setprecision causes the error.
 » 5 years ago, # |   +10 Could someone explain me how this solution (http://codeforces.com/contest/596/submission/14278463) passed all tests?!P.S.: during the contest I tried to hack it several times using tests like but without any success :(
•  » » 5 years ago, # ^ |   0 Thats strange. Even the basic test such as "1 1000000000" runs forever on my computer. Are there any kind of optimizations being done in codeforces compiler?
•  » » » 5 years ago, # ^ |   0 I believe so. There has been a blog about this kind of thing before.
•  » » » 5 years ago, # ^ |   0 Codeforces compiles C++ with gcc's -O2 flag, which is really common among a lot of online judges and other competition platforms.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +29 C++ Optimizer. Optimizer is much smarter than that programmer.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +1 Absolutely agree :)So why not to disable C++ compiler optimizations on Codeforces? Because now hacking such cases is just like trying your luck :(
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +7 Because it would be unfair if you keep in mind almost all compilers/interpreters do it (Codeforces supports a lot of languages!).Anyways: gcc's -O2 flag is used almost everywhere in competitive programming, and while optimizations like this one tend to obscure the true meaning of the code, they only happen in specific situations and do more good than harm.
 » 5 years ago, # |   0 Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
 » 5 years ago, # |   0 Very Weak Data Set for problem C ... http://codeforces.com/contest/596/submission/14281582 3 6 3 7 0 6 2 -3 -7 -4 This code cant pass this input, but passed system test.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +4 Your input: 3 6 3 7 0 6 2 -3 -7 -4 is not valid, is it? Take a closer look to the input section of problem C.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 "Also, it is guaranteed that if some point (x, y) is present in the input, then all points (x', y'), such that 0 ≤ x' ≤ x and 0 ≤ y' ≤ y, are also present in the input."
 » 5 years ago, # |   0 Why I got verdict skipped? 14275850, 14282184 and 14273892. This is my first time to solve 3 problems in a contest!
•  » » 5 years ago, # ^ |   +1 I'll take a look.
•  » » » 5 years ago, # ^ |   0 Thanks. :)
•  » » » 5 years ago, # ^ |   0
 » 5 years ago, # | ← Rev. 2 →   +24 tourist was the first to solve each problem , amazing !!
 » 5 years ago, # |   0 I used binary search for problem C and got AC. Here is my solution 14289254. But I don't think thats it is correct. It should give TLE on a certain test case.
 » 5 years ago, # |   0 Not seeing so much memes this time gives me strange feeling
 » 5 years ago, # | ← Rev. 2 →   +14 numbertheorist17Weak Test cases in Question: C. input: 15 0 0 1 1 2 2 0 1 1 2 2 3 0 2 1 3 0 3 0 4 1 0 2 1 2 0 3 1 3 0 0 1 -1 2 0 -2 3 1 -1 -3 2 -2 1 4 0output: should be NO [also verified using [user:tourist] sol'n :p]Two users in top5(div2 rankings) got it accepted...even though their output is wrong.Rank1: Ichiban and Rank5: Rafiki53 :p
•  » » 5 years ago, # ^ |   0 Also my solution verify this :D (I'm 99.00% sure about my solution correctness)
•  » » 5 years ago, # ^ |   0 This is unfortunate. I thought I took care of all the cases, but I guess I didn't. Sorry about that! Next time, I will have to be more careful.
•  » » » 5 years ago, # ^ |   +3 Less than 1% of div2 participants solved D and less than 0.1% solved E.Is this the expected difficulty level to make participating fun for div1 people too? Or maybe it would be more fun for div2 people if they could get more than 3/5 once in a while?
•  » » » » 5 years ago, # ^ |   +5 I think it is just that jaina and I thought the problems are easier than they actually are.
•  » » » » » 5 years ago, # ^ |   0 Fair enough. :)I understand that estimating the difficulty must be very hard.If you'd like to get feedback for future problems from someone who's far from div1 level, I'd like to volunteer. Maybe sometimes it would be possible to add some simple problems and hold a div1 and div2 at the same time, making everybody happy!
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 MikeMirzayanov, GlebsHP take a look please
•  » » » 5 years ago, # ^ |   +3 The testset for this problem turned out to be weak. That happens sometimes, but everyone is free to do challenges and improve it during the contest.
 » 5 years ago, # |   +22
•  » » 5 years ago, # ^ |   +11
 » 5 years ago, # |   0 Who else thinks D was more doable than C?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 During the contest I got intimidated by the number of people who solved D and didn't give it much thought. Later I tried to solve it and found it easier than C either, it's a straight foward DP.Actually I think the hardest task on C was understand the english translation, the problem itself wasn't hard.
 » 5 years ago, # |   0 Can someone explain why I am getting different outputs on codeforces and ideone if I am executing the same code ? codeforces link ideone link
 » 5 years ago, # |   +14 I Love Judge!!!???
 » 5 years ago, # |   -28 My computer Ram died!!!????