Снова привет, Codeforces!
Мы ради пригласить вас на Mathforces Thinkforces Good Bye 2019, который пройдет 29.12.2019 17:05 (Московское время).
Немного информации о раунде:
- Рейтинговый для всех участников!
- 3 часа!
- Никаких подзадач!
- В раунде будет интерактивная задача . Вы можете ознакомиться с руководством по интерактивным задачам здесь
- Разбор будет опубликован сразу после окончания системного тестирования
Все задачи в этом раунде были приготовлены нами, antontrygubO_o и 244mhq. Мы долго работали над эти раундом и постарались сделать все задачи очень интересными. Надеемся, вам понравится раунд!
Мы бы хотели поблагодарить:
- arsijo за координацию раунда
- Mediocrity за идею решения одной из задач
- gepardo за полезные обсуждения задач
- farmersrice, Danylo99, 300iq, burstintotears, danya.smelskiy, _overrated_, Jeel_Vaishnav, stanislav.bezkorovainyi, shoemakerjo, spar5h, RomaWhite, Juve45, Stepavly, Supermagzzz, WhaleVomit, AdvancerMan, Andres_Alumets, cute_hater за тестирование и неоценимые советы. Рекорд ли это по количеству тестеров? O_o
- MikeMirzayanov за отличные системы Codeforces и Polygon
- Все общество Codeforces за то, что сделали этот год интереснее!
Количество задач и разбаловка будут обьявлены незадолго до раунда (или раньше).
Желаем удачи!
UPD1: Пользуясь случаем, хотелось бы прорекламировать сражение между tourist и Um_nik, которое начнется через пол часа после окончания этого раунда.
UPD2: В последнем контесте десятилетия на Codeforces будет 9 задач .
Разбалловка:
500 — 1000 — 1500 — 2000 — 2750 — 3250 — 3750 — 4000 — 4500
UPD3: Разбор
UPD4:
Поздравляем победителей:
You forgot Speedforces, Gapforces and Checker-is-incorrect-forces.
One more WeakPretestforces
hackforces , one or two times ddosforces
Queue-forces too.
Smolpp-forces
And ComplainingPeopleForces
And EditorialLeakedforces
And BruteForces
SchruteForces
And BestForces
And Isitratedforces
Is it rated?
ConstructionForces
is this rated??
Nah, it doesn't matter because you won't lose your LGM anyway.
Количество задач и разбаловка будут обьявлены незадолго до окончания раунда (или раньше).
Незадолго до начала ю мин?
No subtasks!This is what already makes the round goodWhat 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
what is a subtask
Two problems which only differ in the nature of constraints and the score distribution.
Кажется, что подзадачи на cf стали настолько нормальной практикой, что контест, который обходится без них, воспринимается как нечто необычное и хорошее, раз составитель отмечает это.
Написал Good bye 2019 раунд — Good bye рейтинг
Wow, my favorite author is antontrygubO_o. P.S. How I want to see constructive tasks with weak pretests
Are you serious? should a cyan prepare such important contest?
Are you serious? Should a cyan complain about a cyan preparing such an important contest?
Are you serious? Should a cyan tell something about a cyan complain about a cyan preparing such an important contest?
Are you serious? Should a pupil complain about a cyan complain about a cyan complain about a cyan preparing such an important contest?
Are you serious? Should... Uh, sorry for bothering you, Mr. Grandmaster.
(Edit: Mr. Grandmaster just changed his color just for this comment?)
Stack overflow for real cyan!
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
Only a newbie can prepare such important contest.
hello lance. how are you.
I'm not lance.
no, you are lance. guess who i am!
No I'm not lance. You are a user
hello mr expert. how are you.
Yes
only the coders with more than 2500 rating should make problems for such great contest
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.
Nope, these crossed-out words have the exact opposite meaning :)
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.
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.
hey, what would be the color of your hair in 2020.
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.
It looks like no of problems is not ready but editorial is ready :3
exactly
questions are bad, problems are not
It's a delight to see a specialist posting the announcement. :')
It's Santa's magic.
Terrific way to end the decade. 3 contests in a row, just codeforces style.
why Terrific ?
Magnific*
2019: Give me your sadness and i'll keep it for you =))
Looking forward to antontrygubO_o's new haircut!
Legendary problem setter > International grandmaster :)
I hope this year ends well :)
OOOohhh i get it now! it is number line-forces
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.
This comment should be posted here.
thanks for early editorial
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. :)
P.S. — This was meant as a comment for the Announcement thread for $$$611$$$ Div $$$3$$$.
I really liked this Div $$$3$$$ contest because
A great Div $$$3$$$ Contest to end the year !
mango_lassi I generally refer your solutions. How to solve $$$F$$$ ?
GOODBYE 2019!
Раунд от голубого...
A contest to tell goodbye every year. What about a contest to tell goodbye the decade?
It might take a decade to update the ratings! XD
nearly codeforce becomes best site in coders life :D
goodby contests are best
Hope there would be strong tests. I really don't want to be hacked in the last contest of the year
tourist vs Um_nik who will win ?. Enter your suggestion in reply .
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
This is codeforces magic :). Just check magic tab in your profile or you can read here here
thanks
From confused to LGM in 3..2..1..
go to your profile and checkout magic section
thanks
Огласите количество задач и разбалловку.
D was too nice for me.
Couldn't solve it.
Hoping to be expert after this contest.
9 problems :o I love it!
I don't like it. Let's go back to good old days with 7 problems :(
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.
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 :)
I think you love it because you become the first with it! Congratulations!
I didn't participate partially because there are so many problems.
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.
4500 points!
Is this the highest ever score?
I think hacking will be so hard this round because of the magic :\
13k+ registration. I hope all works fine during contests.
Yeah, and for 3 hours...
I really hope the servers will sustain the pressure...
contest finished with no trouble
Best of Luck to Servers as well.
speedforces strikes again
syrian goverment be like : oh there's a cool round what a great time to shutdown electricity
MultipleAnswerForces
Interactive killed me
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!
One of your submissions was ignored.
Thanks!
Same, but I got runtime error.
ConstructiveForces
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,
2
x s+x
can be the answer.
How you came up with this solution?
I put a pen on a piece of paper and found out in half an hour.
Jesus. This round was so fuckin good. The best in my entire life.
My solutions:
A B C D E F G H
My solutions
Can you explain solution B in test case 1 3 2 4 5?
Answer for this test is yes (segment from 1 to 2) because 3-1>=2
Will k change when we change size of array? I thought k was always = n @@
k is the size of the subarray.
How to solve D?
pick k+1 elements ask every subset of k elements. Count the times of the minimum number appears. The answer is k+1 — times .
Please explain the logic behind it too.
if m = 1 it will be the minimum if it exist
if m = 2 2nd smallest will be 2nd smallest if both 1 and 2 exist
if m = 3 3rd smallest will be 3rd smallest if both 1 and 2 and 3 exist
........
Understood. Amazing solution!!
Ugh, now thanks to your comment the task seems super easy and my idea super ugly.
0) 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 1
2) 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]<a[posB]
4) for i=0..k-1 query All unknown positions (except i-th unknown position) AND posA, posB
5) Answer = 1 + number of times (posB, a[posB]) appears in 4th step.
How to solve C?
Print x,s+x
And what's x?
xor of all elements.s is sum.
Tell me, if u still don't understand it
Can you please explain the logic behind your code?
First you add Xor value to makeits value zero then you add Xor+Sum Its something like this:
Sum Xor
Sum+Xor 0
2(Sum+Xor) Sum+Xor
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.
Congratulations to the organizers/writers of the contest. As far as I can remember, this is the best codeforces contest I have participated in.
Goodbye 2019 and Goodbye ratings. (Great contest btw!)
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.
How did 88 people solve a problem tourist couldn't in 2 hours 30 minutes??
EDIT: looks like lots of heuristic solutions passed :(
tourist got a call from his angry girlfriend that he never cares abt her....
Good bye 2019 and Radewoosh is on the way taking 1st place from Tourist. what an ending year!
Congrats to Radewoosh, first place at context, first place at top
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 :-)
What is your solution to E?
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.
H
I'm an author...
Notorious coincidence
For me it's not swapping but shifting an array. I can solve first but not second. How to reduce to swapping?
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<b$$$). So you keep a set of positions sorted by value.
Oh wow. Very nice criteria. That makes me sad..
How to solve E?
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).
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).
if $$$x+y$$$ is odd, points will be shifted to the left by one first.
To understand what the transformation does, draw some points with same parity of $$$x+y$$$ on a paper, then rotate the paper $$$45$$$ degrees.
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)%2
3.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)
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?
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.
My soln of G -
If 0 exists print it.
Else replace ai by i-ai
Now 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.
wow, great.
How did you find that subset, which cycle you are talking about
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.
Oh got it, Amazing idea
HOWRUSOGOOD??
Damn that is smart. I spent half the competition on G but no luck.
omg so beautiful
Didn't like D. Read the statement multiple times, but there was no mention of printing query in sorted manner, which caused WA.
how to solve D?
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<k$$$ ). First thing to notice is, since you have asked for all sets of k points, the discovered points are all in the "middle" i.e. there will be $$$m-1$$$ undiscovered points smaller than all of the discovered points and $$$k-m$$$ undiscovered points greater than each discovered point. Now, for these $$$k-1$$$ undiscovered points, we can find where ( left or right of the "middle" part they lie ), with one query. Ask query without the point i ( $$$k-2$$$ undiscovered points ) and add 2 points from middle. It is guaranteed that response will be one of the middle points. If it is the smaller middle point, then i belongs to the "right" part, else "left" part.
Then if you have identified $$$k$$$ elements as being in either left or middle or right part, you ask those $$$k$$$ points and again one of the middle points will be the answer. This time, you know all left points are smaller than middle ones, so ans is $$$left.size() + x$$$ ( position of response in "middle" ).
My queries are not in order, but I got accepted?
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.
Maybe you printed some equal numbers.
Looks like that is the only possibility, according to others' replies. Will see what case it failed on.
Silly error! Forgot to put spaces in query originally.
My queries are definitely not sorted, did not seem to be a problem o_O
What a terrible page error...
Scared the crap out of me too
Sale of detergent has spiked due to sudden craps in 13k pants
How do you see the triangle column(rating change column) during contest
It's because of the extension program.
CF-Predictor Chrome Extension
was it just me or anyone else who waited for an epic finish by tourist..?
How to solve D
How to check if integer is odd?
Normal people:
x % 2 != 00 msSmart people:
x & 10 msMe:
x % 2 == 125 minI hope there are some strong tests in G to fail stupid solutions (including mine), aren't they?
What's your stupid solution? I tried but didn't manage to pass pretests with wrong greedies.
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.
It seems that all stupid approaches sucessfully pass systests :<. So sad.
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)
$$$-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.
can anyone explain B as TLE in my case ??
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.
Best contest that I participated, so far. Thank you, antontrygubO_o and 244mhq! : ) .
Happy to end this wonderful year with a beautiful contest, thank you Codeforces team as well!
7 out of 9 problems with tag "math".
I like Mathforces
67929171 why it takes wa? Can you tell me the test?
thank you for explaining its meaning for me
Was not able to see the simplicity in B and C :/
Yeah, goodbye ratings.
Who is waiting for the stream to start?
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.
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.
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...
Yes, cause D, E and G were so similar, they almost felt like doing the same problem. /s
It is not like problems can be partitioned into "sqrt decompositions", "data structures" and "other" and all problems within "other" category are similar.
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.
Yeah, sure. Completely random.
Don't you agree that F and H are definitely more deterministic?
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.
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?
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?
Don't focus on what's fun for you, AtCoder already makes unbalanced contest because they are "fun".
"It's programming competition, not math competition..." said no one ICPC world champion ever :D
Didn't read a single comment from the thread beside yours.
It's programming competition, not math competition...
Well, now my comment is invalid, so sad :(
Also, we aren't here to do math only...
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?
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...
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.
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...
I think F and H is hard-coding but not hard-thinking Edit: It's wrong
According to this comment, you are wrong about H.
There are some mistakes when I read statement :'(
G(almost) https://www.russiancodecup.ru/en/tasks/round/20/B/
Upd: also https://mirror.codeforces.com/gym/100239/problem/B
Goodbye 2019, we'll go in a new decade!
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...
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.
How to solve B?
Consider only subarrays of size 2.
Thank u..
if the difference in absolute value of some adiacent integers si greater than 2 the answer is "YES"; Otherwise is "NO"
Thank u..
can you explain the logic please?
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
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.
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...
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})$$$.
when could we see others solutions?
GH is very cool. Kudos to author
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.
Well, this is a common technique in mathematics competition.
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".
"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.)
"Solving this problem involves nothing but decoding an extremely contrived statement" — what the fuck?
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$$$.
https://mirror.codeforces.com/gym/100239/problem/B Here you are
You can see that a lot of contestants solved it in 20 minutes
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.
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.
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,
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 bicsi 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).
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.
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.
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.
"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.
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.
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."
What happens if you have only one or two positive numbers and the rest are negative?
I also tried to work it out using induction, without much success.
Why can't I see other's submissions?
The contest ended quite a while ago!
antontrygubO_0 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.
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!
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.
I really like these problems. They are short and easy to understand.
Why can't we view others' codes?
Even testcases
Thanks to the 244mhq, antontrygubO_o for this round. For me, this is the best round for 2019
Can submissions be made public? The contest has been over for some time now.
Is it intentional that I you can't see other people's submissions from this round?
Can you please open visibility all solutions?
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?
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
Notorious coincidence? Problem C too?
is it normal that other people's submissions are locked ?
saketh 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.
Link to the two hacks: https://mirror.codeforces.com/contest/1270/hacks/608570 https://mirror.codeforces.com/contest/1270/hacks/608578
We used the test case
(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?
looks like the checker has been fixed, thanks!
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...
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
And he couldn't solve G, H and I...
And you also
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
Bye 2019，the year in which I met my girl friend
Statement of problem I defines x twice in the same context :(
Thanks for the Christmas gift,it helps me to keep my master. I and each of my classmates who did this contest lost about 100 rating.
For the problem E: DIVIDE POINTS
Can someone explain me, how to divide the points into groups for the following example: (1,2), (9,14), (9,2) ?
A: (1,2) (9,14) B: (9,2)
Hey, thanks for your reply. I completely agree with your answer. But I just wanted to know how can we decide this division, when all of them are of the format (Odd,Even) and also they can't be scaled down by 2 ? (in reference with the tutorial). I would be thankful, if you could explain me that.
If x coordinates of all points are odd, move all points (+1,+1)
What if we change B slightly (okay, maybe not slightly): you need not only to say if there exists some interesting subarray, but instead find the longest. I think I can solve it in O(n log n) with a bit of math, segment tree and sorting queries. Is there a simpler approach using greedy/dp?
Good bye 2019!