### ksun48's blog

By ksun48, 5 weeks ago, ,

Hello denizens of Codeforces once again!

After our last two rounds, Yang Liu (desert97) and I (ksun48) are pleased to announce Codeforces Round #492, which will happen on June 24, 2018 at 19:35 MSK. There will be two versions of the contest, one for users in Division 1 and one for users in Division 2. Both versions will have six problems, with four problems shared between the versions.

The round will feature our friend and superstar member of ACM-ICPC team MIT TWO, Allen Liu (cliu568).

The scoring distribution will be visible once the contest begins. As usual, we'd like to thank our wonderful problem coordinator KAN and Codeforces administrator MikeMirzayanov, as well as the rest of the Codeforces staff for keeping this site an amazing place for competitive programming. Thanks also to our testy testers winger, AlexFetisov, and demon1999.

This round is in honor of uDebug who have supported Codeforces on its anniversary. Thank you, uDebug! uDebug is an enthusiastic community of competitive programmers who help each other out by answering questions on chat, providing hints and solutions to problems from several online judges, furnishing test input and sharing feedback. On uDebug, you can select a problem you’ve coded up a solution for, provide input, and get the "accepted" output. You can visit it by the link.

Good luck! As always, we encourage competitors to read all the problems.

(̶a̶l̶s̶o̶,̶ ̶I̶ ̶s̶e̶e̶m̶ ̶t̶o̶ ̶h̶a̶v̶e̶ ̶h̶e̶a̶r̶d̶ ̶s̶o̶m̶e̶ ̶r̶u̶m̶o̶r̶s̶ ̶f̶l̶o̶a̶t̶i̶n̶g̶ ̶a̶r̶o̶u̶n̶d̶ ̶a̶b̶o̶u̶t̶ ̶a̶ ̶s̶p̶e̶c̶i̶a̶l̶ ̶ ̶s̶u̶r̶p̶r̶i̶s̶e̶ ̶w̶h̶i̶c̶h̶ ̶m̶i̶g̶h̶t̶ ̶b̶e̶ ̶h̶a̶p̶p̶e̶n̶i̶n̶g̶ ̶d̶u̶r̶i̶n̶g̶ ̶s̶y̶s̶t̶e̶m̶ ̶t̶e̶s̶t̶i̶n̶g̶,̶ ̶s̶o̶ ̶k̶e̶e̶p̶ ̶y̶o̶u̶r̶ ̶e̶y̶e̶s̶ ̶p̶e̶e̶l̶e̶d̶!̶)̶

EDIT: And the rumors are confirmed! Go to http://codeforces.com/blog/entry/60176 after the contest is over to discuss the problems or voice your complaints along with scott_wu and ecnerwal!

EDIT: Due to some last minute changes, each version will have six problems, with four shared problems.

EDIT: The Div. 2 score distribution is 500-1000-1500-1750-2500-2750 and the Div. 1 score distribution is 500-750-1500-1750-2250-2500.

EDIT: Congratulations to the winners of the round!

Div. 1:

Div. 2:

Thanks to everyone for participating! The editorial is available at http://codeforces.com/blog/entry/60217.

•
• +303
•

 » 4 weeks ago, # |   0 Auto comment: topic has been updated by ksun48 (previous revision, new revision, compare).
 » 4 weeks ago, # |   +138 "a special surprise which might be happening during system testing"fast system testing!
•  » » 4 weeks ago, # ^ |   +162 Don't get your hopes up...
•  » » 4 weeks ago, # ^ |   +55 maybe pretests = systests, so there is no system testing and nobody fails :)
•  » » » 4 weeks ago, # ^ |   +86 Yeah, and get 50+ pages queue during the round, would be nice.
•  » » » » 4 weeks ago, # ^ |   +94 Then we will also have a special surprise during the whole contest.
•  » » » » » 4 weeks ago, # ^ |   0 Maybe if you have passed pretests but failed systests you'll have half points for the problem.
•  » » » » » 4 weeks ago, # ^ |   0 I got bored,not surprised at all
•  » » » » 4 weeks ago, # ^ | ← Rev. 25 →   -49 Of course not, Codeforces servers are too good!!!! Then can handle up to +10000 online judges at the same time... LOL, yesterday I could'nt even enter the problemset, because servers were so busy.
•  » » » » » 4 weeks ago, # ^ |   +4 It seems that when the comment is hidden, people are more likely to read and downvote...
•  » » » » » » 4 weeks ago, # ^ |   0 It seems sometimes people downvote just because the colour of your name isn't good enough!
•  » » » » » » » 4 weeks ago, # ^ |   +5 Here Downvoting is inversely proportional to your ratings
•  » » » » » » 4 weeks ago, # ^ |   +2 it's like a self-fulfilling prophecy. The website says the post got negative feedback, so it gets more negative feedback.... lol
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +6 Then there's no systest so there's maybe also no such 'during' system testing ? ;)
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   -13 Or maybe the surprise is that there are no/weak pretests o_O
•  » » » » 4 weeks ago, # ^ |   0 Or maybe there will be so many failed solution on SysTest
•  » » » » » 4 weeks ago, # ^ |   +6 The surprise was, that there's no surprise :D
 » 4 weeks ago, # |   +31 Yaaay
 » 4 weeks ago, # |   +30 I had enough surprises after today's D problem :(
 » 4 weeks ago, # | ← Rev. 2 →   +29 Its for me:)
