Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### antontrygubO_o's blog

By antontrygubO_o, 2 months ago, ,

Hello again, Codeforces!

We are glad to invite you to Mathforces Thinkforces Good Bye 2019, which will take place on Dec/29/2019 17:05 (Moscow time).

• Rated for all participants!
• 3 hours!
• There will be an interactive problem in this round. You can read the guide for interactive problems here
• Editorial will be published right after the system testing

All problems in this round were prepared by us, antontrygubO_o and kefaa2. We worked on this round for a long time and tried to make all the problems very interesting. We hope that you will enjoy the round!

We would like to thank:

The number of the problems and point distribution will be announced shortly before the round (or earlier).

Good luck and have fun!

UPD1: Using opportunity, we would like to advertise the match between tourist and Um_nik, which will start in half an hour after this round ends.

UPD2: The last contest of the decade on Codeforces will feature 9 problems .

Score distribution:

500 — 1000 — 1500 — 2000 — 2750 — 3250 — 3750 — 4000 — 4500

UPD3: Editorial

UPD4:

Congratulations to winners:

Announcement of Good Bye 2019

• +1517

 » 2 months ago, # |   +246 You forgot Speedforces, Gapforces and Checker-is-incorrect-forces.
•  » » 2 months ago, # ^ |   +141 One more WeakPretestforces
•  » » 2 months ago, # ^ |   +83 hackforces , one or two times ddosforces
•  » » 2 months ago, # ^ |   +41 Queue-forces too.
•  » » » 2 months ago, # ^ |   0 Smolpp-forces
•  » » 2 months ago, # ^ |   +91 And ComplainingPeopleForces
•  » » 2 months ago, # ^ |   +44 And EditorialLeakedforces
•  » » 2 months ago, # ^ |   +123 And BruteForces
•  » » » 2 months ago, # ^ |   0 SchruteForces
•  » » 2 months ago, # ^ |   -54 And LoverFuckerForces
•  » » 2 months ago, # ^ |   +9 And BestForces
•  » » 2 months ago, # ^ |   +25 And Isitratedforces
•  » » » 2 months ago, # ^ |   +3 Is it rated?
•  » » 2 months ago, # ^ |   0 absolutely hilarious
•  » » 2 months ago, # ^ |   +24 ConstructionForces
 » 2 months ago, # |   -80 is this rated??
•  » » 2 months ago, # ^ |   0 Yope!!!
•  » » 2 months ago, # ^ |   +114 Nah, it doesn't matter because you won't lose your LGM anyway.
 » 2 months ago, # |   +15 No subtasks! This is what already makes the round good
•  » » 2 months ago, # ^ | ← Rev. 2 →   -6 What does it really mean though? Will our solutions be judged with all the testcases during the contest or will they be judged only after the contest is over? I'm deeply sorry for not knowing what a subtask is
•  » » 2 months ago, # ^ |   +12 what is a subtask
•  » » » 2 months ago, # ^ |   +20 Two problems which only differ in the nature of constraints and the score distribution.
 » 2 months ago, # |   +9 Wow, my favorite author is antontrygubO_o. P.S. How I want to see constructive tasks with weak pretests
 » 2 months ago, # |   +292 Are you serious? should a cyan prepare such important contest?
•  » » 2 months ago, # ^ |   +164 Are you serious? Should a cyan complain about a cyan preparing such an important contest?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +87 Are you serious? Should a cyan tell something about a cyan complain about a cyan preparing such an important contest?
•  » » » » 2 months ago, # ^ |   +24 Are you serious? Should a pupil complain about a cyan complain about a cyan complain about a cyan preparing such an important contest?
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   +94 Are you serious? Should... Uh, sorry for bothering you, Mr. Grandmaster.(Edit: Mr. Grandmaster just changed his color just for this comment?)
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   +7 Stack overflow for real cyan!
•  » » » » » » » 2 months ago, # ^ |   +8 Are you serious? Is he a real cyan though? I guess it's time to show off my skills obtained by watching scooby doo since childhood. TIME TO UNMASK
•  » » 2 months ago, # ^ |   -30 Only a newbie can prepare such important contest.
•  » » 2 months ago, # ^ |   +9
•  » » » 2 months ago, # ^ |   -27 hello lance. how are you.
•  » » » » 2 months ago, # ^ |   +16 I'm not lance.
•  » » » » » 2 months ago, # ^ |   -24 no, you are lance. guess who i am!
•  » » » » » » 2 months ago, # ^ |   +13 No I'm not lance. You are a user
•  » » » » » » » 2 months ago, # ^ |   -24 ok, i thought you are lance, as lance one told me that its his account. sorry.
•  » » » 2 months ago, # ^ |   +8 hello mr expert. how are you.
•  » » » » 2 months ago, # ^ |   +18 Yes
•  » » 2 months ago, # ^ |   -26 only the coders with more than 2500 rating should make problems for such great contest
 » 2 months ago, # |   -78 So you advertise your contest by saying problems are not gonna require thinking? Let me grab my HLD and suffix automaton. Or maybe I have even better idea. Skip the contest.
•  » » 2 months ago, # ^ |   +92 Nope, these crossed-out words have the exact opposite meaning :)
•  » » 2 months ago, # ^ |   +21 hello swistakk, why you are grabbing so much. I already told you as you grow older you as not as grabber as in your young days.
•  » » 2 months ago, # ^ |   +112 You shouldn't really. I think he meant the opposite, that their contest will be labeled as "mathforces" by people who can't use their brain and can only press the buttons on their keyboards.Maybe that's only my taste, but previous contests by antontrygubO_o were really good.
•  » » » 2 months ago, # ^ |   +5 hey, what would be the color of your hair in 2020.
•  » » » 2 months ago, # ^ |   +17 Ok, thanks, I see that it indeed could be interpreted in two opposite ways and Radewoosh suggested to us the version I mentioned by writing something like "Ideal description of GoodBye, there will be no stupid thinking, I am so horny now" :P. And when I look at Anton's past problems indeed I think they were good, I really liked C and H from SEERC.
•  » » 2 months ago, # ^ |   +6
 » 2 months ago, # |   -75 3 hrs? will there be 300 problems ? antontrygubO_o
 » 2 months ago, # |   +64 Favorite Authors No subtasks Three hours contests Super-strong testers army Div 1 + 2.
