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://mirror.codeforces.com/blog/entry/60176 after the contest is over to discuss the problems or voice your complaints along with scott_wu and ecnerwala!
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://mirror.codeforces.com/blog/entry/60217.
Auto comment: topic has been updated by ksun48 (previous revision, new revision, compare).
"a special surprise which might be happening during system testing"
fast system testing!
Don't get your hopes up...
maybe pretests = systests, so there is no system testing and nobody fails :)
Yeah, and get 50+ pages queue during the round, would be nice.
Then we will also have a special surprise during the whole contest.
Maybe if you have passed pretests but failed systests you'll have half points for the problem.
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.
It seems that when the comment is hidden, people are more likely to read and downvote...
It seems sometimes people downvote just because the colour of your name isn't good enough!
Here Downvoting is inversely proportional to your ratings
it's like a self-fulfilling prophecy. The website says the post got negative feedback, so it gets more negative feedback.... lol
Then there's no systest so there's maybe also no such 'during' system testing ? ;)
Or maybe the surprise is that there are no/weak pretests o_O
Or maybe there will be so many failed solution on SysTest
The surprise was, that there's no surprise :D
Yaaay
I had enough surprises after today's D problem :(
Its for me:
And are you the ball?
Same with Colombia and Poland
Yap, but can get second half of the match fully.
Can't wait to see that special surprise :)
Is it on english only or you have russian version of contest too?
All official Codeforces Rounds have problems available in both Russian and English.
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.
why the score distribution will be revealed after the contest starts ?
I smell math problems.
Are you playing Dota 2? ;)
Dota is love, Dota is life.
LGD is invincible!
Yeah, but i don't like their offlaner.
is it rated?
How is scott_wu orange in your post? o_O
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.Oh that's great!!!
How to do like this:
scott_wu wasn't newbie in any period of time!
It's easy:
I'm LGM : IIIIIIIIIIIIIIIIIIIII
Cool :)
But Why u did so??
Or you can use HTML VladProg
P.S. You have never been red.
Yes, with HTML even you can be admin VladProg XD
Abelyan
Numb
VladProg
You are both olive now
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
P_Nyagolov
Why the 2 divisions are divided by 1900? Anyway I am glad to take part in Div.1.
I want to be the man with the worst contribution can you downvote me please?
Ah! The wonders of reverse psychology.
Best way for that is the golden sentence "Is it rated?"
Nice try son, this is how you do this.
Amazing email id: udebug@udebug.com
Will the conditions of tasks in the Russian language?
Read this.
Wael.Al.Jamal
How did you make it ?
With HTML:
MohamedAhmed04 :D
Thanks rkocharyan :)
500-1000-1500-1750-2500-2750 not 500-100-1500-1750-2500-2750
Div.2 B = 100 points XD
EDT : Fixed
swap(C, D);
What exactly was the point of having a problem like div1 A which is conceptually pathetic but extremely cumbersome implementation?
yep
He is talking about Div1 A not Div2 A
damn. div1 a/ div2 c was hell. I wonder if I'll be able to sleep peacefully after seeing it.
I didnt think it was that cumbersome, just implement a rotation.
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!
In div2 D you are only allowed to swap adjacent elements.
And you don't have to "sort" the array.
This is the same question as Div2 D. copy paste and bamn
In our problem, you can swap only adjacent elements.
kind of bubble sort.
div1C = http://acm.timus.ru/problem.aspx?space=1&num=1130&locale=en
How to solve this ?
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.
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.
I don't understand this.
2
999999 -1
-1 999999
is a countertest, right?
you just take both of them as it is. 999998 999998 is a valid answer.
Oh, I'm stupid
Then repeat both vectors two times.
my bad. I think i've actually missed some cases. probably it won't pass sys tests.
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
What about lot of zeros/small vectors, and several large?
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.
what if 2 vectors 1000000 0 and rest are 0 1. isn't there a chance that the 2 large vectors get never chosen?
There is a chance. But it is something like 0.000000000000000000000000000000000001
Looks hard. Try this:
I think I got it
20 900000
20 -100000 (x9)
repeat 10000 times.
This is a local minimum if you allow only changes in up to 9 vectors at once.
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 ;).
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.
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 :).
Congrats on this :)
very nice solution!
Wasn't simulated annealing an appropriate solution? I got a TLE on system test 51, but otherwise it looked fine to me.
What is 'fine'? Can you prove it or something?
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!
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.
I thought to start practicing acm.timus.ru, I hope I would have started. Maybe I would have done this problem.
maths too hard~~
I solved Tesla in a very roundabout way...
thanks for beautiful task F
Your submission page basically is a graveyard
Stream starting now! Check out https://www.twitch.tv/ttocs45 to discuss problems and watch tests.
[Edited] http://mirror.codeforces.com/contest/996/submission/39627469 can someone point out the mistake with this dp implementation of problem E ?
You took ints, instead of long long?
Не знаю почему, но мне было намного легче решить задачу С из второво дивизиона, чем задачу D. Чувствую многие со мной не согласятся :D
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.
how to host contest :-
randomly select problams from other platform
One of the best rounds lately (IMHO), except that Div1C is boyan.
I cowarded out of submitting div 1 B and C and then it turned out both solutions were correct
How do you learn to prove greedies?
Я не понимаю. Многие решили задачу B двойным циклом. Но хаки не проходят!!!! Как это понять?? 7 раз пытался хакнуть, всего лишь один раз удалось сделать.
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.
Oh, and I hope that E has proved beautiful solution and not my randomized garbage. And that randomized solutions for C will get WA.
For C, I random shuffled the vectors and choosed them greedily. Passed at 77 ms.link
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...
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!
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.
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, jqdai0815
3
1000000 0
0 1000000
600000 -600000
the greedy gives -1 1 1, isn't this correct?
what if it gives 1 1 1?
chosing 1 at beginning and -1 gives same radius.
OK, there you have free choice for second
3
100000 0
-1 1000000
600000 -600000
I thought this solution wouldn't work?
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
See this solution for problem B — http://mirror.codeforces.com/contest/996/submission/39628153 How is this passing the following testcase without TLE: 2 1000000000 1000000000 Can someone explain?
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.
I tried to hack this solution https://mirror.codeforces.com/contest/996/submission/39614615 using above testcase but it gave unsucccessful hacking attempt.
Also I tried this testcase on my PC. It is taking easily 3-4 secs. Don't know what is happening here.
div2.C:toooooo difficult but 1500 div2.D:toooooo easy (than C) but 1750 div2.F:toooooo easy (than E and C) but 2750!!
I really think D gonna be a disaster. I am not even sure why my solution passed
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?
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
Even I think so. Probably, there will be a lot of failed system tests. Appears too easy to be div2 d.
div2C was frustrating.
I think so too. I based my observation on this tc.
After finish debugging my solution for Div 2C. The contest is over. :)
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)
can't understand div1.D QAQ
Ya that was a pretty easy problem but I didn't get the problem statement so couldn't do it.
It would have been much clearer if they explained 1st test case.
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.
haha i even found a similar solution in my room and even his code runs for 1000 1e9s smoothly. weird :/
Same. I tried to hack 39618975 with
but the hack failed.
What was the runtime?
717ms only. Looks like Mike has got supercomputers now.
I successfully hacked 3 TLE solutions, so not sure what's up. Could be some C++ optimizations?
http://mirror.codeforces.com/contest/996/submission/39617181
The 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).
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
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.
ksun48 Many people have this doubt. Can you please explain how a 10^9 solution can pass?
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.
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.
This time the ones that get ACs get them with runtimes of more than 800ms, so optimizations seem less likely than faster testing machines.
How to solve div 2 B ? I saw alot of bruteforce B that passed pretest
how did the brute force passed....i am also wondering ..
@ksun48 how??
i dont even know .... just watch some pretest passed guy on the leaderboard... alot of them using bruteforce
EDIT: that was about div2 D, sorry
It'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.
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.
That runs in O(2^N) which would TLE since N <= 100
Not the same problem. In the problem, you can only swap adjacent element rather in the link you can swap any two elements.
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.
Please take care so that it isn't useless comment in future comments.
My solution for div 2 B: http://mirror.codeforces.com/contest/996/submission/39614836 Will it fail?
yep.
Even there is several "strange solutions" for many tasks, thank you for great round ! It was really interesting solving this tasks :)
Such a surprise, random system testing!
today many div2 b will be failed
test for div2 b : 4
7 5 6 8
// i hope i should hack many sol
is it 2?
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.
Can someone check my div1-F (didnt solve in time though).
Let dpn, d be a way to pay a subtree with root in
nusing a set ofddifferent values. It's rather trivially constructed asIf d < n — that's the answer.
Otherwise lets construct Ek — number of ways to pay everyone using exactly
kvalues.And finally answer is
I'm not sure if it's correct, but shouldn't the answer then be
?
Yes. Got lost moving from my writings to latex
Intuitively the solution looks correct and also Lewin's solution is the same. So I guess it's correct.
Expert for one day :D rip rating
Really enjoyed the set though :)
Your text to link here...
In which hell can these code pass the below test case?
7 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
AC with 889ms runtime. The testing computers got faster?
I think the test case are very lame.
https://www.youtube.com/watch?v=jPLKXEUm0jE
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!
I got 2 unsuccessful hacks due to very fast custom testing computers I guess.
Is not this the same surprise that they promised?
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
please take a look at the question. :)
I am talking about Div2B not A
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.
Interestingly this bruteforce submission gives TLE : 39630584 and this passses : 39630937
only difference is that % operator isn't used in the second one.
Very interesting, indeed.
The difficulty for me: FBDECA.
It seems the problems are randomly shuffled for me :/
Well, you are very good at math, congrats :)
F was hard for me, and D wasn't easy.
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.
I think it's a very classic problem. I have seen tons of similar problems.
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?
I somehow managed to get AC on Div2E/Div1C by greedy...
You should count yourself extremely lucky :/ I iterated from 0 to n — 1 instead and got WA on test 76 :/
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
Yep, I think the system tests could be improved further, but I understand this is a hard problem to write tests for.
Can anyone explain to me why the solution for Div2D is what it is. I cant understand
I think there is more than one solution. For example i did O(n)
Can you please explain your solution?
O shit sorry. I thought that solved it O(n) but did (n^2) )))0))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.
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
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 !!!
"a special surprise which might be happening during system testing"
I was really surprised! I have never thought my solution could pass system tests!
Crazy contest ToT. I am nearly become candidate master :((
I think problem Tesla was very hard
In Div.1 C Div.2 E can two vectors have the same x and y
Yes , Why not ?
no i just want to know the answer for
n = 100000
and all vectors are x = 1 y = 2
Edit : after asking ksun48 it showed out that problems are allowed to have multiple answers.
there are many solution one of them is -> 1 -1 1 -1 1 -1 ......
thats why I asked this question there is some AC gives only 1 for this test
in the first example there are two vectors have the same x and y XD
http://mirror.codeforces.com/blog/entry/58229#comment-419511 — 2nd_places++ (recently also ++'ed on CSA) and still no 1st places anywhere xd
Just why geometric when we have a lot of good tags!!??
Div2 F/Div1 D is the most troll question on all of CF lmao
Is the sample explanation for question E wrong?
Yeah, we're wrong, it should be 1->2->3. We just fixed it.
Can someone prove why this solution passed for Div.2 E? And if not provide a counter case that would disprove this.
div1B = Swap Pairing
EDIT: wrong contest
https://mirror.codeforces.com/contestInvitation/7b43f1bdfe15913f2ead227129417cbfa2fa08ee Залетайте!