•  » » 4 weeks ago, # ^ |   +33 And are you the ball?
•  » » 4 weeks ago, # ^ |   +3 Same with Colombia and Poland
•  » » » 4 weeks ago, # ^ |   0 Yap, but can get second half of the match fully.
 » 4 weeks ago, # |   +3 Can't wait to see that special surprise :)
 » 4 weeks ago, # |   +2 Is it on english only or you have russian version of contest too?
•  » » 4 weeks ago, # ^ |   +44 All official Codeforces Rounds have problems available in both Russian and English.
 » 4 weeks ago, # |   +44 I heard that, as per this blog post, scott_wu and ecnerwala are going to call ksun48 immediately after the contest for a lively discussion about the contest.
 » 4 weeks ago, # |   +28
 » 4 weeks ago, # |   +3 why the score distribution will be revealed after the contest starts ?
 » 4 weeks ago, # |   0 It's so exciting!! Happy coding everyone.
 » 4 weeks ago, # |   +63 I smell math problems.
•  » » 4 weeks ago, # ^ |   +1 Are you playing Dota 2? ;)
•  » » » 4 weeks ago, # ^ |   0 Dota is love, Dota is life.
•  » » 4 weeks ago, # ^ |   +8 LGD is invincible!
•  » » » 4 weeks ago, # ^ |   -8 Yeah, but i don't like their offlaner.
 » 4 weeks ago, # |   -33 is it rated?
 » 4 weeks ago, # | ← Rev. 2 →   +26 How is scott_wu orange in your post? o_O
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +98 You can write [user:some_handle,yyyy-mm-dd] and the handle of user some_handle in the post/comment will be the same as it was actually on the date: year yyyy, month mm, day dd.For example: [user:karanbatra,2017-07-01] -> karanbatra; [user:karanbatra,2017-08-01] -> karanbatra; [user:karanbatra,2018-06-24] -> karanbatra.
•  » » » 4 weeks ago, # ^ |   +5 Oh that's great!!!
•  » » » 4 weeks ago, # ^ |   +27 How to do like this: scott_wu wasn't newbie in any period of time!
•  » » » » 4 weeks ago, # ^ |   +19 It's easy:I'm LGM : IIIIIIIIIIIIIIIIIIIII
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 Cool :)
•  » » » 4 weeks ago, # ^ |   +2 But Why u did so??
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 Or you can use HTML VladProgP.S. You have never been red.
•  » » » » 4 weeks ago, # ^ |   +7 Yes, with HTML even you can be admin VladProg XD
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Abelyan Numb VladProg You are both olive now
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +11 But when you write it with HTML codeforces doesn't send you a notification that someone mentioned you.P.S. Thanks I love olive :D
•  » » » 4 weeks ago, # ^ |   0
•  » » 4 weeks ago, # ^ |   +10
 » 4 weeks ago, # |   0 Why the 2 divisions are divided by 1900? Anyway I am glad to take part in Div.1.
 » 4 weeks ago, # |   0 What about the surprise? :(
 » 4 weeks ago, # |   +49 I want to be the man with the worst contribution can you downvote me please?
•  » » 4 weeks ago, # ^ |   +84 Ah! The wonders of reverse psychology.
•  » » 4 weeks ago, # ^ | ← Rev. 5 →   -7 Best way for that is the golden sentence "Is it rated?"
•  » » 4 weeks ago, # ^ |   0 Nice try son, this is how you do this.
 » 4 weeks ago, # |   +1 Amazing email id: udebug@udebug.com
 » 4 weeks ago, # |   0 Will the conditions of tasks in the Russian language?