•  » » 2 months ago, # ^ |   -8 9 problems
 » 2 months ago, # |   +7 It looks like no of problems is not ready but editorial is ready :3
•  » » 7 weeks ago, # ^ | ← Rev. 2 →   -32 exactly
•  » » » 7 weeks ago, # ^ |   +16 questions are bad, problems are not
 » 2 months ago, # |   +3 It's a delight to see a specialist posting the announcement. :')
•  » » 2 months ago, # ^ |   +2 It's Santa's magic.
 » 2 months ago, # |   +12 Terrific way to end the decade. 3 contests in a row, just codeforces style.
•  » » 2 months ago, # ^ |   0 100% AGREE.
•  » » 2 months ago, # ^ |   0 why Terrific ?
•  » » 2 months ago, # ^ |   +17 Magnific*
 » 2 months ago, # |   0 2019: Give me your sadness and i'll keep it for you =))
 » 2 months ago, # |   +63 Looking forward to antontrygubO_o's new haircut!
•  » » 2 months ago, # ^ |   0 Legendary problem setter > International grandmaster :)
 » 2 months ago, # |   -16 contest lasted 26 minutes for me
•  » » 2 months ago, # ^ |   -19 feel stupid asf
 » 2 months ago, # |   -13 I hope this year ends well :)
 » 2 months ago, # |   -6 OOOohhh i get it now! it is number line-forces
 » 2 months ago, # | ← Rev. 2 →   -10 Edit: This was meant to be a comment for the Div 3 Contest.$F$ was cool. Here's a fun fact: You can prove that number of trees in $n$ vertices is $n^{n-2}$ if you have a working algorithm for $F$!Your algorithm is deterministic, so it generates exactly one output for each input. Also, as each output corresponds to a unique ordering of edge importance, each output will correspond to exactly one input. But number of different inputs with $n$ vertices $= n^{n-1}$ and number of different outputs $= nT(n)$ where $T(n)$ is number of undirected simple graphs in $n$ vertices which are trees. (We are multiplying by $n$ because same graph with different roots are considered distinct in the output.) Thus, as inputs and outputs have a bijection, $n^{n-1} = nT(n)$. Thus, $T(n) = n^{n-2}$!This is kinda similar to other proofs of Caylee's formula like Prufer Codes and proof of Caylee's formula by double counting.
•  » » 2 months ago, # ^ |   +6 This comment should be posted here.
•  » » 2 months ago, # ^ |   +44 thanks for early editorial
•  » » » 2 months ago, # ^ |   +25 What editorial? Its not a solution. I am just posting a cool fact I thought I should share. And I have clarified on top that I posted this on the wrong thread. :)
 » 2 months ago, # | ← Rev. 4 →   -25 P.S. — This was meant as a comment for the Announcement thread for $611$ Div $3$.I really liked this Div $3$ contest because The difficulty balance was decent. It was not too difficult, yet not too easy. The problems were not very implementation based (like $598$ for example). After getting the basic idea, it was easy to implement it. There were no subtasks A great Div $3$ Contest to end the year !mango_lassi I generally refer your solutions. How to solve $F$ ?
 » 2 months ago, # |   +5 GOODBYE 2019!
 » 2 months ago, # |   +41 A contest to tell goodbye every year. What about a contest to tell goodbye the decade?
 » 2 months ago, # |   +4 It might take a decade to update the ratings! XD
 » 2 months ago, # |   +12 nearly codeforce becomes best site in coders life :D
 » 2 months ago, # |   -7 goodby contests are best
 » 2 months ago, # |   +9 Hope there would be strong tests. I really don't want to be hacked in the last contest of the year
 » 2 months ago, # |   -17 tourist vs Um_nik who will win ?. Enter your suggestion in reply .
 » 2 months ago, # |   -19 can anyone explain why such things are happening on codeforces that : like this blog's author's rating is 2364 and they are showing him as specialist only. This problem is actually there with a lot of users
•  » » 2 months ago, # ^ |   +7 This is codeforces magic :). Just check magic tab in your profile or you can read here here
•  » » » 2 months ago, # ^ |   +1 thanks
•  » » » » 2 months ago, # ^ |   +42 From confused to LGM in 3..2..1..
•  » » 2 months ago, # ^ |   +1 go to your profile and checkout magic section
•  » » » 2 months ago, # ^ |   0 thanks
 » 2 months ago, # | ← Rev. 2 →   -42 D was too nice for me.Couldn't solve it.
 » 2 months ago, # |   +1 Hoping to be expert after this contest.
 » 2 months ago, # |   +1 9 problems :o I love it!
•  » » 2 months ago, # ^ |   +18 I don't like it. Let's go back to good old days with 7 problems :(
•  » » » 2 months ago, # ^ |   0 Well, I like the fact that you have to find yourself in every possible category to perform really well and can always find something for yourself if you just want to perform well. Also, it's good when the speed matters.
•  » » » » 2 months ago, # ^ |   +14 I think it's better to have more time spent on individual problems because that means we can solve tougher problems for oneself. Of course, different round setters may have different ideas :)
•  » » » » 2 months ago, # ^ |   0 I think you love it because you become the first with it! Congratulations!
•  » » 2 months ago, # ^ |   +9 I didn't participate partially because there are so many problems. [you] can always find something for yourself The number of interesting hard problems doesn't really increase if they use more of those easy and medium problems. IOI has 3 problems for 5 hours, ICPC has 12 problems for 15 hours (kind of). That's a lot of time to think about solutions. Doing well in a 9-problem CF round means that you likely spend at most 2-3 minutes of thinking on each of maybe 6 problems. Yay, so much fun.
 » 2 months ago, # |   +27 4500 points! Is this the highest ever score?
 » 2 months ago, # |   +24 I think hacking will be so hard this round because of the magic :\
 » 2 months ago, # |   0 13k+ registration. I hope all works fine during contests.
