Eran's blog

By Eran, 6 years ago, translation,

Hi everyone!

Codeforces Round #365 (Div.2) takes place today on 4th of August at 18:05 MSK. As usual Div.1 participants can join out of competition.

I am the author of all the problems, and this is my first round on Codeforces. I advise you to read all the problems, hope you will enjoy them :)

I'd like to thank GlebsHP and danilka.pro for helping me in preparing problems, MikeMirzayanov for the great Codeforces and Polygon platforms and IlyaLos for some useful adviсe.

In this round you will meet Mishka, a little polar bear. She is still young, that's why she may have some problems in finding answers for difficult questions. Will you help her to cope with some of them? :)

UPD. 5 problems, 2 hours to solve them and scoring distribution: 500 — 1000 — 1750 — 2000 — 2250

UPD. We apologize for the inconvenience. All solutions will be judged soon.

UPD. Round is unrated.

UPD. The contest is over. Congratulation to the winners!

Div1: 1. uwi 2. kmjp 3. savinov 4. BigBag 5. KrK

Div2: 1. meteor 2. TmEnd 3. chenjiamin 4. vokeal 5. Denisson

Editorial will be published in the nearest time.

UPD. Editorial

• +242

 » 6 years ago, # |   -210 First Comment!!!
•  » » 6 years ago, # ^ |   +140 this is codeforces not youtube
•  » » » 6 years ago, # ^ |   +18 I wish high rating for everyone!!!
•  » » » » 6 years ago, # ^ |   +8 Really sorry to say but your wish won't be granted until next round. Unrated :(
•  » » » » » 6 years ago, # ^ |   +18 I cursed this round. I am sorry Codeforces.
•  » » » » 6 years ago, # ^ |   0 At least nobody dropped!
•  » » » 6 years ago, # ^ |   -35 Ok, I knows. But codeforces is not always a rigid place.Some fun is ok. All in all, I am stronger than you.
•  » » » 6 years ago, # ^ |   +9 you stole my comment -_-
•  » » » 6 years ago, # ^ |   +3 Why are you being so rule... Don't you know he is human too??
•  » » 6 years ago, # ^ | ← Rev. 2 →   +20 Anyone else having trouble submitting these problems for practice?It still says Pending System Testing for me...Edit: It's open for submitting now.
•  » » » 6 years ago, # ^ |   -6 Looking forward to a story of Limak and Mishka
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Yes, the same problem :(
 » 6 years ago, # |   -68 Let's Help Mishka
•  » » 6 years ago, # ^ |   -18 Let's not decrease Contribution by this kind of comments!
•  » » » 6 years ago, # ^ |   0 Yes.But What gets Downvoted no one knows :v
 » 6 years ago, # |   +47 May be it's 4th August, not 3rd?
•  » » 6 years ago, # ^ |   +6 Fixed
 » 6 years ago, # | ← Rev. 2 →   +9 Is the time correct? Edit: It's fixed now.
•  » » 6 years ago, # ^ |   -15 Yes, it is ;)
 » 6 years ago, # |   -39 Hello i am rommel
•  » » 6 years ago, # ^ |   0 Hi Rommel! Where is Guderian?
 » 6 years ago, # |   -13 Wish all of us can have a good rating after the contest.
 » 6 years ago, # |   +5 Looking forward to a story of Limak and Mishka
 » 6 years ago, # |   -30 I will be back
 » 6 years ago, # |   +5 Can somebody tell me how to hack?
•  » » 6 years ago, # ^ |   +21 First you have to solve a problem. If you solved problem A, lock the problem A(in problem page) and go to 'room', double-click someone's (who solved problem A) source code, and click the "Hack!" button. Sorry for the bad english :(
•  » » 6 years ago, # ^ |   +27 First of all, you need to pass the pretests on the problem you want to hack. When you are done, go to Dashboard and click the padlock which will be on the right of the problem's name. This way you will be able to open every submission for that problem made by someone in your room by going to Room and double-clicking on the cell showing the score and the time of submitting the solution but you won't be able to make further submissions on that problem for the rest of the contest. Also note that you won't be able to use too big test files so in this case you can use a test generator (I think you will see how during the contest), I didn't know that and finished 7th instead of top5 on one of my first contests.
•  » » 6 years ago, # ^ |   -21 you can find it on google
 » 6 years ago, # |   +246 Today's date: 22 / 23 / 24
•  » » 6 years ago, # ^ |   +123 and division 21. The task is to take 20 place:)
•  » » » 6 years ago, # ^ |   +28 And the number of fucks given is 20-1
 » 6 years ago, # |   +24 Nice context time, I can watch TI6 after the context :D
•  » » 6 years ago, # ^ |   +23 I think it's contest, not context :D
•  » » » 6 years ago, # ^ |   +9 my poor English...
•  » » 6 years ago, # ^ |   0 I wish I can go to Seattle next year:D
•  » » 6 years ago, # ^ |   0 Haha I didn't expect anybody on this site of all places to be Dota fans :D
•  » » » 6 years ago, # ^ |   0 Not only div2 participants play dota. For example V--o_o--V is a very good guy with 5k)).
•  » » » » 6 years ago, # ^ |   0 really? dota1 or dota2?
•  » » » » » 6 years ago, # ^ |   0 dota 2. Honestly, I don't know lots of people who play first dota.
•  » » » 6 years ago, # ^ |   0 Lots of my local OI team trainers are LoL players too.
 » 6 years ago, # |   0 Good luck everyone
•  » » 6 years ago, # ^ |   0 high rating
 » 6 years ago, # |   +28 Why you always announce scoring & duration &... just before the contest ?!
 » 6 years ago, # |   -56 jibancanyang的后援会路过，坐看羁绊妹子上紫，后援会成员过来留言呀呀呀(excuse me...don't decrease my contribution.....haipa..
•  » » 6 years ago, # ^ |   0 Pls use English
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Actually, I can't read your comment!
•  » » 6 years ago, # ^ |   -13 啊啊
•  » » » 6 years ago, # ^ |   0 I think I need a translator or something!
•  » » 6 years ago, # ^ |   -13
•  » » 6 years ago, # ^ |   -13 Ok, I am fighting!Go ahed!
•  » » 6 years ago, # ^ |   -11 salayou!
 » 6 years ago, # |   +50 Number of problems, duration and scoring distribution will be announced later. perhaps after contest :D
•  » » 6 years ago, # ^ |   0 Waiting.....
 » 6 years ago, # |   +17 What does 'Later' mean in Russian?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 use google translate :/
•  » » 6 years ago, # ^ |   +53 Maybe, "never" :D
•  » » 6 years ago, # ^ |   +2 It means : Any time except before the contest!
 » 6 years ago, # |   0 Unique Timing...But where's the number distribution? :(
•  » » 6 years ago, # ^ |   0 scoring distribution: 500 — 1000 — 1750 — 2000 — 2500
 » 6 years ago, # |   +31 Delayed! :/
•  » » 6 years ago, # ^ |   0 By 10 min.
 » 6 years ago, # |   -9 I think just now the problem setter has finished his virtual contest of this round !!
 » 6 years ago, # | ← Rev. 2 →   +14 Is this the first contest on CF for which more than 7000 people registered?
•  » » 6 years ago, # ^ |   +2 Good Bye 2015 had > 7000 participants (it's a Div. 1 + Div. 2 competition).
•  » » 6 years ago, # ^ |   +6 Second one after the round that took place right after the color revolution
 » 6 years ago, # |   0 Delay 15 minutes and the number of Contestants reach 7000+.
•  » » 6 years ago, # ^ |   0 Lol
•  » » 6 years ago, # ^ |   0 7000+...is that a record?
»
6 years ago, # |
-36

How does the world look through your eyes?

•  » » 6 years ago, # ^ |   +8 What the fuck is the deal with those inane comments?
 » 6 years ago, # |   +42 Looks like it'll get cancelled or non-rated. I am going to sleep.
•  » » 6 years ago, # ^ |   +26 todays contest should be cancelled!
•  » » » 6 years ago, # ^ |   +16 +1 to non-rating... 40 minutes for a TLE veredict... really annoying...
 » 6 years ago, # | ← Rev. 2 →   +11 It's already 20 minutes while i'm trying to log in...
 » 6 years ago, # |   +6 in queue for more than half hour whats happening
 » 6 years ago, # |   +13 I finished B in 10 minutes and successfully submitted it in 28 minutes...
 » 6 years ago, # |   +7 Took 10 minutes to realize a simple wrong file.
 » 6 years ago, # |   +4 There are more than 4000 submissions queued now :-"
 » 6 years ago, # |   +23 That feeling when the first 90 pages of status are "In queue" ...
 » 6 years ago, # |   +124 Is it rated? :P
•  » » 6 years ago, # ^ |   +42 now that's a good situation to ask such question =)
•  » » 6 years ago, # ^ |   +29 May be the contest will be declared as unrated.
 » 6 years ago, # |   +47 Codeforces became so popular: Codeforces team should think about improving it's server or finding another smart solution :/
 » 6 years ago, # |   +45 So this time it should be unrated right?
 » 6 years ago, # |   +54 Codeforces, please don't turn into Codechef.
•  » » 6 years ago, # ^ |   +1 What does it mean ? Please explain.
•  » » » 6 years ago, # ^ |   +3 You would know its meaning only if you had been active on Codechef contests for some time.
 » 6 years ago, # |   +3 That's not deal, I've submitted 45 mins ago, still can't get the result.., sad about that
 » 6 years ago, # |   0 wow,very fast judging system!
 » 6 years ago, # |   +6 It got passed while I was typing the comment:D
 » 6 years ago, # |   +3 CFOI-_-
•  » » 6 years ago, # ^ |   0 You got me:)
 » 6 years ago, # |   +59 Hmmm...... Huyum_nik?
•  » » 6 years ago, # ^ |   0 I think both it's both servers and him. ;)
 » 6 years ago, # |   0 Me off, cause it will be unrated 90% and cause I got no deal with any bitwise ops(C) (that's my mistake I can't really make myself learn something about bitwise ops..), and got no idea how to solve (D) and (E).
•  » » 6 years ago, # ^ |   0 bitwise(D)*
 » 6 years ago, # |   +65 After 45 minutes, it finally show the result of my B... And the verdict is wrong anwser on pretest 4 :'(
•  » » 6 years ago, # ^ |   +25 I accidentally read your nick name as "I am Wrong". Would have fit to your WA perfectly... No offence :)
•  » » 6 years ago, # ^ |   -43 Maybe, you should have sent a correct solution? There are lines because of such people who send wrong programs.
•  » » » 6 years ago, # ^ |   +52 You are quite interesting...
 » 6 years ago, # |   0 finally , i can see my solutions result. (after 30 min)
 » 6 years ago, # | ← Rev. 4 →   +29 After 45 minutes from submitting B, I find out that it's a WA. :D Got B Pretest Passed 10 minutes ago and still not appearing on standings that I solved it. :D Is it rated? :D UPD1: Oh, my B solution is being rejudged. UPD2: Oh, my B solution has been running on test 1 for over 5 minutes now UPD3: Pretest passed again and still not showing on standings. -_-. What a nice rated round. :D
 » 6 years ago, # |   +61 Can anybody analyze the time complexity of this problem?
 » 6 years ago, # |   +8 Did anyone hack successfully?
•  » » 6 years ago, # ^ |   +13 Submissions sticking on queue for 45 minutes, and you want hacks? :D
•  » » » 6 years ago, # ^ |   +8 just asking :D
 » 6 years ago, # |   +135
 » 6 years ago, # | ← Rev. 2 →   +6 Time limit in D is so bad :( n log n solution with segment tree
•  » » 6 years ago, # ^ |   0 its not , it has a simple N+QlogN solution.
•  » » » 6 years ago, # ^ |   +3 Segment trees. I wish I could code it
•  » » » » 6 years ago, # ^ |   +1 just bit was enough for this problem
•  » » » 6 years ago, # ^ |   +1 Care to explain ??
•  » » » » 6 years ago, # ^ |   +22 xor of all dinstinct elements occuring even number of times is equivalent to xor of all distinct elements xored with xor of all elements occuring odd number of times , xor of distinct elements occuring odd number of times is just xor of the whole subarray , so you need to find xor of all distinct elements of a subarray , this can be done offline in N+QlogN in the same way as finding number of distinct elements of a subarray
•  » » » » » 6 years ago, # ^ |   0 This can be online with segment tree log^2
•  » » » » » » 6 years ago, # ^ |   0 This can also be online with persistent segment tree in per query.
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +6 can you elaborate? the online segtree lg^2 solution
•  » » » » » » » 6 years ago, # ^ |   0 Store all nexts (index). Distinct values [l, r] is number of nexts that next[i] (l <= i <= r) > r. This can be with upper_bound. O(log^2) for each query
•  » » » » » » 6 years ago, # ^ |   0 Are you sure? I thought so too at first, but I found a problem with my idea... You might be thinking something completely different though, which is why I'm curious :DMy flawed solution: Store a set in each node of the segment tree. Add all values on the node's segment to its set. This takes O(n log^2 n) time. And when you make a query, you only need to look at log n sets.The problem with this: Unless I'm missing something, you can't merge those log n sets efficiently, or get the solution for the entire queried segment from their subsolutions in any other way.
•  » » » » » 6 years ago, # ^ |   0 You see the hardest part of this question was to compute the xor of distinct elements. can you elaborate on how you do that offline?
•  » » » » » » 6 years ago, # ^ |   +24 sort queries according to right end point , now go from 1 to N , if arr[i] has occured before , remove arr[i] from last occurance of arr[i] and put arr[i] at i , now for all queries ending at i , xor of distinct elements from l to i is just query(l , i). this can be done easily with a bit
•  » » » » » » » 6 years ago, # ^ |   0 I don't quite understand your explanation. Would you mind giving a code that does this?Why do we have "xor of distinct elements from l to i is just query(l , i)"?
•  » » » » » » » » 6 years ago, # ^ |   0 Refer this with a few changes ! https://github.com/VitSalis/SPOJ/blob/master/DQUERY/dquery.cpp
•  » » » » » » » 6 years ago, # ^ |   0 A great idea!I got it~Thx a lot
•  » » » » » » » 6 years ago, # ^ |   0 Is it similar to Mo's algorithm
•  » » » » » » » » 6 years ago, # ^ |   0 Mo's Algo didn't work for me...TLE
•  » » » » » » » » » 6 years ago, # ^ |   0 Yeah, it got TLE, the best I could reach was prestest 15 after a lot of optimisations. :P
•  » » » 6 years ago, # ^ |   0 Will you please explain?
•  » » » 6 years ago, # ^ |   +8 Explain++
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   0 This problem requires the result of the XOR elements that appear an even number of times in the segment ... we know that the XOR of an even number of the same element is null and of an odd number of the same element is equal to that element. for example : 1010 XOR 1010 = 0 Then 1010 XOR 1010 XOR 1010 = 0 XOR 1010 = 1010 So, in each segment, you must do the XOR of all the elements with XOR distinct elements of this segment ... (because the XOR function works in the opposite way to that of the problem) for example : 3 3 2 The number of separate elements is 2 (3 and 2) Answer: 3 ^ 3 ^ 2 ^ 3 ^ 2 = 3 To find the different elements, you can use MO's algorithm or persist segment tree or sorting segment (or BIT or sqrt sparse decomposition or table)) and use the OFFLINE method (stores the queries you're doing and sorting) you can do dquery od spoj first to get the main idea... Note: MO's algorithm is slow to the constraints of the problem ...
•  » » 6 years ago, # ^ | ← Rev. 2 →   -8 yep, TLE at test number 14 :( I used BIT Q*logN as well and not pass
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 After I solved this problem (here's my code: http://codeforces.com/contest/703/submission/19655570 ), I decided to take a challenge and modify your solution so it will pass :)http://codeforces.com/contest/703/submission/196562841) add cin.tie(0); cout.tie(0); 2) change endl to '\n' and you have AC :) Even the second one on it's own is enough. Now it's your part to find out what does this black magic exactly do :P
•  » » » » 6 years ago, # ^ |   0 Yup, I have tried to resubmit my solution with printf and scanf instead of cin and cout. Finally got AC. Anw, thanks for help :)
 » 6 years ago, # | ← Rev. 2 →   +18 i don't know why i was forcefully logged out. First submission to problem A: 00:03 & passed pretests at 01:06 anyone else was forcefully logged out every now and then?
•  » » 6 years ago, # ^ |   +5 Me Too
•  » » 6 years ago, # ^ |   +5 Yes..During the competition,I can't log in.....T_T
•  » » 6 years ago, # ^ |   0 Yep happened while i was submitting B :| Then after 5 minutes, adding www. worked though
 » 6 years ago, # |   +3 Did anyone manage to get through n * sqrt(n) for problem D? Is it even possible to get through 10 ^ 9 operations like that? Spent whole contest trying, guess it is not possible for me. In c++ ran in 7 seconds locally.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +7 I got tle on test case 15 with Mo algorithm. Then switched to (n + q)logn and it passed for pre tests. Was something like counting distinct number in range but xor of those values.
•  » » » 6 years ago, # ^ |   0 Same for me, couldn't get O(Q sqrt N) to pass
•  » » » 6 years ago, # ^ |   +1 I was thinking of how to find xor of distinct numbers in a range, but failed to. Now I've only solved problem A :(. Mind explaining how you got it?
•  » » » » 6 years ago, # ^ |   +1 It is similar to this: http://www.spoj.com/problems/DQUERY/ Read this: http://codeforces.com/blog/entry/8962 for an offline approach. Here in this problem, just need to use segment tree to update an element at index and calulate xor of a range using segment tree
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +2 Keep a XOR segment tree: when you encounter a value for the first time, on index i, in the segment tree update the position i with that value, and rememember that last[ arr[i] ] = i;And if you've already encountered the value before, also update the position last[ arr[i] ] with the value before updating last[ arr[i] ].After processing each index i, you can answer all queries that have r = i. You will only ask the segment tree for some query(l, i), in other words, your right bound is fixed.Personally I did it with BIT, not a segment tree.
 » 6 years ago, # |   +7 Getting WA after about 45 minutes!! I only took a minute to debug my code ... of course not that long That really kills :v :3
 » 6 years ago, # |   +5 How to solve C? Heck i can't even write a bruteforce solution :\
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I used binary search on time before start walking UPD: As I can see there are some easier solutions than mine. Nevermind)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +11 Try transforming the problem into the new coordinate space (Time, Y). That is, the first coordinate X is time and second coordinate Y denotes the same thing (distance from bottom to top).I will write a more detailed explanation (with a picture) after a few hours (I'm still working =)) if nobody writes satisfactory explanation.PS: no need for binary search.
•  » » 6 years ago, # ^ |   0 Imagine that the x axis represents time. If the pedestrian walks at full speed straight up, he'll move with a slope of u/v. Then, you can easily check if he can walk in front of the bus (this line is to the left of the entire bus) and, if he can't make it in front, how long he has to wait for each vertex of the bus to pass (horizontal distance between the line and vertex).
•  » » 6 years ago, # ^ |   0 Felipe solved it using a well known algorithm named rotating callipers and a sweep line over every x coordinate of the polygon to get the points where the speed changes, finally a simple binary search over those points ;) Good Luck!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 For each vertex, find if it can reach the vertical line before the person can pass the point at which this vertex will intersect with the line. If no/all points satisfy the previous statement, then the person can pass before/after the bus with full speed. Otherwise, you have to go after the bus with different speeds. Start with the lowest (and rightmost in case of a tie) vertex and check the point at which it will meet the vertical line. If you can arrive to this point in a time earlier than the vertex reach time, wait for this vertex to pass the line. If the vertex reached it earlier, then you can move with max speed. Consider vertices in counter-clockwise direction and stop when you pass the highest vertex (at this moment go the remaining distance with full speed).
•  » » 6 years ago, # ^ |   +1 Instead of moving the bus, just consider the guy to be moving. As the bus is convex we can see that it is optimal to be still for a while and then move at maximum speed. Then we only need to see for how long do we need to wait. Again, as the bus is convex, we just need to see the time needed to pass right through each point and store its maximum (for point (X,Y) it will be X/V-Y/U). Thus, if we can't just walk from time 0, (i.e. among the values calculated there is a positive and a negative value) we will need the maximum value calculated plus W/U, else its just W/U. (sorry for possible errors, first time commenting :) )
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Supplement visual guide to the comments above :)Transformation of the pedestrian's path. Strictly vertical path in XY-plane becomes tilted to the right in the TY-plane.Convex bus undergoes absolutely the same transformation, but it doesn't become tilted! After that we should look at the intersections of the transformed figures.Here is neat solution of the guy from MIT : 19629479
•  » » » 6 years ago, # ^ |   0 can u please elaborate?
 » 6 years ago, # |   +12 is it rated?
 » 6 years ago, # |   0 How to solve D??
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 I use a similar offline-algorithm like http://www.spoj.com/problems/DQUERY/ try to calculate the XOR-sum of distinct number in a segment then the ans = the XOR-sum of distinct number in a segment ^ prefix[r] ^ prefix[l — 1] prefix[i] means a0 ^ a1 ^ a2 ^ ... ^ ai
 » 6 years ago, # | ← Rev. 2 →   0 I liked B and C but don't know how to solve D. There are so many ideas in my head with different time and memory complexities using huge amount of build-in data structures and written by my own but nothing of this, I guess, can pass tests. Please help me. What is your solution for D? UPD: I think, because of 15 given additional minutes, round must be rated.