•  » » 4 weeks ago, # ^ |   0 Read this.
 » 4 weeks ago, # |   -33
•  » » 4 weeks ago, # ^ |   -25 not even a deam it is true wow..
•  » » 4 weeks ago, # ^ |   -21 How did you make it ?
•  » » » 4 weeks ago, # ^ |   +5 With HTML: CodeMohamedAhmed04 
•  » » » » 4 weeks ago, # ^ |   -8 Thanks rkocharyan :)
 » 4 weeks ago, # |   +10 500-1000-1500-1750-2500-2750 not 500-100-1500-1750-2500-2750
 » 4 weeks ago, # | ← Rev. 2 →   0 Div.2 B = 100 points XDEDT : Fixed
 » 4 weeks ago, # |   +23 swap(C, D);
 » 4 weeks ago, # |   +53 What exactly was the point of having a problem like div1 A which is conceptually pathetic but extremely cumbersome implementation?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   -41 yep
•  » » » 4 weeks ago, # ^ |   0 He is talking about Div1 A not Div2 A
•  » » » » 4 weeks ago, # ^ |   0 damn. div1 a/ div2 c was hell. I wonder if I'll be able to sleep peacefully after seeing it.
•  » » 4 weeks ago, # ^ |   +8 I didnt think it was that cumbersome, just implement a rotation.
 » 4 weeks ago, # |   -20 hello i don't know my word is right or not bud div2 D problem was duplicated. here it's not a classic algorithm like shortest path it's the solution itself!
•  » » 4 weeks ago, # ^ |   +4 In div2 D you are only allowed to swap adjacent elements.
•  » » » 4 weeks ago, # ^ |   0 Right, that's another important difference.
•  » » » 4 weeks ago, # ^ |   0 yes but here we have sth but as my friend said we don't have to sort the array
•  » » 4 weeks ago, # ^ |   +4 And you don't have to "sort" the array.
•  » » 4 weeks ago, # ^ |   0 It doesn't look exactly the same to me: the resulting array needs not to be sorted as 33114422 is a valid answer for div2-D as well.
•  » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   +1 In our problem, you can swap only adjacent elements.
•  » » » » 4 weeks ago, # ^ |   0 kind of bubble sort.
 » 4 weeks ago, # |   +108