•  » » 2 months ago, # ^ |   0 Yeah, and for 3 hours...I really hope the servers will sustain the pressure...
•  » » » 2 months ago, # ^ |   +7 contest finished with no trouble
 » 2 months ago, # |   +44 Best of Luck to Servers as well.
 » 2 months ago, # |   0 speedforces strikes again
 » 2 months ago, # |   +39 syrian goverment be like : oh there's a cool round what a great time to shutdown electricity
 » 2 months ago, # |   0 May 2020 will be the year of high ratings for the hard workers.
 » 2 months ago, # |   0 MultipleAnswerForces
 » 2 months ago, # |   +15 Interactive killed me
 » 2 months ago, # |   +4 I have sent my solution for B from the main website, and after about half a minute of page loading I got 502 Bad gateway :( Since my submission did not appear on m2.codeforces.com, I submitted the same code from there, and — hooray! — both of my submissions appear Accepted, but I got 50 points penalty for resubmission. The codes are exactly the same, arsijo could you please take a look at it? Thanks.P.S. Great contest by the way, nice thinking problems, and seems to be very well balanced!
•  » » 2 months ago, # ^ |   +13 One of your submissions was ignored.
•  » » » 2 months ago, # ^ |   0 Thanks!
•  » » 2 months ago, # ^ |   0 Same, but I got runtime error.
 » 2 months ago, # |   +73 ConstructiveForces
 » 2 months ago, # |   +38 Solution to C :Let's define s as the sum of a1 to am, and x as the xor of a1 to am. Append x to the array. Now the sum of (m+1) elements is s+x, and the xor of (m+1) elements is 0. And append s+x to the array. Now the sum of (m+2) elements is 2(s+x), and the xor of (m+2) elements is s+x. So the array becomes good.In short, for any cases,2x s+xcan be the answer.
•  » » 2 months ago, # ^ |   0 How you came up with this solution?
•  » » » 2 months ago, # ^ |   0 I put a pen on a piece of paper and found out in half an hour.
 » 2 months ago, # |   +50 Jesus. This round was so fuckin good. The best in my entire life.
 » 2 months ago, # |   -24 My solutions:
•  » » 2 months ago, # ^ |   0
•  » » 2 months ago, # ^ |   0 Can you explain solution B in test case 1 3 2 4 5?
•  » » » 2 months ago, # ^ |   0 Answer for this test is yes (segment from 1 to 2) because 3-1>=2
•  » » » » 2 months ago, # ^ |   0 Will k change when we change size of array? I thought k was always = n @@
•  » » » » » 2 months ago, # ^ |   0 k is the size of the subarray.
•  » » » » » » 2 months ago, # ^ |   0 I didnt understand the chal :(((( Im so baddddd
•  » » 2 months ago, # ^ |   0 Can you prove your solution for B?
 » 2 months ago, # |   0 How to solve D?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +35 pick k+1 elements ask every subset of k elements. Count the times of the minimum number appears. The answer is k+1 — times .
•  » » » 2 months ago, # ^ |   0 Please explain the logic behind it too.
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +11 if m = 1 it will be the minimum if it existif m = 2 2nd smallest will be 2nd smallest if both 1 and 2 existif m = 3 3rd smallest will be 3rd smallest if both 1 and 2 and 3 exist........
•  » » » » » 2 months ago, # ^ |   0 Understood. Amazing solution!!
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +13 Ugh, now thanks to your comment the task seems super easy and my idea super ugly. Ugly idea0) Notice, that result of query can never be among first (smallest) m-1 and last (biggest) k-m of unknown array a.1) If k==1 return 12) n-(k-1) times do the following: query k positions, elements in which we don't know yet (a[i]==-1). When you receive (pos, a_pos) update a[pos]=a_pos; (initially all a[i]=-1). In each query we are guaranteed to get some (yet unknown) new element of a.3) Now we're left with k-1 unknown elements (m-1 smallest and k-m biggest of a), and n-(k-1) >= 2 known elements. Suppose 2 smallest known elements in a are a[posA]
 » 2 months ago, # |   0 How to solve C?
•  » » 2 months ago, # ^ |   +9 Print x,s+x
•  » » » 2 months ago, # ^ |   0 And what's x?
•  » » » » 2 months ago, # ^ |   0 xor of all elements.s is sum.
•  » » 2 months ago, # ^ | ← Rev. 4 →   -22 for _ in range(int(input())): am = int(input()) arr = list(map(int,input().split())) add = 0 xor = 0 used = [] for i in range(am): add+=arr[i] if i == 0: xor = arr[i] else: xor ^= arr[i] if add == 2*xor: print(0) print("") else: used.append(xor) add += xor used.append(add) print(len(used)) print(*used) Tell me, if u still don't understand it
•  » » » 2 months ago, # ^ |   0 Can you please explain the logic behind your code?
•  » » » » 2 months ago, # ^ | ← Rev. 4 →   +1 First you add Xor value to makeits value zero then you add Xor+Sum Its something like this:Sum XorSum+Xor 02(Sum+Xor) Sum+Xor
•  » » » » 2 months ago, # ^ |   +5 Let's say you have T where you calculate xor sum and S where you calculate normal sum.Now we add T and we obtain T xor T which is always 0 and S + T in normal sum.If we now add S + T, we obtain 0 xor (S + T) which is S + T always, and 2 * (S + T) in S.
 » 2 months ago, # | ← Rev. 2 →   +100 Congratulations to the organizers/writers of the contest. As far as I can remember, this is the best codeforces contest I have participated in.
 » 2 months ago, # |   +64 Goodbye 2019 and Goodbye ratings. (Great contest btw!)
 » 2 months ago, # |   +41 It's neither Mathforces nor thinkforces.It's Construct-forces :/Problems are fantastic, but maybe I should say goodbye to both 2019 and my rating.
 » 2 months ago, # | ← Rev. 2 →   +96 How did 88 people solve a problem tourist couldn't in 2 hours 30 minutes??EDIT: looks like lots of heuristic solutions passed :(