•  » » 6 years ago, # ^ |   0 Did you use Convex-hull in C?
•  » » » 6 years ago, # ^ |   0 You don't need to compute convex hull, if you are already given a convex hull ;)
•  » » » » 6 years ago, # ^ |   0 Oh, i'm sorry. I mean traverse convex-hull clockwise to get the answer.
•  » » » » 6 years ago, # ^ |   0 But there can be some good ideas using parts of Graham's scan
•  » » » 6 years ago, # ^ |   0 No, as I said above, I used binary search on time before start walking and check used simple geometry like oriented triangle area
 » 6 years ago, # |   +6 let's convert it to unRated one :D
 » 6 years ago, # |   +1 Did anyone else feel this contest was hard?
•  » » 6 years ago, # ^ |   0 Yes I solved only problem A and bugged for B ;(
•  » » » 6 years ago, # ^ |   +1 Same. And it didn't help that I thought my B was pretests passed for an hour and then realized it was actually WA and couldn't figure out how to finish it. Pretty hard contest imo.
•  » » 6 years ago, # ^ |   0 NO ,,, its funny :D :D :D lots of errors :D
 » 6 years ago, # | ← Rev. 2 →   -8 Anyone who's D's solution passed in spite of using cin and cout ? I did use segment trees, got TLE on pretest 10.
 » 6 years ago, # | ← Rev. 2 →   0 19633422 can u tell me why my solution for D task is so slow?Now work:) printf and scanf. I thought that cout/cin is faster with ios_base::sync_with_stdio(false) than printf/scanf