•  » » 4 weeks ago, # ^ |   +8 How to solve this ?
•  » » » 4 weeks ago, # ^ |   +64 Let's take 3 vectors of length no more then L. Draw them and their negations from one point. Since there are 6 vectors there are two with angle no more then pi/3 between them. Their sum has length no more then L (use Law of cosines to prove).Then the solution looks like this: while we have at least 3 vectors, reduce the number of vectors using the statement above. When we have 1 or 2 vectors, it is trivial.To restore the answer you should build a tree of dependences and then run dfs.
•  » » » » 4 weeks ago, # ^ |   +3 I had a much simple sol. first calculate x,y taking all vectors positive. Then if x>0&&y>0 then take a vector with xi > 0&yi > 0 and reverse it and calculate new x,y. do same thing in any 4 directions as need until we get required answer.
•  » » » » » 4 weeks ago, # ^ |   0 I don't understand this.2999999 -1-1 999999is a countertest, right?
•  » » » » » » 4 weeks ago, # ^ |   +10 you just take both of them as it is. 999998 999998 is a valid answer.
•  » » » » » » » 4 weeks ago, # ^ |   0 Oh, I'm stupidThen repeat both vectors two times.
•  » » » » » » » » 4 weeks ago, # ^ |   0 my bad. I think i've actually missed some cases. probably it won't pass sys tests.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +7 Wow, that's beautiful! However I didn't have such nice ideas, so did simple local search (take 1 or 2 random vector and try negating them) and I think that actually it is rather impossible to make such solutions fail. Do you have any countertests on mind?EDIT: I got safe AC in 109ms
•  » » » » » 4 weeks ago, # ^ |   0 What about lot of zeros/small vectors, and several large?
•  » » » » » » 4 weeks ago, # ^ |   0 Doesn't seem to be a problem. I even tested my solution locally on such tests. I will have low chance of looking at big vectors but I will also less work to do on them which kinda balances out.
•  » » » » » » » 4 weeks ago, # ^ |   0 what if 2 vectors 1000000 0 and rest are 0 1. isn't there a chance that the 2 large vectors get never chosen?
•  » » » » » » » » 4 weeks ago, # ^ |   0 There is a chance. But it is something like 0.000000000000000000000000000000000001
•  » » » » » 4 weeks ago, # ^ |   0 Looks hard. Try this: #include #include #include using namespace std; int main() { printf("100000"); for (int i = 0; i < 100000; i++) { int y = 900000 + i; if (i % 4 == 1 || i % 4 == 2) y *= -1; printf("20 %d\n", y); } return 0; } 
•  » » » » » 4 weeks ago, # ^ |   0 I think I got it20 90000020 -100000 (x9)repeat 10000 times.This is a local minimum if you allow only changes in up to 9 vectors at once.
•  » » » » » » 4 weeks ago, # ^ |   0 My solution dealt with your first case using only 23 improvement phases and in second case using only 356 — which is eps. You are welcome to experiment with my code on your own and then tell me about results ;).
•  » » » » » » » 4 weeks ago, # ^ |   0 Well, can you remove random initialization and run second case?) I don't think that I can do anything against random initialization but I'll try.
•  » » » » » » » » 4 weeks ago, # ^ |   0 Yeah, I agree that this breaks my solution if I remove random initialization of signs. I didn't look at ACed solutions, but there is positive probability that such test will break some of them, if authors didn't wonder about breaking such solution (but maybe they did, I don't know). However luckily my solution contained random initialization and it stands still :).
•  » » » » » » » » » 4 weeks ago, # ^ |   0 Congrats on this :)
•  » » » » 4 weeks ago, # ^ |   0 very nice solution!
•  » » » » 4 weeks ago, # ^ |   0 Wasn't simulated annealing an appropriate solution? I got a TLE on system test 51, but otherwise it looked fine to me.
•  » » » » » 4 weeks ago, # ^ |   0 What is 'fine'? Can you prove it or something?
•  » » » » » » 4 weeks ago, # ^ |   0 By "fine" I meant it looked the right approach to me, before discovering it failed :) I assumed, since the problem asked for "a" solution, not the "best" solution, that an approximate algorithm would do the job.Clearly this was not the right thinking! Could you please elaborate what do you mean by "prove" (I assumed the claim that a solution exists assured convergence) and how would you have considered or excluded this kind of solution?Thank you very much!
•  » » » » » » » 4 weeks ago, # ^ |   -29 By your definition it is you who should be asked if solution is fine. Did it look the right approach to you?It is true that this problem allows some approximate algorithms. If not proving the solution is OK with you — fine.
•  » » » » » » » » 4 weeks ago, # ^ |   0 I was not trying to define anything, rather I clearly admitted that my reasoning was wrong and I humbly and genuinely asked for advice to improve.I'm not quite understanding your harsh response...
•  » » 4 weeks ago, # ^ |   -9 I thought to start practicing acm.timus.ru, I hope I would have started. Maybe I would have done this problem.
 » 4 weeks ago, # |   +1 maths too hard~~
 » 4 weeks ago, # | ← Rev. 4 →   +32 I solved Tesla in a very roundabout way...
 » 4 weeks ago, # |   +10 thanks for beautiful task F
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +22 Your submission page basically is a graveyard
 » 4 weeks ago, # |   +14 Stream starting now! Check out https://www.twitch.tv/ttocs45 to discuss problems and watch tests.
•  » » 4 weeks ago, # ^ |   0 do you stream after every contest ?
 » 4 weeks ago, # | ← Rev. 2 →   0 [Edited] http://codeforces.com/contest/996/submission/39627469 can someone point out the mistake with this dp implementation of problem E ?
•  » » 4 weeks ago, # ^ |   +1 You took ints, instead of long long?
•  » » » 4 weeks ago, # ^ |   0 i'm sorry please check this one out , i submitted with long long as well . http://codeforces.com/contest/996/submission/39627469
 » 4 weeks ago, # | ← Rev. 4 →   +32 IMHO, some of last rounds really proved that codeforces reduced quality of problems required for contest. Div1A — very easy to solve, very hard and boring to implement. Div1B — super simple and super old classic problem, I would expect it for div2A-B, not even close to div1A-B, div1C — duplicated problem.Don't know about other problems though.
 » 4 weeks ago, # |   +2 how to host contest :-randomly select problams from other platform
 » 4 weeks ago, # |   +40 One of the best rounds lately (IMHO), except that Div1C is boyan.
 » 4 weeks ago, # | ← Rev. 2 →   +19 I cowarded out of submitting div 1 B and C and then it turned out both solutions were correctHow do you learn to prove greedies?
 » 4 weeks ago, # |   0 please tell me you are going to change the scoring .... C has fewer submissions than D and E and i solved ABC :'(
 » 4 weeks ago, # |   +113 1.59.59
 » 4 weeks ago, # |   +38 Despite known C, I really liked the problems. 'maintain sum of numbers in array' for div1D (and which takes 20 minutes to solve) is bold. F is beautiful. I also really liked B, nice easy problem.