•  » » 2 months ago, # ^ |   -48 may be the solution requires creative thinking.
•  » » 2 months ago, # ^ |   +33 tourist got a call from his angry girlfriend that he never cares abt her....
 » 2 months ago, # |   0 Good bye 2019 and Radewoosh is on the way taking 1st place from Tourist. what an ending year!
 » 2 months ago, # |   0 Congrats to Radewoosh, first place at context, first place at top
 » 2 months ago, # | ← Rev. 2 →   +18 Really nice problems, I especially loved C, E, G.When I was fixed a bug in H, I switched to Chrome and a wild "Round has finished" pop-up has appeared. I hope it would have failed anyway :-)
•  » » 2 months ago, # ^ |   0 What is your solution to E?
•  » » » 2 months ago, # ^ |   +3 Split the points by the parity of $x_i + y_i$. If this is not a valid split, move all the points $1$ to the left if their parity is odd, to ensure it is even.Then, split the points by the parity of $x_i$. If this is not a valid split, move all the points to $1$ to the left and $1$ up if the parity is odd. Then, all coordinates are even. Divide them by two and repeat the whole process.Proof by AC.
 » 2 months ago, # |   +151 HI'm an author...
•  » » 2 months ago, # ^ |   +49 Notorious coincidence
•  » » 2 months ago, # ^ |   0 For me it's not swapping but shifting an array. I can solve first but not second. How to reduce to swapping?
•  » » » 2 months ago, # ^ |   +20 Well, not reducing, but you can notice that for sorted (by value) array of positions it's enough to for every two neighboring positions $a$ and $b$ to prohibit cuts on segment $[a, b]$ (if $a •  » » » » 2 months ago, # ^ | +2 Oh wow. Very nice criteria. That makes me sad..  » 2 months ago, # | +32 How to solve E? •  » » 2 months ago, # ^ | +39 Observe that if two points with different parities of$x + y$exist, then we can just partition the initial point set into points whose$x + y$is odd and points whose$x + y$is even. Otherwise, assume all sums$x + y$are even (other case is similar) and transform all points so that$(x, y) \mapsto (\frac{x + y}{2}, \frac{x - y}{2})$. This preserves equality of distances and halves the maximum of$x^2 + y^2$, so we can just repeat this process until we get a solution (note that this has to happen since the input points are distinct). •  » » » 2 months ago, # ^ | +1 Thanks for the solution. I am not sure what'll happen when we have a points on a square. (1, 1), (1, -1), (-1, 1), (-1, -1). It'll transform to (1, 0), (0, 1), (-1, 0), (0, -1). And then? In the next step all will become (0, 0). •  » » » » 2 months ago, # ^ | +1 if$x+y$is odd, points will be shifted to the left by one first. •  » » » » 2 months ago, # ^ | ← Rev. 2 → 0 To understand what the transformation does, draw some points with same parity of$x+y$on a paper, then rotate the paper$45$degrees. •  » » 2 months ago, # ^ | +13 0) Move all points, so that (x0, y0) is at origin: Pi=(xi,yi)=(xi, yi)-(x0,y0);1) Let t(a) in {0, 1} be the group of a-th point (We can restore group A uniquely using t(0), ... t(N-1)2) Consider quadruples of points (a, b) (c, d) such that |a,b|==|c, d|. Using our array t this becomes t(a) xor t(b) == t(c) xor t(d)3) Define parity of i-th point as (xi+yi)%23.0) If parity of all points is 0 (we must have at least 1 (0-th point) with this parity).3.0.0) All points have xi%2==yi%2==0. Then solve same task for "scaled down" version of this problem (xi/2, yi/2).3.0.1) There's at least one point with (xi%2, yi%2)==(1, 1). Then answer: t(i) = x(i)3.1) Parity of some point is 1. Then, assign t(i) = (xi+yi)%2.4) Why this works? For step 3.1. consider mod 2: (xa-xb)^2+(ya-yb)^2 == (xa+ya) + (xb+yb) = (ta ^ tb)%2 For step 3.0.1 consider mod 4: * distance between (0,0)<-->(0,0) and (1, 1)<-->(1,1) is 0 (mod 4) * distance between (0,0)<-->(1,1) is 2 (mod 4) •  » » » 2 months ago, # ^ | +10 Thanks for the nice explanation of a super nice solution. Could you please tell me, how did you come up with the idea of using parity of x+y? Did you guess randomly and then peoved, or did you make some observation? •  » » » » 2 months ago, # ^ | +6 At first, I was surprised this can always be done, so I thought about the case where$y = 0$and$x = 0, 1, 2, \dots$— this seemed to work well with parity (and in no other easy to spot ways). I recalled when I solved a problem using a checkerboard coloring, so I then did the algebra (as shown by A_Le_K above) and concluded this should be the way to proceed.  » 2 months ago, # | +221 My soln of G -If 0 exists print it.Else replace ai by i-aiNow we have to find a subset of vertex such that ai+aj+ak+...=i+j+k+....Since all elements are in range 1....n there exists a cycle in it.Find it and print it. •  » » 2 months ago, # ^ | +5 wow, great. •  » » 2 months ago, # ^ | 0 How did you find that subset, which cycle you are talking about •  » » » 2 months ago, # ^ | +3 Permutation cycle.Basically find a permutation such that ai=j,aj=k,...., a_=i.Another way round create a directed graph with edges i -> ai. Find a cycle in this graph, and it can be proven that there exists a cycle in it. •  » » » » 2 months ago, # ^ | 0 Oh got it, Amazing idea •  » » 2 months ago, # ^ | +207 HOWRUSOGOOD?? •  » » 2 months ago, # ^ | +3 Damn that is smart. I spent half the competition on G but no luck. •  » » 2 months ago, # ^ | +8 omg so beautiful •  » » » 2 months ago, # ^ | 0 can anyone explain B as TLE in my case ??  » 2 months ago, # | 0 Didn't like D. Read the statement multiple times, but there was no mention of printing query in sorted manner, which caused WA. •  » » 2 months ago, # ^ | +1 how to solve D? •  » » » 2 months ago, # ^ | +13 Keep querying for$k$undiscovered elements at random ( you can do this$n-k+1$times ). If at any point you already have discovered$k$points, you can print answer then and there by querying those points.Otherwise, you have$n-k+1$points discovered with$k-1$points undiscovered ( and$n-k+1
•  » » 2 months ago, # ^ |   +14 My queries are not in order, but I got accepted?
•  » » » 2 months ago, # ^ |   -18 The only change between 67912676 and 67920459 is that I put the final query in a set ( i.e. which sorted it ). Difference in submission here.
•  » » » » 2 months ago, # ^ |   +26 Maybe you printed some equal numbers.
•  » » » » » 2 months ago, # ^ |   0 Looks like that is the only possibility, according to others' replies. Will see what case it failed on.
•  » » » » 7 weeks ago, # ^ |   0 Silly error! Forgot to put spaces in query originally.
•  » » 2 months ago, # ^ |   +16 My queries are definitely not sorted, did not seem to be a problem o_O
 » 2 months ago, # |   +1 What a terrible page error...
