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.
Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
It's very rare that scoring distribution isn't "announced later".
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).
If it is dynamic scoring, solving B or C first may be better.
lots of number theory problems ?!?! :)
if there is any number theory problem in this contest, there will be many hacks .....
I wonder why it's 19:35 but not 19:30.
I think the 5 minutes difference is just that famous DELAY!!
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.
Now my brain rounds 19:30 to 19:35 :D
Usually, that is happened with me. I thank to MikeMirzayanov for setting this time. So, I could participate next all contests.
Or just keep in mind the contest's starting time. I think it's not so difficult (only five minutes earlier) :D
Hi can you register me please or delay it 5 more minutes
and here it's :D first testcase
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.
PrinceOfPersia is in the same color, you know....
And your colour says your comments are trash, then?
as your username it seems we are going to have number theory problems
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.
this contest will be rated! yeeee! ^_^
Good luck to everyone
I thought I saw Xellos comment in this thread, but now it's disappear. Is that a bug?
I think its going to be a math contest (The handle of Girishvar Venkat :|) Why not changing the name from CodeForces 2 AlgebraForces??
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?
Wish I can have a good night and a high rating.
Hope for maths!
we've had enough math in the last few rounds...
just a usual delay !!!
Mathforces instead of codeforces ...
Really liked the problems! Haven't had such a nice round for a while
Can anyone explain C?
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 queues
Vertices 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: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 order
The 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 map
14289137 — with vector
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!
Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
Editorial before finish time ??
I had draft ready. Only posted it after contest finished.
hacked 5 people in problem B in my first hacking attempt on codeforces thanks to this
2
-1000000000 1000000000
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...
go to room than double click in any submission and hack it , of course you have to lock your problem .
Thank you, but "I had not found in time" means I had done it after contest ends)
Nobody in my room was stupid enough not to use long long.
The character "Wilbur" may just as well have not been in the problem statements. All it did was add clutter.
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.
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.
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.net/problemset/problem/48/A
I loved the contest — keep it up! Thanks numbertheorist17 and GlebsHP
This comment was written before final results. I didn't know that they will be same
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)
Super fast system testing this time
> when you hack someone and then fail on your own hack during systest
EDIT: 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 :'(
I don't know how to deal with the problem D? Is this a dp problem?
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.
Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
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. :(
This straight line in your curve looks pretty cool though.
On the other hand, you got the 228th place, Bredor is very proud of you!
The computer component principle is a nightmare!!
Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
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
The correct answer for that test is 227504, and yours is 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.
tourist is BACK for a contest! :D
Maybe he decided that Div.1 contests are too complicated for him and will participate only in Div.2?
you must be kidding.
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.
Why this code getting TLE? Its complexity is O(n^2) :( I really don't have any idea why.
14287878
I think it is because while loop in your find function.
Oh, I didn't notice that >< Btw, thanks!
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
numbertheorist17,thesilione
My AC algorithm fails it too
UPD: And also the winner's solution
Sorry, my mistake, w is negative not x,y
My submission is also wrong! :)
my submission works good even on this test (however I solved the question after contest !!)
You just made my day pretty sad T_T
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
Your answer does not actually specify the last significant digit of the answer
Thanks, I get it. It's my fault not to specify the setprecision. Default setprecision causes the error.
Could someone explain me how this solution (http://codeforces.net/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 :(
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?
I believe so. There has been a blog about this kind of thing before.
Codeforces compiles C++ with gcc's -O2 flag, which is really common among a lot of online judges and other competition platforms.
C++ Optimizer. Optimizer is much smarter than that programmer.
Absolutely agree :)
So why not to disable C++ compiler optimizations on Codeforces? Because now hacking such cases is just like trying your luck :(
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.
Auto comment: topic has been updated by numbertheorist17 (previous revision, new revision, compare).
Very Weak Data Set for problem C ... http://codeforces.net/contest/596/submission/14281582 3 6 3 7 0 6 2 -3 -7 -4 This code cant pass this input, but passed system test.
Your input:
is not valid, is it? Take a closer look to the input section of problem C.
"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."
Why I got verdict skipped? 14275850, 14282184 and 14273892. This is my first time to solve 3 problems in a contest!
I'll take a look.
I got verdict skipped too:
http://codeforces.net/contest/596/submission/14275416
http://codeforces.net/contest/596/submission/14278689
http://codeforces.net/contest/596/submission/14286289
tourist was the first to solve each problem , amazing !!
numbertheorist17
Weak 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 0
output: 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
Also my solution verify this :D (I'm 99.00% sure about my solution correctness)
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.
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?
I think it is just that jaina and I thought the problems are easier than they actually are.
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!
MikeMirzayanov, GlebsHP take a look please
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.
Who else thinks D was more doable than C?
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.
I Love Judge!!!???