•  » » 4 weeks ago, # ^ |   +43 Oh, and I hope that E has proved beautiful solution and not my randomized garbage. And that randomized solutions for C will get WA.
•  » » » 4 weeks ago, # ^ |   +14 For C, I random shuffled the vectors and choosed them greedily. Passed at 77 ms.link
•  » » 4 weeks ago, # ^ |   -13 Hey Um_nik I didn't get the editorial for Div1D. What's the point of maximising and minimising the xi's. What I get is that there is just some numbers, which are changing in each step, one at a time, and we need to find expected value of them at every stage.But what was the point that Allen want's to maximise and minimise and all. Please can you explain...
 » 4 weeks ago, # |   +41 I found B-F questions really nice, but it was totally ruined by that A, to the extent that I did not even take part. Loved the B-F problems though!
 » 4 weeks ago, # | ← Rev. 2 →   0 Is this idea for C correct?Let the angle between two vector (a, b) the smaller one between (a, b) and (a,  - b)Case n = 2 is trivial.If n ≥ 3, then there are at least two vector i and j with angle smaller than 60 degree. And |i - j| or |i + j| will be smaller than or equal to max(|i|, |j|). So we can just add (or substract) these two vector up and we will have a similar problem with size n - 1. We can randomly choose any two vector until we find a pair that work.I got WA on pretest 6 because I only do the random choice one instead of doing a loop (in a moment of panic), so I don't know if my idea is correct.
•  » » 4 weeks ago, # ^ |   0 I did a very simple solution: greedily choose the sign, which gives the smallest radius at the current moment. I see that a few others also did a similar approach, for example, OO0OOO00O0OOO0O00OOO0OO
•  » » » 4 weeks ago, # ^ |   +10 31000000 00 1000000600000 -600000
•  » » » » 4 weeks ago, # ^ |   +3 the greedy gives -1 1 1, isn't this correct?
•  » » » » » 4 weeks ago, # ^ |   0 what if it gives 1 1 1?chosing 1 at beginning and -1 gives same radius.
•  » » » » » 4 weeks ago, # ^ |   0 OK, there you have free choice for second3100000 0-1 1000000600000 -600000
•  » » » 4 weeks ago, # ^ |   0 I thought this solution wouldn't work?
•  » » » » 4 weeks ago, # ^ |   0 It shouldn't work. It gives WA 26 when sorting the array from largest to smallest, so there is a countertest like 26 but sorted
 » 4 weeks ago, # |   +10 See this solution for problem B — http://codeforces.com/contest/996/submission/39628153 How is this passing the following testcase without TLE: 2 1000000000 1000000000 Can someone explain?
•  » » 4 weeks ago, # ^ |   0 I completely agree. How this passes I do not understand. In my room a lot of people solved the problem in a double cycle, but no one could hack. It cost me a lot.
•  » » 4 weeks ago, # ^ |   +1 I tried to hack this solution https://codeforces.com/contest/996/submission/39614615 using above testcase but it gave unsucccessful hacking attempt.
•  » » 4 weeks ago, # ^ |   0 Also I tried this testcase on my PC. It is taking easily 3-4 secs. Don't know what is happening here.
 » 4 weeks ago, # |   0 div2.C:toooooo difficult but 1500 div2.D:toooooo easy (than C) but 1750 div2.F:toooooo easy (than E and C) but 2750!!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 That's why they said we encourage competitors to read all the problems
 » 4 weeks ago, # |   0 I really think D gonna be a disaster. I am not even sure why my solution passed
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +2 For D: my solution was taking the leftmost unpaired person and moving the other person left till they meet. And repeat. I think my algorithm's correct.What was yours?
•  » » » 4 weeks ago, # ^ |   +1 What i did was mapped each element again to some integer like say my array was 2 1 2 1 i made it 1 2 1 2. And then did inversion count. Dont know if its correct
•  » » 4 weeks ago, # ^ |   0 Even I think so. Probably, there will be a lot of failed system tests. Appears too easy to be div2 d.
 » 4 weeks ago, # |   +25 div2C was frustrating.