•  » » 6 years ago, # ^ |   +3 Could try printf / scanf, the input is huge.
•  » » 6 years ago, # ^ |   +7 I have been in similar situation, you can try two optimizations: 1. Use scanf and printf instead of cin and cout. 2. Use dynamically allocated array using malloc, new or global array instead of vector. Time limit problem will most probably go away. And segment trees are slow(not asymptotically but practically) so you will most probably have to do these optimizations whenever using them.
 » 6 years ago, # |   +12 I thought it will be a unrated so i stopped doing contest after submitting B and start watching a movie. Now one a mine facebook friend ping me and realize me that it won't, pathetic :(
 » 6 years ago, # |   +110 This was evil! I was about to hack this :P
•  » » 6 years ago, # ^ |   +30
•  » » » 6 years ago, # ^ |   0
•  » » 6 years ago, # ^ |   +1 How do you hack this?
•  » » » 6 years ago, # ^ |   0 You don't. Because you are aiming for int overflow but, since the defender has defined int as long long, your hack will fail.
•  » » 6 years ago, # ^ |   -15 This is why #define should be translated when hacking
 » 6 years ago, # |   +16 It would be such a shame if Codeforces ignores the mistakes and makes the round rated. :) btw i'm saying this although I did good and I would benefit if it's rated And for god sake, why the hell isn't my pretest passed showing on standings?!
 » 6 years ago, # |   +2 Please, lets convert this round to unrated.. Because long checking and many bugs..
 » 6 years ago, # |   +24 this contest should be declared unrated .
 » 6 years ago, # |   -9 Making this round rated proves how unserious this website is