•  » » 2 months ago, # ^ |   +14 Scared the crap out of me too
•  » » » 2 months ago, # ^ |   0 Sale of detergent has spiked due to sudden craps in 13k pants
•  » » 2 months ago, # ^ |   0 How do you see the triangle column(rating change column) during contest
•  » » » 2 months ago, # ^ |   0 It's because of the extension program.
•  » » » 2 months ago, # ^ |   +11
 » 2 months ago, # |   +38 was it just me or anyone else who waited for an epic finish by tourist..?
•  » » 2 months ago, # ^ |   0 i too.. waiting for his submission for I.
 » 2 months ago, # |   +13 How to solve D
 » 2 months ago, # |   +71 How to check if integer is odd?Normal people: x % 2 != 0 0 msSmart people: x & 1 0 msMe: x % 2 == 1 25 min
 » 2 months ago, # |   +15 I hope there are some strong tests in G to fail stupid solutions (including mine), aren't they?
•  » » 2 months ago, # ^ |   +18 What's your stupid solution? I tried but didn't manage to pass pretests with wrong greedies.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I coded two different approaches. First one is shuffle numbers randomly in 100 random ways and check all subsegments, second one was some hill climbing. Hill climbing alone was not sufficient, but together with first one it was (maybe hill climbing wasn't executed even once on pretests, I don't know).EDIT: Indeed, shuffling (+1 check on sorted) and checking subsegments was enough to get AC.
•  » » 2 months ago, # ^ |   0 It seems that all stupid approaches sucessfully pass systests :<. So sad.
•  » » » 2 months ago, # ^ |   +8 I wonder if there is a way to prove that they are always going to work by demonstrating some nice lower bound on success probability; alternatively, what would be the test to break random_shuffle.(I also tried my best thinking about holes and pigeons, but didn't succeed on recalling how this one is supposed to be solved, so I ended up doing random shuffle too)
•  » » » » 2 months ago, # ^ |   0 $-N, (N-1), 1, 1, 1, \ldots$I think this will only succeed in probability $\frac{1}{N}$, since two large values should be close. So I added sorting by absolute value, but I'm pretty sure there is still a countercase.
 » 2 months ago, # |   -8 can anyone explain B as TLE in my case ??
•  » » 2 months ago, # ^ |   +1 We can prove that if there's two consecutive elements with difference > 1 output the index of the two elements else there's no solution.
•  » » » 2 months ago, # ^ |   0 do you mean to consider only subarray of size 2 ??
•  » » » » 2 months ago, # ^ |   0 Yes
•  » » 2 months ago, # ^ |   0 Just find if there exists two consecutive elements with difference >=2
 » 2 months ago, # |   +24 Best contest that I participated, so far. Thank you, antontrygubO_o and kefaa2! : ) . Happy to end this wonderful year with a beautiful contest, thank you Codeforces team as well!
 » 2 months ago, # | ← Rev. 2 →   +3 7 out of 9 problems with tag "math".I like Mathforces
•  » » 2 months ago, # ^ |   -11 LOL.
 » 2 months ago, # |   0 67929171 why it takes wa? Can you tell me the test?
 » 2 months ago, # | ← Rev. 3 →   +357
•  » » 2 months ago, # ^ |   +4 thank you for explaining its meaning for me
 » 2 months ago, # |   +5 Was not able to see the simplicity in B and C :/
•  » » 2 months ago, # ^ |   +2 Yeah, goodbye ratings.
 » 2 months ago, # |   +2 Who is waiting for the stream to start?
 » 2 months ago, # |   +105 F and H can be, but the rest... Don't do such CF rounds... Ad hoc problems are OK individually, I liked each of your problems, but not a whole contest made up of them. How would you feel with 9 geometries or number theories? Already AtCoder doesn't make normal contests and uses only ad hocs, let CF stay normal.