•  » » 4 weeks ago, # ^ |   0 I think so too. I based my observation on this tc. 2 2 0 1 0 2 1 0 2 0 
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 After finish debugging my solution for Div 2C. The contest is over. :)
 » 4 weeks ago, # |   +9 It's not an often case for me when DEF have better ratio points/needed time than ABC :p (especially A which took me longest time XD)
 » 4 weeks ago, # |   0 can't understand div1.D QAQ
•  » » 4 weeks ago, # ^ |   0 Ya that was a pretty easy problem but I didn't get the problem statement so couldn't do it.
•  » » 4 weeks ago, # ^ |   0 It would have been much clearer if they explained 1st test case.
 » 4 weeks ago, # | ← Rev. 2 →   +11 For Div 2 B, I failed to hack a solution with the case N = 2 and maximum a[i] values, when it directly simulated the problem situation. Can someone explains how this magician bamboozled me this badly?P.S. This solution failed when run on the case on my own computer.
•  » » 4 weeks ago, # ^ |   0 haha i even found a similar solution in my room and even his code runs for 1000 1e9s smoothly. weird :/
•  » » 4 weeks ago, # ^ |   +4 Same. I tried to hack 39618975 with 2 1000000000 1000000000 but the hack failed.
•  » » » 4 weeks ago, # ^ |   0 What was the runtime?
•  » » » » 4 weeks ago, # ^ |   +21 717ms only. Looks like Mike has got supercomputers now.
•  » » » » 4 weeks ago, # ^ |   0 I successfully hacked 3 TLE solutions, so not sure what's up. Could be some C++ optimizations?
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 http://codeforces.com/contest/996/submission/39617181The man passed system testing. How?EDIT: Some people keep citing compiler optimizations, but the extent of that should not allow someone with the most naive solution idea to pass system tests (which included max case).
•  » » » » » » 4 weeks ago, # ^ |   0 I think the testing machines got faster, and now there is a problem setting proper time limit in order to TLE O(n) complexity. Check out this comment
•  » » » » » » 4 weeks ago, # ^ |   0 Looks like compiler optimization also plays some role: I ran this on my laptop with and without -O2, and got 0.8s and 5s runtimes. If I replace the increment of i with increment modulo n (using %), then runtimes are 8s and 10s. So, optimization doesn't optimize as well if there is a % involved.
•  » » 4 weeks ago, # ^ |   0 i think 2 1 0 will hack him !
•  » » 4 weeks ago, # ^ |   +3 ksun48 Many people have this doubt. Can you please explain how a 10^9 solution can pass?
•  » » » 4 weeks ago, # ^ |   +5 This is explained each time a 10^9 hack fails. It's almost always due to compiler optimizations, which can do magic if the operations are not too complicated, AFAIK.
•  » » » » 4 weeks ago, # ^ |   0 Can you or do you know someone who can elaborate on this? This came as a shock... Any sort of link to any article/CF blog or stack overflow relating to this may also be useful. Please.
•  » » » » 4 weeks ago, # ^ |   +3 This time the ones that get ACs get them with runtimes of more than 800ms, so optimizations seem less likely than faster testing machines.
•  » » 4 weeks ago, # ^ |   0 same happened for me also, I hacked using N=2 and A[1]=10^9 and A[2]=10^9 but the solution gave TLE on big value of N and larger values of array. http://codeforces.com/contest/996/submission/39615146
 » 4 weeks ago, # |   0 How to solve div 2 B ? I saw alot of bruteforce B that passed pretest
•  » » 4 weeks ago, # ^ |   0 how did the brute force passed....i am also wondering ..
•  » » » 4 weeks ago, # ^ |   +3 @ksun48 how??
•  » » 4 weeks ago, # ^ |   0 i dont even know .... just watch some pretest passed guy on the leaderboard... alot of them using bruteforce
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 EDIT: that was about div2 D, sorryIt's more greedy than bruteforce. If there are k people between two people in a couple, they will need to do do at least k swaps in any case. If you start with the couples for which at least one member is close to the left or right end of the line, you will not be adding distance to other couples.
 » 4 weeks ago, # |   -33 Solution for Div2D available ( https://www.geeksforgeeks.org/minimum-number-of-swaps-required-for-arranging-pairs-adjacent-to-each-other/ )And the google query to get to this page was "minimum adjacent swaps to pair same elements".It's ok if there are duplicated ideas, but if they are googlable by such easy keywords it is unfair.Please take care so that it isn't repeated in future rounds.