•  » » 6 years ago, # ^ |   0 3andak 7a2 wallahy :D :D da esmo hzar
•  » » 6 years ago, # ^ |   +8 the terms was equal for everyone. you guys are not logical :/
 » 6 years ago, # |   -31 this round was the worst round ever the server dies what is this shit !!!!!!! :(
•  » » 6 years ago, # ^ |   +5 Why do you care if you didn't participate?
 » 6 years ago, # |   +5 thanks for offering the problems,i like this contest,especially problem D,
 » 6 years ago, # |   +8 How to solve E?
•  » » 6 years ago, # ^ |   +8 I think it's dynamic programming, suppose k=p_1^a_1....p_s^a_s let F(b_1,b_2...b_s,w) be the minimum number of integers among a_1,a_2...a_w you should pick to make the number a multiple of p_1^b_1.....p_s^b_2. That works to get the minimum number of integers needed, although I'm not sure how to change it to get the actual set of number.
•  » » » 6 years ago, # ^ |   0 This can be easily represented as divisors of the input k, which can be found in time at first.
•  » » 6 years ago, # ^ |   +8 Just solved E using iterative DP with state[index,value to make] with scary timing..!! :3 from the looks of it there should be a faster soln i think..!! :/
•  » » 6 years ago, # ^ |   0 I solved it by bitmaks dp, since 2*3*5*7...*31*33 > 10^12 , so it should probably fit in the time limit. I can't submit it check though, I've heard that the TL is pretty tight.And lucky me just read this question's (Here) editorial and learn the approach, and yes you read it correctly, this question has a similar constraint yet a 2 second TL ...
 » 6 years ago, # |   0 When after submitting A , my submission list was empty ,it was such a relief. But after 10 min my friend told me I have one submission pending I knew from that moment that this contest will judge my patience :P
 » 6 years ago, # |   0 I wish that Codeforces judging system were faster so that I could submit my solution 1 minute after the contest had ended.BTW Is there a way to submit a solution quicker after the contest ends?
 » 6 years ago, # |   +163 It seems long queue affected many participants of the contest. I counted number of users which got verdict after 15 minutes of waiting and verdict was non-OK. It is about 2000 participants.Taking into account such a significant number, we've decided to make round unrated. Sorry about it.Today long queue is not a systemic issue, it is a result of several unsuccessful matches. Be sure, I'll do my best to make the next round quickly judged.====Похоже, что длинная очередь существенным образом задела большое количество участников. Я посчитал у скольких участников тестирование было в очереди более 15 минут, а затем был получен вердикт не-OK. Таких участников около 2000.Принимая во внимание такую значительную цифру, мы решили сделать раунд нерейтинговым. Приносим извинения за это. Сегодняшняя проблема с очередью не системная, а результат нескольких неудачных совпадений. Можете быть уверены, я приложу все усилия, чтобы следующий раунд тестировался быстро.