•  » » 2 months ago, # ^ |   +128 It's not like everybody thinks some sqrt decompositions and data structures are only "normal" tasks. I like original tasks and your normal is my definition of boring. I came here to think not to code and problem DEG were much more fun than FH.
•  » » » 2 months ago, # ^ |   -7 I also don't like doing the same all the time, F and H are different from each other. There are soooo many topics... Not only ad hocs and the rest...
•  » » » » 2 months ago, # ^ |   +11 Yes, cause D, E and G were so similar, they almost felt like doing the same problem. /sIt is not like problems can be partitioned into "sqrt decompositions", "data structures" and "other" and all problems within "other" category are similar.
•  » » » » » 2 months ago, # ^ |   +8 You have to try random options without knowing if they lead anywhere in these problems. Also, it's somehow random if you figure it out or not.
•  » » » » » » 2 months ago, # ^ |   +22 Yeah, sure. Completely random.
•  » » » » » » » 2 months ago, # ^ |   +8 Don't you agree that F and H are definitely more deterministic?
•  » » » » » » » » 2 months ago, # ^ |   +31 Sure they are, cause they are standard and boring. And now go to IMO where no hard problems are standard and tell all the USA and China teams that these problems require nonstandard thinking so they are random cause "you either get the good idea or not" and all their participants are just lucky every year.
•  » » » » » » » » » 2 months ago, # ^ |   +16 It's programming competition, not math competition... And before you say something, I'm not saying that these problems are bad on CF, but there were a bunch of them. Why are you even competing in programming competitions if you expect only doing math/proving stuff?
•  » » » » » » » » » 2 months ago, # ^ |   +6 Everytime somebody says "this is programming competition, not math competition" a kitten somewhere in this world dies. Do not do that. I do not expect math problems only, but problems requiring good amount of thinking are much more fun. Why don't you go to the industry if you love coding and hate all kinds of thinking?
•  » » » » » » » » » 2 months ago, # ^ |   +63 Don't focus on what's fun for you, AtCoder already makes unbalanced contest because they are "fun".
•  » » » » » » » » » 2 months ago, # ^ |   -23 "It's programming competition, not math competition..." said no one ICPC world champion ever :D
•  » » » » » » » » » 2 months ago, # ^ |   +18 Didn't read a single comment from the thread beside yours.It's programming competition, not math competition...
•  » » » » » » » » » 2 months ago, # ^ |   -18 Well, now my comment is invalid, so sad :(
•  » » » » » » » 2 months ago, # ^ |   +19 Also, we aren't here to do math only...
•  » » » » » » » » 2 months ago, # ^ |   -21 So you got two coding-heavy standard problems. Do you really feel overwhelmed by E and G and think it is beyond what is reasonable to put them in one contest? Or is the problem D the one that causes amount of thinking to overflow for you?
•  » » » » » » » » » 2 months ago, # ^ |   -9 They weren't coding-heavy, they were easy as shit to implement if you KNOW HOW TO SOLVE THEM PROPERLY... See? You also have to know how to solve them and how to implement them as quickly as possible. That's your problem, you think that the only skill is coming up with the solutions, but there are so many side's of competing in contests and each of them has to be developed independently. That's why programming is a way better than math.To DEG, how would you feel with 3 problems, one for centroids, one for HLD and one for some jump-pointers? I'd feel great, but I know that contests should be balanced and unfortunately this one wasn't enough...
•  » » » » » » » » » 2 months ago, # ^ |   +12 In my opinion even the skill to know when you can try to squeeze too slow solution or when to try some random shit is important in contests. Unfortunately, even if the problemsetter has great math/coming-up-with-solutions/inventing-new-algorithms skill, then if he doesn't have PROBLEM-SOLVING(yes, it's definitely different than coming up with the solutions/coding)/competing skill the contest won't be prepared perfectly, what we can see in G's testset.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +20 Also, tests look poor... I wanted to hack someone's G with a test good enough to make people fail but to which my solution is immune, but there were no Gs in my room...
 » 2 months ago, # | ← Rev. 2 →   -25 I think F and H is hard-coding but not hard-thinking Edit: It's wrong
•  » » 2 months ago, # ^ |   0 According to this comment, you are wrong about H.
•  » » » 2 months ago, # ^ |   0 There are some mistakes when I read statement :'(
 » 2 months ago, # |   +356
 » 2 months ago, # | ← Rev. 2 →   +38
 » 2 months ago, # |   +6 Goodbye 2019, we'll go in a new decade!
 » 2 months ago, # |   +2 F is definitely easier than D and E for me. I don't even know how to prove my solution for E and my frustrating attempt somehow passed pretests...
•  » » 2 months ago, # ^ |   +8 I would say it is much more standard: one may skip problem statement and only read constraints, and that would be enough to guess that we are asked to do some sqrt decomposition.Both D and E are in ad hoc land :) I wouldn't go as far as saying that they are harder than F, but they are much less standard to me.
 » 2 months ago, # |   0 How to solve B?
•  » » 2 months ago, # ^ |   0 Check above comments.
•  » » 2 months ago, # ^ |   +5 Consider only subarrays of size 2.
•  » » » 2 months ago, # ^ |   0 Thank u..
•  » » 2 months ago, # ^ |   0 if the difference in absolute value of some adiacent integers si greater than 2 the answer is "YES"; Otherwise is "NO"
•  » » » 2 months ago, # ^ |   0 Thank u..
•  » » 2 months ago, # ^ |   0 can you explain the logic please?
•  » » » 2 months ago, # ^ |   0 if you have adiacent values in the array the distance k is 1 and if the difference is >=2 then the answer is "YES" because 2>1 If there isn't anything with the difference greater than 2 than the elements are consecutive for example 2 3 4 3 2 and you can't have the answer "YES"\If the answer is "YES" print i and i-1 where abs(v[i]-v[i-1])>=2
•  » » » » 2 months ago, # ^ |   0 when I realized what u said, i have submited 3 times for stupid solution :(
 » 2 months ago, # |   0 why am i not able to access others code even after the contest is ended??
 » 2 months ago, # |   -7 Well this was pretty interesting. I didn't quite enjoy the round, but i also didn't hate it. Problem D as interactive is a big mistake IMO, since problem D is the one that usually is the barrier between easy and harder problems for most people. It was only a matter of finding the idea (which is what i don't like about interactive problems too much). It's like solving a riddle, not a true CP problem. I think it being problem G or H or even an easy problem B (to introduce some people to this concept) would have been a better idea.
 » 2 months ago, # |   0 Happy new codeforces' contest full of cheats *_*
 » 2 months ago, # |   +1 Arterm ksun48 any idea why I works? I just wrote something which looks enough randomly and strange to be the hardest solution on this contest, having no idea if it calculates anything what makes sense...