•  » » 4 weeks ago, # ^ |   +3 That runs in O(2^N) which would TLE since N <= 100
•  » » 4 weeks ago, # ^ |   +6 Not the same problem. In the problem, you can only swap adjacent element rather in the link you can swap any two elements.
•  » » 4 weeks ago, # ^ |   0 I guess that problem's a bit different than Div2 D... here the only swaps allowed are 'Adjacent Swaps' but there swaps between any two positions are allowed.
•  » » 4 weeks ago, # ^ |   +5 Please take care so that it isn't useless comment in future comments.
 » 4 weeks ago, # |   0 My solution for div 2 B: http://codeforces.com/contest/996/submission/39614836 Will it fail?
•  » » 4 weeks ago, # ^ |   0 yep.
 » 4 weeks ago, # |   +9 Even there is several "strange solutions" for many tasks, thank you for great round ! It was really interesting solving this tasks :)
 » 4 weeks ago, # |   +6 Such a surprise, random system testing!
 » 4 weeks ago, # |   0 today many div2 b will be failed
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 test for div2 b : 47 5 6 8// i hope i should hack many sol
•  » » » 4 weeks ago, # ^ |   0 is it 2?
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 or is it 1?
 » 4 weeks ago, # |   +52 Even through my rating will go to hell after this round, and issue with A's difficulty and duplicated C, I enjoyed the problemset. Want to see more round where problems requires creative idea like this one on Codeforces in the future.
 » 4 weeks ago, # | ← Rev. 4 →   +10 Can someone check my div1-F (didnt solve in time though).Let dpn, d be a way to pay a subtree with root in n using a set of d different values. It's rather trivially constructed as If d < n — that's the answer.Otherwise lets construct Ek — number of ways to pay everyone using exactly k values. And finally answer is
•  » » 4 weeks ago, # ^ |   +5 I'm not sure if it's correct, but shouldn't the answer then be ?
•  » » » 4 weeks ago, # ^ |   +10 Yes. Got lost moving from my writings to latex
•  » » » » 4 weeks ago, # ^ |   0 Intuitively the solution looks correct and also lewin's solution is the same. So I guess it's correct.
 » 4 weeks ago, # |   +9 Expert for one day :D rip ratingReally enjoyed the set though :)
 » 4 weeks ago, # | ← Rev. 2 →   +8 Your text to link here...In which hell can these code pass the below test case?7 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
•  » » 4 weeks ago, # ^ |   0 AC with 889ms runtime. The testing computers got faster?
•  » » » 4 weeks ago, # ^ |   0 I think the test case are very lame.
•  » » 4 weeks ago, # ^ |   +7
 » 4 weeks ago, # |   +19 How can a 10^9 solution pass in a sec? This is quite unfair. The simulation takes no thinking and about 2-3 minutes to code and there's no chance of making a mistake. Many people got WA in system testing just trying to do it in the right way. Trying to hack thinking it'll get a TLE and getting "Unsuccessful Hack" is also unfair!
•  » » 4 weeks ago, # ^ |   0 I got 2 unsuccessful hacks due to very fast custom testing computers I guess.
•  » » » 4 weeks ago, # ^ |   +4 Is not this the same surprise that they promised?
•  » » 4 weeks ago, # ^ |   0 it wont be 10^9, if it is a big number then you keep taking 100's and there can be atmost 10^7 of them
•  » » » 4 weeks ago, # ^ |   0 please take a look at the question. :)
•  » » » 4 weeks ago, # ^ |   +4 I am talking about Div2B not A
•  » » 4 weeks ago, # ^ |   0 Interestingly, some of them do fail with a TLE. That's probably not what the writers intended to happen, and it should be taken into account for future rounds.
•  » » » 4 weeks ago, # ^ |   +3 Interestingly this bruteforce submission gives TLE : 39630584 and this passses : 39630937 only difference is that % operator isn't used in the second one.
•  » » » » 4 weeks ago, # ^ |   0 Very interesting, indeed.
 » 4 weeks ago, # |   +117 The difficulty for me: FBDECA.It seems the problems are randomly shuffled for me :/
