Hi everyone!
Yeah, you guessed it right, after a long four month break after the latest div. 1 round which was not dedicated to any official competition, you will once again have the unique opportunity to participate in usual codeforces round. No t-shirts for top-x competitors! No multi-level selection system for the opportunity to compete in final! No esoteric languages or marathon-like problems! We even will not tell you the scoring untill the very end of the round! That's it, like the good old days.
So this round was prepared for you by Ivan Smirnov (ifsmirnov) and me (adamant). We want to thank Max Akhmedov (Zlobober), Alex Frolov (fcspartakm), Edvard Davtyan (Edvard) and Mike Mirzayanov (MikeMirzayanov) for the help in round preparing, and useful advice. Special thank to Edvard for taking the role of coordinator this time and traditionally MikeMirzayanov for polygon and codeforces systems.
Good luck to everyone! We really hope that you will have a lot of fun participating in this round :)
UPD. Score distribution:
Div. 2: 500-1000-1500-2000-3000
Div. 1: 500-1000-2000-2000-3000
UPD. 2. Also thanks a lot to Alex Fetisov (AlexFetisov). Forgive me, please, I have totally forgotten about you :)
UPD. 3. If you missed the editorial, you can find it here.
My nerves are thin after previous contests, I hope one amazing and interesting round !
Good luck and without frustrating bugs :)
Hahaha.. This blog has been written so well.. Waiting for tomorrow...
প্রিয় গ্রাহক বায়োমেট্রিক সিম নিবন্ধনের শেষ দিন কাল। আর অপেক্ষা না করে ১ কপি ছবি, ভোটার আইডির কপি ও সচল সিমসহ এয়ারটেল বায়মেট্রিক পয়েন্টে আজ-ই চলে আসুন।
MR Airtel,
Nice to see you here. I am pretty damn sure you are not here to code but this is totally disgusting. We already know that you have a big business to work with but do leave others doing their work. Don't just pop out everywhere and say things like this. If you are here to code, then great. Other than that, Here is a bit of tutorial for you.
char c='F'; char c2='*'; cout<<c<<c2<<c2<<'k'<<" "<<"OFF";
{sorry everyone for the disturbing comment but I feel we have to be respectful to everyone. We[bangladeshi] are just destroying our reputation.]
I think some regular contestant has created a fake ID to make fun.
I am too lazy to translate, what was written there?
It says tomorrow is the last day of 'Sim Registration'. So hurry up.... :3
When i first see adamant is the author of the contest, my first impression is.. i have to read about policy based DS
(if you know what i mean :D )
I don't know... What do you mean?
You are the only source i found explaining the (policy based DS) in your blogs here here and here, and in the last round when i saw your submission 17490448
( less than 20 lines on E div1 :D ) using (policy based DS). so i think you might prepare problems which is solvable with this (policy based DS). that's it.
Sorry,but where is the solution?QAQ
So that's who is responsible for all these pbds-clang-incompatible solutions. Every time I need to compile them (with clang) in education round I have to delete this stuff.
"We even will not tell you the scoring untill the very end of the round!" — didn't you mean very beginning of the round :P?
Btw, I will keep some suffix array prepared for tomorrow :D.
No, I meant very end of the round.
So, are you simply not counting making it public at the start of the contest as telling?
Btw, is it rated?
All I can say is that we don't yet know the opposite.
P.S. You should definitely have asked this question right after the post appeared to get more upvotes!
How about dynamic scoring? :) You don't really get to know the scores until the end of the round.
We will consider this, thanks for brilliant idea!
It can be concluded from announcement that you really like usual rounds, so better keep it static :P
Btw sometimes it is hard to get the irony in the Internet, but I hope that your post was pure irony :P.
I have missed so many contests in 2016 because the power and the internet are always cut off at 23:30 UTC+8 in my school. But this contest is next to the holiday so that I can fight again! I wish I won't forget the feeling of algorithm competitions.
666 is the sum of the first 36 natural numbers and thus it is a triangulal number.
Notice that 36 = 15 + 21; 15 and 21 are also triangular numbers; and 15^2 + 21^2 = 225 + 441 = 666.
What we see here? Triangles in the perspective. We must go deeper! Do not you think it's like this?
The largest pyramid in Egypt is the Pyramid of Cheops (IV Dynasty), the Pyramid of Khafre (IV Dynasty), Red Pyramid, Sneferu (IV Dynasty).
(IV + IV + IV) : 3 = 4
In the perspective appearance of divisions 4 officially confirmed.
666 is also a special and popular number in China. When we Chinese see something is so cool or so amazing, we will say it is "666" or "66666666666"(very 666). This special meaning of this simple number begins just in these years. Similar with 666, 233 is another special and popular number in China, which means "LOL" -- Lots Of Laugh. If we Chinese see something is funny or ridiculous, we may say "233" or "2333333333333333333333" (very 233).
Ah, that's why his handle was 2333333333333. :D
Source.
No t-shirts for top-x competitors
yesterday my team ended first in our university ACM qualifications, so I hope to carry that achivement in today's round :D
Congratulations, was Qwerty your team's name???
(1)The team that ended first was named Qwerty. (2)He was in the team that ended first. From (1) and (2) we can see that his team was named Qwerty.
Such modus ponens, much wow!
Well he didn't say what collage he is from,did he?
Thanks, yes it's Qwerty from Tishreen university :D
my first contest after a long time I just hope I do this good
Since everyone's sharing their thoughts about the contest I'm gonna share mine too. 3 contests ago I was thinking if I make it in top 200 I'm gonna become purple again, but I failed. So 2 contests ago I was thinking if I make it in top 100 I'm gonna become purple again, but again I failed. So before previous contest I was thinking if I make it in top 50 I'm gonna become purple again, but yet again I failed. Today I need a place in top 5. Wish me luck!
Good luck.
good luck dude :) , i need place in top 1 to be purple :3 :D
haha, I need place in top 1e-3 or better to be purple :P
প্রিয় গ্রাহক বায়োমেট্রিক পদ্ধতিতে সিম নিবন্ধন করে ১৯ টাকা রিচার্জ করলেই আপনি হতে পারবেন purple. মেয়াদ ৩ দিন।
মাত্র ১৯ টাকা !!!! o.O তাতেই Purple :O :O
MR Airtel, Nice to see you here. I am pretty damn sure you are not here to code but this is totally disgusting. We already know that you have a big business to work with but do leave others doing their work. Don't just pop out everywhere and say things like this. If you are here to code, then great. Other than that, Here is a bit of tutorial for you. char c='F'; char c2='*'; cout<<c<<c2<<c2<<'k'<<" "<<"OFF"; {sorry everyone for the disturbing comment but I feel we have to be respectful to everyone. We[bangladeshi] are just destroying our reputation.]
You know you are almost becoming as much as annoying as the airtel guy. Leave him be and he will lose interest. You don't need to reply on each and every one of his comment
how long it will take me to be purple ??
depends on you
I will be blue before August! Fingers crossed! >_<
It doesn't feel any different ! It's just a color.
P.S : I want to be purple before August XD !
I know that but I feel that I can solve Div2C but I am unable to solve it because I start hacking after solving Div2B which takes half hour to one hour and most of the times it's useless. I feel pathetic about this. That's why I feel I am not where I should be.
Cant believe you like debugging more than problem solving!
just don't think about getting rating or your rating wouldn't increase ! well thats totally true for me whenever i think about rating i get my solutions failed so just code without any worries
Finally a chance for me to get back in Div2 :)
Me too. Fingers crossed.
You can do it :D
And I did it :P
div.2 E is div.1 D
such a usual contest
That's because div1 C and D share the same full point -- 2000. So it is to say, they think div1C and div1D have the same or similar difficulty.
On my mind the difficulty of problems div1C and dic1D is different for div1 and div2 participants. It is about obvious the problem D is harder, because there tricky cases there. But for div2 participants who not familiar with combinatorics it's about impossible to solve problem div1C while they can come up with the solution for the problem div1D (it is not require some specific knowledges). So I decided and the guys are agreed to give the problem about four points to div2 round.
CF and its overcomplicated problems are stoooopid! Who needs such hard problems in their life? They making quantum computers and soon all these precious algorithms will become useless. They make fast processors and cheaper memory, and array sizes can be as huge as anything. Any average billionaire can't solve even a div2 C yet they're billionaires. Seriously, what are we doing here? I am never coming back here. My last comment on CF ever!!!!!!
I request my account to be permanently deleted.
before leaving, can you tell us who you are(your name/organization/..)? I can't realize whom to miss.
Finally. I was getting tired of your shit in every thread.
In Div. 1 D there is a sentence in the problem statement.
"Note, though, the problem can include several records in one test, you can hack other people's submissions only with the test of one plate, i.e. parameter t in a hack test should be equal to 1."
Does this not go against the philosophy of hacking, which is that any hacking contributes to the best possible set of test cases, and that any incorrect solution should be hackable? There can be solutions you know are sure to fail system tests, but cannot be hacked by any test case (for example, TLE). This seems to implicitly states that the problem setters believe their test cases are best possible and do not need contribution from participants.
However, an easy fix could be to change all the system testing to have t = 1 so that hacking and system testing are identical.
I guess that for this particular problem testing the speed of the solution can be easily done with the tests from problemsetters. And the hacking tests are used for checking the correctness. The other reason is, perhaps, that it just takes too long to check the correctness of the answer provided by the solution, hence the limitation:)
my condition
Aaah, this C is so awesome but I couldn't finish it on time :( We can store the states through every sqrt(100000) numbers, right?
Actually we can use the fact that there are only sqrt different lengthes.
Oh, yes, mine will be slow, thank you :)
Formula for this problem:
, where k is the length of s.
It seems that I'll get TLE :)
Why does this formula work?
It is derived from recursive formula: f[n][k] = 25 * f[n - 1][k] + f[n - 1][k - 1]. That is similar to the LCS problem.
It is a two-variable recursive formula, how can you solve it?
I just know how to solve some simple forms with one variable such as the Master's theorem form (in Introduction to Algorithm). Can you recommend some mathematical resources for that too? I think it will be very helpful for everyone.
Thank you.
why this hack failed? (Div2A)
How to solve A? >_<
I had deja vu, when I was reading the problem. You can read about the idea here.
I will summarize very abstractly:
1. You need to convert to the same dimensions. That is, you need to convert the speed of gaining new water (because of the rain) to milliliters (because drinking speed is also in milliliters): ee = c × e.
c — is some coefficient.
2. The whole speed of loosing the water from a cup can be expressed as v - ee milliliters per second.
You have some amount of water from the beginning W milliliters and you loose it with the speed v - ee milliliters per second, so the time you have is:
t = W / (v - ee) seconds
The relative error was less than 10^-4.
relative error is 0.131386 and its MORE than 1e-4
That's absolute error. Relative error will be abs(9993.61-9993.74139)/9993.74139 which is less than 1e-4.
thanks!
It's absolute error. Relative error is actually
0.00001314677817154782844173184042381306993321477614657486...
http://www.wolframalpha.com/input/?i=(9993.61-9993.741385501099)%2F9993.741385501099
thank you i didn't know that!
What's wrong with Div2 D's TL? I just spend 30mins to debug. So desperate to optimize some loop and vector's push_back, AND IT PASSED PRETEST!!! It sucks.
yes same thing here but i could n't correct it because there wasn't any time!
very bad sence!
Very hard to read problem statement. I could solve problem A if problem statements were a bit more readable...
yes i had the same the problem for A ! without the examples there was no hope for me !
My apologies for that :(
I didn't see the words "in a row" and I tried to solve it for almost the whole contest only to found it not solvable at all...
Maybe I should read the next problem instead of stuck on this one.
It's been so long without a contest I forgot what it feels like...it feels good. I hope everyone has done good.
Geometry kills me in contests. I gotta get better at it.
:3 :3
How to solve Div2 D / Div1 C ?
None of my ideas ended up fast enough
The way I did it was I first did N BFS's to determine the all-pairs shortest paths. Then I made two matrices and put in the first one sorted lists of all the distances (and which cities they were from, courtesy of multiplying by 10000 and adding the city) to a given city and in the second one a sorted list of all the distances (and what cities they were to) from a given city. I then looped through each pair of cities with nonzero distance (these will be the middle two cities in the path), and for each of those pairs I went through the largest three distances from the second city and to the first one. If any of the cities were the same (or the distances zero) I didn't consider that combination (hence why I needed the top three cities in each case). I printed a set of cities with the maximum distance given these conditions. Overall this runs in O(NM) time.
Oh I see, ty
O(N^2logN) actually.
del
Do You mean O(N^2) ?
Yes you can do that by simply instead of sorting keeping a list of the top four cities as you won't need more.
Turns out you don't need more than three, since the distance to a city from itself is always zero (and thus, anything lower-ranked than that will be a zero distance as well and will be discountable as a possibility)... leaving you with only two possible conflicts for each list.
Python module "itertools" rocks in Div2E. Hope I won't get TLE or some disgusting WA case I didn't notice. Edit: Oops, actually, there is such a case:
My answer:
Right answer:
And it isn't covered by pretests...
What is the solution for Div2 B? I sorted and took minimum of absolute of ( Prefix_i * 2 — sum + 1) .
max(maxx-sum+1,sum-maxx+1) , where maxx- maximum element, and sum is sum of all other elements
It is always "maxx — sum +1"
I also do not see a proof. I think it works because it is impossible to form a polygon with what is given.
Yes, since it is impossible to form a polygon, there must be a side such that its length >= sum of other sides. The optimal way now is to build a triangle with its base as the larger side, the rest sides combined together to a single side with a zero degree angle to this side. So third side would be (total length — sum of remaining sides). But this triangle has zero area, so we need to lift the middle vertex just so that the new side's length increases by 1.
Fortunately my solution does that LOL.
I didn't knew why my solution works but I was trying to build a triangle, I thought of taking up the maximum element only but I couldn't come up with the proof for that either so I checked whether my solution passed the pretest or not.
I sorted the array, then subtract maximum with first n-1 terms and add 1. Couldn't prove it.
Source
when will the sytests start ?
DIV 2 D(World Tour) involves finding strongly connected components along with topological sorting like tarjan's algorithm right? I just got there but couldn't figure out how to proceed further. Any ideas?
Use bfs on all nodes to find All Pair Shortest Paths.
Basically my idea is for each pair (b, c), find (a, d) such that (a, b, c, d) are distinct and d(a, b) is maximal and d(c, d) is maximal. (use set or something similar for that)
Please don't start system testing 1 hour later like the last contest!!
Hello, my name is Alexander, and I like to write things like this (sorry for quality):
Writing
saves symmetry. Symmetry saves you.
In Problem C Div2 ... I just want to know what is the importance of this sentence "The only restriction — it is not allowed to append the same string twice in a row."
for example if I have "xxxxxabab" I cant put ab in the output as I can do like that --> "xxxxxab" — "ab"
In this case, xxxxxbcabab you can't get bc as output!
Suppose you have the string "xxxxxghiabab", note that the only way to obtain the suffix ("ghi") is doing: "xxxxx"+"ghi"+"ab"+"ab". But, with the restriction, it is impossible to obtain that suffix (because you put the suffix "ab" twice in a row).
How to solve div1D? I thought at brute force fixing the direction(OX or OY) and the order othe vertices in the square. After this we get a system of equations but the problem is that it's not uniquely determined. Still, I am pretty sure that we can have at most one free element(the others depend on it), and I guess that now, iterating this free elements throught the integer values that he can take, we get a convex function, so we can ternary search. Unfortunately I am not able to prove the convex function part and there is one more problem with the integer restriction because I'm not that sure that for any fixed integer value we get all the values integer, so the function won't be defined on Z so it doesn't work anymore. Can someone who thinks he solved it tell me how?
The editorial will be posted today or tomorrow.
As a writer of this problem, I'm also very interested in a solution with binary search.
http://codeforces.net/contest/666/submission/17585111
I used binary search here to get AC.
The editorial hasnt been posted yet.
If you know which vertex is, say, the top left one, the direction it will go and an upper bound on the time it has, you also know the segments of possible coordinates for top and left sides of the square. Intersect these segments using the information from all points. Now you can find out the segment of possible values for horizontal and vertical dimensions of the square. These two segments must have a common positive element.
So, brute force the permutation, brute force the directions, binary search on the time (which is unnecessary but makes things easier) and intersect some segments.
It seems nice and I'm sure in this way it can be done. Still, I don't actually understand what do you intersect. After brute forcing that stuff(I also did this thing) and binary searching the maximum change, you get some segments, knowing that on the first segment the upper left vertice can be found, on the second the upper right, and so on. But How do you actully deal with the remaining problem? It seems possible, but I can't see how. Can you please explain me more thoroughly?
Wrong solution was here before;)
Wow how stupid I was. In the cx=cy=2 case, I thought that it's impossible to find a solution and it was actually the easiest case. In this way, the code was much easier to write. Thanks :)
17578532
Run the following solution once, swap coordinates, run it once again.
Create sets X and Y where X denotes a set of x-coordinates from the input. Iterate over
that x1 < x2. Iterate over 
. Assume that we already have coordinates of 3 sides and run a function check_sq(x1, x2, y, y + |x1 - x2|) and also check_sq(x1, x2, y, y - |x1 - x2|). This function should check 4! possibilities of assigning input points to 4 points (x1, y1), (x1, y2), (x2, y1), (x2, y2). Check my code for implementation details. Also, it's possible that we know only x1 and x2, without knowing any y value, e.g. for test:
We know x1, x2. Let f(y) denote a function that returns the answer for check_sq(x1, x2, y, y + |x1 - x2|. This function is maximum over 4 functions of form |y - const| so it's also strictly bitonic (it has form const1 + const2·|y - const3|). So, we can ternary search the optimal y, checking the value with already created function check_sq().
Very nice explanation. I've just got AC and event though I wrote about 190 lines, they were very easy to write (about 20 minutes). This solution makes me like the problem. Thanks!
I am not good at English so i don't understand div2 E Also, i spend too much time to understand div2 D
I think i should study English Hard T.T
I'm also not good at English but I think after a year of training and reading problems, you can understand 99% of problems with simple translator.
Waiting system test is like waiting prison break season 5.
you know the end will be shit , but you still waiting -.- .
system testing is over , it took less than a minute
and the end is shit -_-
I failed in B+C and got D accepted
How to solve DIV 2C : http://www.codeforces.com/contest/667/problem/C
It's easy. see this: 17584300
Dynamic programming from right to the left, storing True or False for every suffix of length 2 or 3 (can this sequence be a suffix or not).
Can you provide a code? I was thinking about that but I didn't know how to code it
You can see my submission here, but I suspect you don't understand Python (here is the information about slices and indexing in the string), here are some comments:
Thanks
Hey, My code fails in sys test 42.. but it gives the correct answer on my system. I have even handled the case it fails on, in my code. Can anyone pinpoint the issue ? Solution link:
http://codeforces.net/contest/667/submission/17577331
Sorry for the mix up, I took jury's o/p as participant's o/p..
For div1c, I derived the mathematical formula which runs in 100000 * 100000 — and used some tricks to prune the runtime for half. I was very nervous since I thought it might fail. but happily, it passed systest (in only 2.4s)!
Am I the only one who used pruning?
http://codeforces.net/contest/666/submission/17577445
This is incorrect solution. Test: 1e5 string(5e4, 'a') 2 1e5 ... 2 1e5
I'm aware of that data, and after submitting C, I tried to run that data at custom invocation — but I failed to run it (idk why, but it didn't work). so I just hoped for a fast calculation + easy testdata :)
Whatever, pruning is just pruning :)
You are right.
It is our fault that there were no such cases in testset. We are very sorry for that. Testcases are added so solutions like yours will not pass in upsolving. However, competition result will not be rejudged since it is considered to be a bad idea to cancel AC after final results are published. You should feel lucky since your solution could be hacked, but it was not. Sorry again.
There are only at most
different lengths given the sum n, so you can reduce the complexity to 
.
Can someone please tell me what is wrong with my answer?
you forgot to print "YES"
Oh FML! >_<
UDP: Sorry, I have found the ans.
Hacking case for div-2 C is aaxaxabbabbb. many solution with 1D dp failed at this case.
Can anyone tell me what went wrong? Solution A
Try to change the value of PI from 3.14159 to acos(-1.0).
You better not set precision.
I tried using %.6f and it worked. setprecision was the reason I got it wrong!
In Div.2 C, I mistakenly thought a suffix sequence "aa" -> "aaa" -> "aa" is invalid. hahaha.
I tried to hack div2.Problem B.Coat of Anticubism of some users with test case
5 8 4 3 2 1
but it said invalid input, but why?
In input statement, "It is guaranteed that it is impossible to make a polygon with n vertices and nonzero area using the rods Cicasso already has."
Let's sort them first. 1 2 3 4 8.
Now if we add the first 3 rods we have 4 6 8.
We can construct a convex polygon with side 4 6 and 8. But the problem says that it is guaranteed that no convex polygon can be construct by the input.
I used bisection to solve Div2A. Couldn't find an easier solution -_-
me too :p no need to think hard for the right formula , just get it right
OK! it's now two contests in a row, getting WA on pretest 2, which is in the samples!!!! This is really getting embarrassing :(
The subjective and easy to lost points :)) :)) Sometimes me too :(( :((
and lossing 226 places in the standings :(
Proof that in Div2B it is sufficient to make each side less than sum of others: Let the greatest side be of length d. Then split all other sides into two categories with nearly equal sum of lengths: let us add other sides in length decreasing order one by one into the category with smaller sum of lengths. Then in the end the sums will differ not by ≤ d, with equality only in the trivial case when all sides are d. Then we can construct a triangle from d and concatenated sides from each of the categories, because all three triangle inequalities are satisfied.
Many solutions on Div2A would fail on the hack test by user sid02
hack test is: 2 5 3927 1250
correct answer is: 1710.545730564287
for example:
17576065 output is: 1575.38
17569724 output is: 1570.796000
17574966 output is: 1693.15
17570584 output is: 1570.8
17569909 output is: 1698.1582
17571073 output is: 1698.1581622
I was wondering why it wasn‘t added to the final system tests...
All the successful hacks should have been added. If it wasn't it means there was a bug and that task should be rejudged.
how is NrootNlogM complexity passing for E in 2 seconds. its way more than 10^9 operations.
And time isn't 1 second? :P
When will the editorial be posted?
BTW how to solve div2/C ?
They will be posted as soon as possible. Div. 2 C is simple DP. Assume we reversed the string. Then DPlen[i] — is it possible to split s[1..i] in suffixes in such a way that last would have length len. Then you can use following formulas:
. Similarly 
Completely ****ed up with this problem..... thanks man!
Does this case "zzzzzpbpppb" exist an ambiguity in the meaning of DP? The first "pb" (from left to right) cannot be chosen because there is another "pb" on its right, However its DP value is true.
But it can be chosen. zzzzz|pb|pp|pb is correct partition.
How? pb is repeating here.
Is this valid partition? zzzzzpb | pp | pb
Yes, this partition is also valid.
zzzzzpb | pp | pb is valid
but
zzzzzpb | pb is not valid
because pb is "twice in a row" in second case.
The appended strings can't be twice in a row. First "pb" is part of the root, so it is OK!
Oh I misunderstand “twice in a row”:(
I just misunderstood the statement too... Btw,how to solve the problem if removing the condition "in a row"? Also DP?
Hm, I don't know actually. Does anybody?
Can someone help me in finding out why this gives WA for Div2 D ?
Thanks!
There is one thing I would like to officially complain about. I didn't carefully read the statement of the task A and forgot to print YES before printing the result. I wouldn't mind subtracting points for an incorrect submission, but if the same thing happened to somebody who prints incorrect version of NO, like
NO
0
there will be no punish, because that would be caught by the first test and this is not counted as incorrect submission. This way people who are lucky to get WA on the first test case, will get away with it.
Hence I kindly ask to change this rule: either count each incorrect submission or don't count incorrect submissions on all the tests from the task statement. Otherwise the order of tests influences your final score, and that factor shouldn't be taken into account at all.
In my solution (Problem D), my code is giving runtime error, but, when I comment line 121 (resp[0]=a) not gives? someone understand why it happen?
runtime
not runtime
Editorial??
Btw, will the round be rated?
Yes. Ratings have already been updated.
I see. Hope for lots of math.
What is the answer for this case in Div.2B?
4
1 2 3 4
3
Shouldn't it be 1? If we take 1 + 4 as a side and 2 + 3 as the other side, we have two sides of length 5. Then we only need a size of length 1 to build a triangle.
It's invalid! We can make convex polygon using sides 1, 2, 3 and 4 because 1 + 2 + 3 > 4.
You're right. Thanks!
Why is there still no editorial in English? Is an English editorial going to be published at all? BTW, I think you should organize more rounds, the problems from this round that I managed to solve during and after the contest are awesome! :)