•  » » 2 months ago, # ^ | ← Rev. 4 →   +38 First assume all cells are 0 or 1. We work mod $2, x^{2^k}-1, y^{2^k}-1$ and consider polynomials in two variables, where cell $i,j$ represents the polynomial $x^iy^j$. The input polynomial is some polynomial $S(x,y)$, and we'd like to invert the polynomial, to find some $T(x,y)$ with $T(x,y)S(x,y) = x^iy^j$ mod $2, x^{2^k}-1, y^{2^k}-1$.Since $(P(x,y) + Q(x,y))^{2^a} \equiv P(x,y)^{2^a} + Q(x,y)^{2^a}$ mod 2, this tells us that $P(x,y)^{2^a} = P(x^{2^a}, y^{2^a})$. $P(x,y)^{2^k} = P(x^{2^k}, y^{2^k}) = P(1,1) = 1$ (as $t$ is odd).In particular the inverse of $P(x,y)$ is $P(x,y)^{2^k-1} = P(x,y)P(x^2,y^2)\dots P(x^{2^{k-1}}y^{2^{k-1}})$. Furthermore, $P(x^a,y^a)$ is also a figure with $t$ cells as it has $t$ terms, so we can multiply by this polynomial in time $O(tk 2^{2k})$.
 » 2 months ago, # |   +4 when could we see others solutions?
 » 2 months ago, # |   0 Problem C: -> s = sum of all Ai -> x = xor of all Ai if you add x to the array -> now the sum is s + x and the xor is 0 (x xor x = 0) after that you add s + x to the new array -> the sum is s + x + s + x and the xor is s + x ( a xor 0 = a )
 » 2 months ago, # | ← Rev. 2 →   -12 Hello Guys seriously I am afraid from joining live contests because I am not trusting myself and I couldn't find such a good plan for training or practicing that fitting my constrains to be experienced with problems and solve them regularly, is there an advice for me and others who are the same ?! I talk with honesty please don't gimme negative feedback because it's a real problem I am crossing over. Thanks in advance.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Create a new account and start joining live contests. and when you start felling that you're doing well you can start with your main account.
 » 2 months ago, # |   +16
 » 2 months ago, # |   +58
 » 2 months ago, # |   +28 GH is very cool. Kudos to author
 » 2 months ago, # |   +44 How would one natually come up with the solution of G? It seems very hard to come up with the thinking process that would get you to find it.
•  » » 2 months ago, # ^ |   +24 Well, this is a common technique in mathematics competition.
•  » » » 2 months ago, # ^ |   +12 Emmm, what is exactly common here? It's beautiful idea but I don't think I can name anything here as "_some name/word_ technique".
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +23 "Beautiful"? Solving this problem involves nothing but decoding an extremely contrived statement (I can tell as somebody who solved it and never turned the brain on during doing so). (I am too lazy to explain my "thinking process", because yuhoooo already did it below pretty well.)
•  » » » » » 2 months ago, # ^ |   +15 "Solving this problem involves nothing but decoding an extremely contrived statement" — what the fuck?
•  » » » » » » 2 months ago, # ^ |   +16 Do you agree that the problem is very easy after restating it in the following way: we are given $n$ integers $p_1$, $p_2$, $\ldots$, $p_n$, all between $1$ and $n$, find a non-empty subset $S$ of ${1, 2, \ldots, n}$, such that $\sum\limits_{i \in S} (i - p_i) = 0$ (at the very least, I very much suspect that the problem is not original when stated this way)?If no, then I am sorry. If yes, then I say that the only difference between this and the original problem is getting rid of a contrived statement $i - n \leqslant a_i \leqslant i - 1$ and replacing it with a more natural $1 \leqslant p_i \leqslant n$ for $p_i = i - a_i$.
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   +18 https://codeforces.com/gym/100239/problem/B Here you areYou can see that a lot of contestants solved it in 20 minutes
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   +10 I totally agree with you, the solution is obvious due to the unnatural restrictions. I have a similar but more elegant problem from a math competition several years ago:There are $2^n$ distinct $n$-dimensional $\pm 1$ vectors initially, some of the components of some vectors are changed to $0$. Please find a nonempty set $S$ of vectors such that the sum of $S$ is zero.Solution: if a vector $v_1$ is changed to $v_2$, then we can consider $v_2$ to be $(v_1 - v_3) / 2$ Notice that $v_3$ will be a $n$-dimensional $\pm 1$ vector, the rest is trivial.
•  » » » » » 2 months ago, # ^ |   +61 I mean, what, that's a very big difference. For me, it was about having one number in range [-4, -3, -2, -1, 0], [-3, -2, -1, 0, 1], [-2, -1, 0, 1, 2], [-1, 0, 1, 2, 3], [0, 1, 2, 3, 4]. What isn't natural about this statement? It looks symmetric, looks reasonable, it's not at all obvious to me there needs to be a different restatement of the problem to solve it. A case such as -2, -2, -2, 3, 3 looks pretty natural under the original statement, and the given formulation suggests.If it's contrived, it means it should be easy to see through, or at least see that there needs to be a different restatement. But so many contestants didn't solve it.Just because you didn't spend much time on it doesn't mean you didn't turn your brain on to solve it. It's an idea you came up with, to subtract the i to the other side. Tons of strong contestants can't come up with that idea, and when I learned the solution after, I don't feel tricked, I feel that I just wasn't able to come up with that good idea.
•  » » » » » » 2 months ago, # ^ |   +10 I agree. For me, during the whole time I spent trying to solve it I was picturing "sliding windows" of size n as intervals and, for me, it didn't feel unnatural at all, and I didn't feel the need to restate it in some other way. I guess it's one of those things that for some people it's very easy to come up with the good way of approaching this particular problem, and it might make it seem very obvious,
•  » » » » » » 2 months ago, # ^ |   0 Exactly my thoughts. Maybe $i-n \le a_i \le i-1$ doesn't look encouraging, but if you picture it as sliding windows it looks very nice. After reformulating it indeed looks even nicer, but as you and retrograd said as well, I didn't feel the need to look for reformulation since it already looked natural to me (it seems that of course I should have, however it could have been solved even without restating it as VadymKa explained below).
•  » » 2 months ago, # ^ |   +10 You should somehow use weird condition $i-n\leq a_i \leq i-1$, it's much more nice to write this as $1\leq i-a_i\leq n$. After this one way to solve is to define new array $b_i=i-a_i$ and writing $sum=0$ condition for this array, which is $b_{i_1}+\cdots+b_{i_k}=i_1+\cdots+i_k$ and after this it's pretty easy to come up with cycle solution.
•  » » 2 months ago, # ^ |   +13 There is also a solution by induction by Marcin_smu. He claims you can reduce problem for n to problem for n-1 by either removing maximum or removing minimum or removing both of them and adding their sum. Induction was kind of natural way of thinking here, but I couldn't make it work either.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I guess it's quite easy to come up with the following solution: Consider some permutation of the initial array. In case we have two equal prefix sums, we also have a zero-sum subset (this idea is smth quite standard). Well, now it's enough to select a's one by one in a way that the current sum is between 1 and n — 1.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 "Well, now it's enough to select a's one by one in a way that the current sum is between 1 and n — 1." — but you can't really do that.
•  » » » » » 2 months ago, # ^ |   +13 Let's imagine that array values are actually hidden from us. If the current sum is k, then you need to select the next number from range [-k, n — 1 — k]. Instead of picking an arbitrary one, just go for a[n — k — 1]. If it's not available, you already have two equal prefix sums. It's in some sense identical to the solution from editorial, but this one explains some intuition behind the constructed graph.
•  » » » » » » 2 months ago, # ^ |   +20 Wow, that is great! Too bad I thought about exactly that solution but missed final conclusion "If it's not available, you already have two equal prefix sums."
•  » » » » 2 months ago, # ^ |   0 What happens if you have only one or two positive numbers and the rest are negative?
•  » » » 2 months ago, # ^ |   0 I also tried to work it out using induction, without much success.
 » 2 months ago, # |   +27 Why can't I see other's submissions? The contest ended quite a while ago!
 » 2 months ago, # |   +51 G is a beautiful problem, but did you even consider killing heuristic solutions -.-? I'll tell you what, random tests are not sufficient in such problems. Simple test that ko_osaga posted already cause my accepted solution to fail and probably a lot of accepted solutions from contest as well. I think if somebody thinks a bit more on tests then he can come up with tests that will fail almost all, if not all, heuristic solutions. It's obvious from the very start that this is "heuristicable" problem and creating strong tests, coming up with many heuristic and ensuring they do not pass is very important.