•  » » 6 years ago, # ^ |   -8 nrO Mike Orz
•  » » » 6 years ago, # ^ |   -7 Dear Mike, I submit twice because of in queue judgement. Both of them passed pretest, at 47min and at 101min, but why it shows the time of the last one,at 101min?
•  » » » » 6 years ago, # ^ |   +5 You're second submission is considered as a resubmission which costs penalty and the first submission will be ignored.
•  » » » » » 6 years ago, # ^ |   -6 okay, never mind, unrated:D)))))))))))))))))
•  » » 6 years ago, # ^ |   0 thanks :)
•  » » 6 years ago, # ^ |   -13 Nice, last time when I didn't do well, it was rated, this time when I do well its, unrated. This is life I guess..Highly unfair
•  » » » 6 years ago, # ^ |   0 What if you get all FST?
•  » » » » 6 years ago, # ^ |   -10 All my solutions passed, sorry for ur pessimist attitude
•  » » » » » 6 years ago, # ^ |   0 So when you passed all the solutions, you say that 'Mike you should make it rated'.I just do not think it is fair in that I don't believe if you, unfortunately, get FST, you will still say that.
•  » » » 6 years ago, # ^ |   +3 Same here. I thougth that I'd become blue again :)
•  » » 6 years ago, # ^ |   -30 Make it optionally rated please.This is so wrong
•  » » » 6 years ago, # ^ |   +3 Why wrong? Getting WA in the middle of the contest at a very easy problem affects a lot your standings,not mentioning that codeforces was loading a page in about 2 minutes.
•  » » » 6 years ago, # ^ | ← Rev. 4 →   +2 Usually when these things happen on a site that involves some type of competition, you have to take a decision. Implementing both is very impractical. Do you realise how much time would it take to manually update rating for everyone who wants? and putting a time implementing a feature for it so just when only something like this happens it is used, is a waste of time and money. ( And it's also not fair, because if some people could actually submit solutions, your rank might probably be a little bit down).These issues rarely happen on CF. Just deal with it as if it was an ED round. No big deal, if you did well this time, you can pretty much do it again in future contests.
•  » » 6 years ago, # ^ |   +8 khar :/
•  » » 6 years ago, # ^ |   +17 What does "unsuccessful matches" mean ?
•  » » » 6 years ago, # ^ |   +34 Unlucky coincidences.
•  » » 6 years ago, # ^ |   0 How are solution judged? I saw pretestes passed submission for A increasing which show that judgement was going on. However no solution appeared for like first 45 min for B. Isn't it by submission time?
•  » » 6 years ago, # ^ |   -14 In my opinion people who got problem 1 or 2 wrong deserve to lose rating, but it's not a big deal either way.
•  » » 6 years ago, # ^ |   0 It is the second time when I do well in contest and then it becomes unrated.
•  » » » 6 years ago, # ^ |   0 Q_Q
•  » » 6 years ago, # ^ |   0 Mike why won't you try load balancing to more VMs, from example amazon web services or smth similar. They'd be probably necessary only for the first hour of the competitions when the load is quite bigger.
•  » » 6 years ago, # ^ |   -15 То что была задержка 15 минут, это не так много в тем более это было в начале ближе к середине и еще добавили время. У кого не прошло решение, и они ждали около 15 минут, они все равно знали об этом еще во время контеста и у них было много времени что бы исправить это. Это единственный контест где я так хорошо написал для себя, (никогда не был топ — 50) и сидел до очень поздней ночи что бы написать нерейтинговый контест и еще ждать пару часов своих результатов и потом увидеть что " UPD. Было принято решение сделать раунд нерейтинговым. ". Бомбит ужасно!!!
•  » » » 6 years ago, # ^ |   -7 Я узнал вердикт через 50 минут,ещё и 15 минут ждал чтобы послать.
•  » » » » 6 years ago, # ^ |   -16 Это ведь было только в первой середине контеста.
•  » » » 6 years ago, # ^ |   0 کیرم تو استایل تخمیت
•  » » 6 years ago, # ^ |   0 Kiram laye moohat mike
 » 6 years ago, # |   -11 I just want to ask why
 » 6 years ago, # |   0 I think that I solved B, but 10 seconds after the contest over when I try to submit it.I will submit it again when system testing is over,, I'll be sad if I got Accepted verdict...
 » 6 years ago, # |   0 It's may be the worst feeling when your code remain in queue for a long time.
 » 6 years ago, # |   +28 Anyone can see disappearing Huyum_nik message at the first place in comments? It appears on my screen for a second and then disappears until I reload the page.
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   0 As soon as i tried to submit solution i got logged out showing apache format error and since after repeated trying manage to submit after 40 mins later. May be same case with some other peoples too so would it be called a fair codeforces rated round ?? :-(
 » 6 years ago, # |   -12 Something strange.... int this codeforce round.... WHO TO CALL??????(Just a relaxing comment,don't take it so seriously Xp)
 » 6 years ago, # |   0 woops, got wrong answer on C because I used int instead of long long, to check if the dude could pass before the car arrived.
•  » » 6 years ago, # ^ |   0 why not double
•  » » » 6 years ago, # ^ |   +3 I wanted to avoid precision errors, I just checked if X[i]*u >= Y[i]*v.
 » 6 years ago, # | ← Rev. 2 →   +21 Were the submissions in a queue, or in a stack? :p :D http://imgur.com/t9AsTHtPS: I don't know how to paste image here, can anyone please help me?
 » 6 years ago, # | ← Rev. 2 →   +7 I think the problems for this round were pretty good (I struggled quite a bit honestly) but it sucks that the server was garbage the entire time. I didn't even know my B was WA until more than halfway through the contest. Overall, lots of nice problems just horrible circumstances. Hopefully Eran can write some more problems another time.Edit: An editorial will still be released as well right?
•  » » 6 years ago, # ^ |   0 I agree! The problems were excellent — hopefully they can come back for another round :)
•  » » » 6 years ago, # ^ |   -14 what нахуй exellent problems?? просто realization
 » 6 years ago, # |   -8 The round is unrated.I wish I can get higher rating but failed. :) I wish next round is rated! :)
 » 6 years ago, # |   0 I liked the concepts of the problems, they were very interesting, but I have a couple observations to make: As everyone has said, the servers were complete garbage, though this isn't the fault of the writers. I think the design for problem D was kind of bad, because you have a very large input, and at the same time large numbers. I had to use a map for the occurrences, which led to TLE on test 50. If the numbers in the array were to be at most, say, 1.000.000, there would have been no problem, but by making the numbers as large as a billion, you are making the problem harder and the time complexity greater for no real purpose. For both large input and large numbers, the time limit was too tight. But I think the writers have good potential! They are able to write hard, interesting and complex problems. I wish them luck in the next rounds they will (hopefully) write.P.S. I find it is in good taste to make the round unrated, mostly because of the huge server issues. Thank you for that.
•  » » 6 years ago, # ^ | ← Rev. 5 →   +5 If 1 ≤ n, q ≤ 2 × 105 on D then Mo's algorithm will pass easily but i think this way the problem will be very stupid,just apply a well known algorithm.The limits are ok,i looked at your code and saw that you used map of vectors but it is very very slow.
•  » » 6 years ago, # ^ |   0 Yes also 1 <= N , Q <= 1.000.000 made the time limits even tighter
 » 6 years ago, # | ← Rev. 2 →   -15 :c
•  » » 6 years ago, # ^ |   0 Sorry for that, it just burned quite a lot.
 » 6 years ago, # |   +3 When will the problems moved to practice and editorials published ?
 » 6 years ago, # |   0 Why unrated ?
 » 6 years ago, # |   -52 Congratulations for what? For doing the best round in their lives only to realise its unrated?
•  » » 6 years ago, # ^ |   +39 We are sitting here not only for ratings, man
 » 6 years ago, # |   +12 Although there was sure some inconvenience, I still think it a good contest~ Many thanks to contributors~~~The delay and some other problems are largely due to the large number of participants and div 2 only. It doesn't affect that CF is still a great community to improve coding skills. It just mean that this site is becoming more and more popular and the server need to be upgraded. I think we should support the site rather than complain the organizer or the limited source of the site.That's it. Just feel a little sad seeing so many people blame the organizer and the site.
 » 6 years ago, # |   +6 Is the testing gonna end any time soon? I was hoping to submit some code.
 » 6 years ago, # |   0 For problem no B 703B - Mishka and trip , Why my this submission : 19639339 got accepted verdict but this implementation, 19639538 , got wrong answer? When I used cin/cout its got accepted , but for scanf/printf it gives me wa verdict. Please help .... Thanks in advance.
 » 6 years ago, # |   0 Why Round is UnRated !!!? (Unusual)
•  » » 6 years ago, # ^ |   +4 Because life can be cruel sometimes, but you need to tough it out.
 » 6 years ago, # |   -9 Why unrated? It's unfair...
•  » » 6 years ago, # ^ |   +20 It's unfair... that's Why unrated !
 » 6 years ago, # |   0 Is it really that the contest was unrated?
 » 6 years ago, # |   +3 Hope the editorial will not come out as late as the number of problems,duration and scoring distribution did.
 » 6 years ago, # |   0 Well,Why is the time limit of E is 1s? Some of the Accepted source takes 997ms to passed.And I was TLE because of the large constant.QAQ There are same people's Sources didn't Accepted because of the same reason.Could you make the time limit longer?These are Accept Sources: 19634240 19636289
•  » » 6 years ago, # ^ |   -12 Nice Chinglish
 » 6 years ago, # | ← Rev. 3 →   0 I am not quite familiar with geometry stuff, I wonder what's the idea behind judging if the point we are checking is the front or the back of the bus?Edit: I think I have an idea now... Almost forgot about high school maths. Btw, is everyone else's contest page show "pending for system test" right now?Edit2: Just noticed "input are given in counter-clockwise order" FML
•  » » 6 years ago, # ^ |   0 Could you explain your idea please? That problem had me completely stumped.
•  » » » 6 years ago, # ^ | ← Rev. 6 →   +1 My implementation: http://ideone.com/mFVRYD(I can't submit it right now — it says the contest is still pending for system test, so I can't guarantee this code is bug free, as I always miss out small counter-case details. I am pretty sure the approach is correct though.)Case 1: The pedestrian will not get hit by the car if he rushes through as fast as possible — in this case we just have to check whether he will reaches point (0,y) earlier than each (x,y) of the car.Case 2: The pedestrian will have to wait for the car to past through first.In this case we just consider everything as the back of the car, and sort all the vertices in increasing y-axis value. Then you just check for the later event — the pedestrian reaches point (0,y) or the point (x,y) of the car passes (0,y). And as a smart-aleck I missed this obvious observation when I coded, instead I did the following in my code.We can check from the lowest point of the car, the sequence of edges which starts from it and has a positive slope is the parts where it could possibly "limit" the pedestrian speed as a part of the back of the car. (This is because it is guaranteed the vehicle is a CONVEX POLYGON, and it is convenient to implement since the edges are given in counter-clockwise order.) Again we check for the later among the two events mentioned above — it's fine to just check these points anyways. Don't forgot to calculate for time (0,0) -> (0,ymin) and (0,ymax) -> (0,w)UPD: Just rewrote the code in a much more simple fashion, this should be easier for anyone to understand the idea. http://ideone.com/ZjTybR
•  » » » » 6 years ago, # ^ |   0 My idea is similar. I implemented it during the contest but after my solution, which past pretests, was judged with the system tests gave WA#12. I too have the problem with still pending system testing as I wrote below. Here is my implementation:19631048.
•  » » » » » 6 years ago, # ^ | ← Rev. 4 →   +3 I think you miss out cases where miny>=w and mawy>w.Here is a hack case for you:5 1 1 2 1 2 3 1 4 3 3 4 1 4It's just the test case 1 with w=1, the pedestrian is able to rush to (0,1) with ease, yet your code outputs 3.0s.(Whopos just read the constraints again... nvm it's guarantee every y<=w)
•  » » » » » » 6 years ago, # ^ | ← Rev. 3 →   0 OK. So there has to be something else that is wrong.
•  » » » » » » 6 years ago, # ^ |   0 I found out my mistake (it was in the second case). Here is the AC implementation: 19664924 (complexity: O(n))
 » 6 years ago, # |   0 I'm new here, why is the contest unrated? Because of the delay time caused by long queue?
•  » » 6 years ago, # ^ |   0 Probably yes, since it has cause unfairness in terms of rewarding points.
 » 6 years ago, # |   0 How many machines does Codeforces have?
 » 6 years ago, # | ← Rev. 5 →   -16 Unrated :(
•  » » 6 years ago, # ^ |   0 There were amazing beautiful problems which worth thinking! rating isn't the priority always!!!
•  » » 6 years ago, # ^ |   0 Please don't curse Codeforces. Don't you think that it would have been so unfair if this contest was rated? Besides, is rating really so much important? Think about the happiness which you obtain after solving a problem! :)
 » 6 years ago, # |   0 For problem no B 703B - Mishka and trip , Why my this submission : 19639339 got accepted verdict but this implementation, 19639538 , got wrong answer? When I used cin/cout its got accepted , but for scanf/printf it gives me wa verdict.what is wrong with it?Could anyone explain please ? .... Thanks in advance.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 you made array with a variable as the size!!!! amazing!!! i don't know but maybe the problem is from this miracle!!!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Please anyone help me with that problem
 » 6 years ago, # |   0 Is there someone else having trouble submitting code now?It just says 'You can't run practice now or contest does not support practice.'I see some submissions, but I can't submit still.
•  » » 6 years ago, # ^ | ← Rev. 7 →   +6 When I enter yesterday contest now, it still says pending system testing (and of course I can't submit and see what are the tests of the tasks). Maybe there are more people with this problem. I found that this problem is on the devices (my laptop and tablet) where yesterday I was checking the standings for a lot of time and for example if I open codeforces on my phone, there is no such problem. Could someone offer me some advice or a way to fix it?UPD: Now the problem mysteriously disappeared. Finally the contest finished for me :). Does someone still have this problem?UPD2: The problem returned again.
 » 6 years ago, # |   +17 Please Switch on Practice for this contest. It shows Contest not over and you cant practice
 » 6 years ago, # |   0 is O(N * (number of divisors of K)) supposed to pass in E?
•  » » 6 years ago, # ^ |   -9 Our correct solution has complexity O(n * divisors(k) * primes(k)). I will try to publish editorial as soon as possible.
•  » » » 6 years ago, # ^ |   +16 WTF, so the problem is only optimization!
•  » » » » 6 years ago, # ^ |   -29 Well... That's it! We decided that otherwise it will be too easy for the Div2E.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +13 Do you think excluding O(n*divisors(k)*log_gcd) solutions was a good idea with author's O(n*divisors(k)*primes(k))?
•  » » » » 6 years ago, # ^ |   -37 Yep. We tried to exclude such solutions. However it seems like not all tests were good enough.
•  » » » » » 6 years ago, # ^ |   +64 Guessing author's constant optimizations — yeah, it is what problem E must be.
•  » » » 6 years ago, # ^ |   0 wait for editorial
 » 6 years ago, # |   0 This round turns into unrated! it's so disappointing!i hope this type of inconvenience won't happen again :/
 » 6 years ago, # |   -17
 » 6 years ago, # |   +18 Someone help me understand... Why is the contest still pending system tests? I can't even submit a solution now. O__O
 » 6 years ago, # |   +11 Its taking forever for the system testing to finish. I am not able to submit solutions to any of the answers to yesterday's contest.
 » 6 years ago, # |   +9 Why one day after contest it's on "pending system testing" level?!
 » 6 years ago, # | ← Rev. 4 →   +10 Please publish the editorial and allow to submit the solution.It is almost a day now... UPD :- It is published now....
 » 6 years ago, # |   0 Will O( N SQRT(N) ) work for D?
•  » » 6 years ago, # ^ |   0 No. I had n log n and tle
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 what was your nlogn idea? you must be calculating it wrong, the intended solution is nlogn itself.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I sort queries. I have segment tree which can make xor on range and can return xor value of range. I iterate through input data and do xor(1,last_place[input [i]], input [i]). In i step I have in tree data about xor(only for numbers with even amount of occur ) for ranges [1,2,3,...,i;i]. Now i can just check valueInTree(query[i].start,query[i].start).Now work:) printf and scanf. I thought that cout/cin is faster with ios_base::sync_with_stdio(false) than printf/scanf
•  » » 6 years ago, # ^ |   0 Can't you just check it yourself? Just multiply them, ...and tada, the answer appears within a second!
•  » » » 6 years ago, # ^ |   0 i understand its 10^9 but it is a bit peculiar that the time limit is 3.5 seconds and looks like it is so to make such solutions run
 » 6 years ago, # | ← Rev. 2 →   0 I have provided an explanation to problem D here
 » 6 years ago, # |   0 Editorial is here: http://codeforces.com/blog/entry/46434
 » 6 years ago, # |   0 Still pending system testing. Why is this problem caused and is there some solution?
 » 6 years ago, # |   0 Editorial Please ..!!
•  » » 6 years ago, # ^ |   0 Editorial is ready, but there are some problems with displaying it. Still waiting fixes.
•  » » » 6 years ago, # ^ |   +1 Thank you! It's so nice when authors answer the comments.
•  » » » 6 years ago, # ^ |   0 Please allow us to submit solutions now
 » 6 years ago, # | ← Rev. 2 →   0 Has anyone solved Div2D with persistent segment tree . My submission (Code) is giving Runtime Error on TestCase 14.I don't have any clue of the reason and have allocated more than enough memory (I think). The idea of pst's root[i] is to store xor of distinct numbers which are as close to it as possible.
•  » » 6 years ago, # ^ |   0 Look at constraints, 211111 is not enough.
 » 6 years ago, # |   0