•  » » 4 weeks ago, # ^ |   +23 Well, you are very good at math, congrats :)F was hard for me, and D wasn't easy.
•  » » 4 weeks ago, # ^ |   0 I bet that F was so so similar to some SRM problem in the past, which also involves the Lagrange interpolation. That's why F is also very easy for me even though I don't remember the exact problem from SRM.
•  » » » 4 weeks ago, # ^ |   +17 I think it's a very classic problem. I have seen tons of similar problems.
 » 4 weeks ago, # |   +19 So I got accepted in E div1 but couldn't find any submission having the same approach.My approach is to go from u to 0 to v. Treat u as a fraction p/q, the operations transform (p,q) to (p-q,q), (p+q,q) or (q,p) which are basically operations of Euclid's algorithm. Then I have to pick some q such that applying Euclid to (q*u%p,q) takes less than 100 steps.I was sure that there are a LOT of q which satisfy the condition, so I chose it randomly. However, can anyone prove it, or at least give a lower bound of number of satisfying q?
 » 4 weeks ago, # |   -7 I somehow managed to get AC on Div2E/Div1C by greedy...
•  » » 4 weeks ago, # ^ |   +3 You should count yourself extremely lucky :/ I iterated from 0 to n — 1 instead and got WA on test 76 :/
•  » » » 4 weeks ago, # ^ |   0 Yea, I knew there were countertests but was counting on them not adding any starting from the back. Very surprised that all of 105 tests were correct
•  » » » » 4 weeks ago, # ^ |   +3 Yep, I think the system tests could be improved further, but I understand this is a hard problem to write tests for.
 » 4 weeks ago, # |   0 Can anyone explain to me why the solution for Div2D is what it is. I cant understand
•  » » 4 weeks ago, # ^ |   +1 I think there is more than one solution. For example i did O(n)
•  » » » 4 weeks ago, # ^ |   0 Can you please explain your solution?
•  » » » » 4 weeks ago, # ^ |   0 O shit sorry. I thought that solved it O(n) but did (n^2) )))0))0))
•  » » » » » 4 weeks ago, # ^ |   0 Did you do something similar to this — http://p.ip.fi/2xsx.I saw tons of code who did something like that. If so can you tell me why its correct? I cant figure it out.
•  » » » » » » 4 weeks ago, # ^ |   0 I did the following.Consider one pair that needs to be connected. I counted distance between them and added it to ans also i counted number of such pairs that one item of pair lies exactly between choosen pair but outer item lies exactly outside choosen pair and added this value to bad. Result is ans - bad / 2. Think this idea can be improved to O(n * log(n)). But i stucked with formal proof. Very naive intuition is that you extract bad because you do such swap only ones but count it twice in ans. My thoughs was based on well-known fact that number of swaps you need to solve permutation is number of inversions
 » 4 weeks ago, # |   0 Can please someone tell me how are the solutions that are counting till a[I]-cnt <0 increasing count by one in each step are not getting tle when hacked ? I had two unsuccessful hacks due to this !! Not fair codeforces !!!
 » 4 weeks ago, # |   +9 "a special surprise which might be happening during system testing"I was really surprised! I have never thought my solution could pass system tests!
 » 4 weeks ago, # |   0 Crazy contest ToT. I am nearly become candidate master :((
 » 4 weeks ago, # |   +2 I think problem Tesla was very hard
 » 4 weeks ago, # |   0 In Div.1 C Div.2 E can two vectors have the same x and y
•  » » 4 weeks ago, # ^ |   +1 Yes , Why not ?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 no i just want to know the answer for n = 100000and all vectors are x = 1 y = 2Edit : after asking ksun48 it showed out that problems are allowed to have multiple answers.
•  » » » » 4 weeks ago, # ^ |   +1 there are many solution one of them is -> 1 -1 1 -1 1 -1 ......
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 thats why I asked this question there is some AC gives only 1 for this test
•  » » 4 weeks ago, # ^ |   +10 in the first example there are two vectors have the same x and y XD
 » 4 weeks ago, # |   +73 http://codeforces.com/blog/entry/58229#comment-419511 — 2nd_places++ (recently also ++'ed on CSA) and still no 1st places anywhere xd
 » 4 weeks ago, # |   +3 Just why geometric when we have a lot of good tags!!??
 » 4 weeks ago, # |   0 Div2 F/Div1 D is the most troll question on all of CF lmao
 » 4 weeks ago, # |   +39 Is the sample explanation for question E wrong?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yeah, we're wrong, it should be 1->2->3. We just fixed it.
 » 4 weeks ago, # | ← Rev. 2 →   0 Can someone prove why this solution passed for Div.2 E? And if not provide a counter case that would disprove this.
 » 4 weeks ago, # |   0 Your crafting.oj.uz ratings are updated!
 » 4 weeks ago, # |   +19 div1B = Swap Pairing
 » 4 weeks ago, # | ← Rev. 2 →   0 EDIT: wrong contest