•  » » 2 months ago, # ^ |   +20 We tried to cut heuristics and to come up with specific tests :c . Best tests we came up with were tests of the form:Fix some $i$ such that $gcd(i, n) = 1$. Take $a_j = i-n$ for $1\le j\le i$, $a_{i+1}$ is any valid number, $a_j = i$ for $i+2\le j \le n$. It can easily be seen that these kind of tests have only one subset with sum $0$.We added such tests, but, unfortunately, this wasn't enough. We are sorry for this and hope that you still enjoyed the round!
•  » » » 2 months ago, # ^ |   +13 Wow, it seems that vast majority of people actually got legit solutions. I was convinced it must have been the case that 80% of ACs are some random shit and just a small portion of them are provable, but it seems it is the other way around.
 » 2 months ago, # | ← Rev. 2 →   +18 I really like these problems. They are short and easy to understand.
 » 2 months ago, # |   +35 Why can't we view others' codes?
•  » » 2 months ago, # ^ |   +5
•  » » 2 months ago, # ^ |   +3 Even testcases
 » 2 months ago, # |   0 Thanks to the kefaa2, antontrygubO_o for this round. For me, this is the best round for 2019
 » 2 months ago, # |   +14 Can submissions be made public? The contest has been over for some time now.
 » 2 months ago, # | ← Rev. 2 →   +8 Is it intentional that I you can't see other people's submissions from this round?
 » 2 months ago, # |   0 Can you please open visibility all solutions?
 » 2 months ago, # |   +16 I got disqualified from the contest and got a message saying that my solution for problem E coincides with the solution of gamegame. It must be some kind of mistake since I didn't copy any code from another place. (I can not see the other solution yet to compare anyway) Can anything be done about that?
•  » » 2 months ago, # ^ |   +3 I can confirm that I didn't giveaway my solution and its not quite possible to steal, as I compile with my Dev-C++ locally (not ideone). I think its is a coincidence
•  » » » 2 months ago, # ^ |   +3 Notorious coincidence? Problem C too?
 » 2 months ago, # |   +10 is it normal that other people's submissions are locked ?
 » 2 months ago, # | ← Rev. 2 →   +18 socketnaut and I were discussing 1270E - Divide Points, and tried to uphack our solutions, but got "Unexpected Verdict", so we think something is wrong with the judge/checker.We used the test case 4 524288 0 -524288 0 0 524288 0 -524288 (the same as the second sample, just scaled up by a large power of 2)Using custom invocation, socketnaut's submission (67907624) has no output for this input, and mine (67906687) outputs a correct answer, but both receive "Unexpected Verdict" (instead of "(Un)successful Hacking Attempt").Is it possible to fix the judge/checker?
•  » » 7 weeks ago, # ^ |   +3 looks like the checker has been fixed, thanks!
 » 2 months ago, # | ← Rev. 2 →   0 67939710 Why no TLE in B...? I found solve idea aleady but It's solution can be O(10000 * 2 * 10^5) so I assumed B is need O(nlogn) solution to solve...
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 @nicotina04 I fixed your submission by modifying the if-statement to new this : abs(table[j] — table[j — 1]) >= 2) ///not > 1
 » 2 months ago, # |   +29 I'm curious how can people read problems so fast and submit so fast. For example tourist, he read problem A and B and solved them under 2minutes 59seconds. and then he went directly to problem E and he solved it in minute 7. which means he thought and coded it in 4 minutes.Do people who are this fast, skim through all problems and find the easiest in their mind and then implement it ? like personally just reading A took me a whole 2 minutes
•  » » 2 months ago, # ^ |   0 Same question
•  » » 2 months ago, # ^ |   -13 And he couldn't solve G, H and I...
•  » » » 7 weeks ago, # ^ |   +16 And you also
•  » » » » 7 weeks ago, # ^ |   -8 There's a huge difference be me and tourist, then there's no point of doing that comparison
 » 2 months ago, # | ← Rev. 2 →   0 Can someone please explain to me how top coders solved E , it seems like most of them have used common and concise approach.Thanks in advance! Edit :. The sol is above , didn't see that
 » 2 months ago, # |   +46 Bye 2019，the year in which I met my girl friend
 »