### cgy4ever's blog

By cgy4ever, 5 years ago, ,

Fox Ciel is back!

I invite you to participate in Codeforces Round #290, which will start at the standard time on next Monday:

This is my 4th round on Codeforces, my previous rounds: #190, #228, #270.

Last Div1 Round (#286) is so hard, so after notice that, we decide to reduce the difficulty of this round. (For example, current Div1-E was used as Div1-D) I hope more people can enjoy all tasks in this round: this time no task requires advanced knowledge like linear space or Fourier Transform.

The background story will be Fox Ciel's life: learning programming, play games, traveling, have dinner and so on.

Like Round #228, top-20 contestants that are currently at Petrozavodsk training camp will be rewarded with nice Codefores T-Shirts. Contestant may be a team member, jury, coach, organizer, or whoever else involved in camp, no matter of status.

As usual, thanks to Zlobober for giving great suggestions and test my round, and MikeMirzayanov for the platform (Codeforces and Polygon).

Good luck and have fun!

Update1: Score Distribution is ... Div2: Standard (500 — 1000 — 1500 — 2000 — 2500), Div1: a bit unusual ... (500 — 1000 — 1500 — 22502250)

Update2: Editorial: http://codeforces.com/blog/entry/16173

Update3: Congratulation to our winners:

Div1:

They are all people who solved 5 tasks!

Div2:

• +636

 » 5 years ago, # |   +56 Nice! I love your contests! Always I think that a little easier problems are better.The best programmers will certainly be in their place,and other competitiors will get more fun.
 » 5 years ago, # |   -11 i'm not in Petrozavodsk training camp, but i want t-shirts too :)
•  » » 5 years ago, # ^ |   +1 ooops sorry, i just kidding.
 » 5 years ago, # |   +77 "advanced knowledge like linear space" :P
 » 5 years ago, # |   +53 hmm, i always thought that Bredor_228_Jaguar_Turnik was the author of Round #228. ;)
•  » » 5 years ago, # ^ |   +1 Look at his head carefully in his profile photo :)
 » 5 years ago, # |   -23 Doesn't using the current Div1-E as Div1-D make it harder, not easier? The D task will be hard as E task, and E task will be even harder!
•  » » 5 years ago, # ^ |   +17 It means the previous D will be the current E.
•  » » » 5 years ago, # ^ |   +3 actually, minimario's translation was correct. It seems that the author has his wording wrong.
•  » » » » 5 years ago, # ^ |   0 Maybe you are right, I'm not good at grammar. Then how to express it properly?
•  » » » » » 5 years ago, # ^ |   -6 It should be:"For example, the previous Div1-D was used as the current Div1-E."
•  » » » » 5 years ago, # ^ |   0 I parsed it as "the upcoming Div1-E was initially supposed to be Div1-D". But the points is this round is going to be easier than the last Div1 round, at least according to the author.
 » 5 years ago, # | ← Rev. 2 →   +50 The contest is from China. The time is 19:00 in Russia it means 00:30 in China! an it will last for two hours that is 2:30 AM! Will you be awake that time? :D Anyway, Thank you for the contest... It's my 100th contest and I'm really scared because my rating change in your last contests was : -54 , -74 , -127 :D UPDATE : This time my rating change was -106 :| cgy4ever...
•  » » 5 years ago, # ^ |   +62 Afaik, cgy4ever is from China, but not in China.
•  » » 5 years ago, # ^ |   +39 It start at 8:30 am here (California), I hope I can get up at that time.
•  » » 5 years ago, # ^ | ← Rev. 5 →   +20 We all get used to competing programming contests at late night, since almost all contests of Topcoder, Codeforces, Hackercup and GCJ are hosted on bedtime in China (UTC+8). So I'm sure cgy4ever would be awake if he were in China (But he is in US now, Chinese topcoders always get up late :P).
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 .
•  » » 5 years ago, # ^ |   +19 next one -213
•  » » 5 years ago, # ^ |   +3 last time your rating change was -127,this time -106, so that's an improvement by +21 !!!
 » 5 years ago, # |   +72 Didn't provide much help to Fox Ciel in last round . Will try to impress Fox Ciel atleast this time
 » 5 years ago, # |   -24 Thank you for making this contest :)
 » 5 years ago, # |   -21 YESA CGY4EVER ROUND!!!
 » 5 years ago, # |   +21 finally a Div 1 + Div 2 round after 4 continuous Div 2 only rounds :)
 » 5 years ago, # |   +42 Congratulations on advancing to the onsites of Facebook Hackercup cgy4ever.
•  » » 5 years ago, # ^ |   +96 Thanks!! Now I've advanced to nearly all big onsite finals at least once: GCJ(2011), TCO(2013,2014), Yandex(2014, but can't participate due to visa issue), FHC(2015) and ICPC(2015).
•  » » » 5 years ago, # ^ |   0 best of luck for the final
 » 5 years ago, # | ← Rev. 4 →   0 ~~~~~~~~
•  » » 5 years ago, # ^ |   +6 you did it once before, i believe you can :)
•  » » » 5 years ago, # ^ |   +6 twice :P
•  » » » 5 years ago, # ^ |   0 I did it!!
 » 5 years ago, # |   0 I've registered but I might not be able to participate. Will my rating be affected if I never even open the contest page? (like on TopCoder).
•  » » 5 years ago, # ^ |   +3 Your rating is not affected if you don't make any submission. (You can open the problems and decide to leave if you don't want to submit without any rating change.)
 » 5 years ago, # |   -7 I wish good rating for all
•  » » 5 years ago, # ^ |   +29 But that will never happen :(
 » 5 years ago, # |   -24 I Love my rating :1616 :))
•  » » 5 years ago, # ^ |   +6 then you shouldn't participate in this contest or your rating will change :)
•  » » » 5 years ago, # ^ |   +29 Maybe it change to 1717:)
•  » » » » 5 years ago, # ^ |   +13 17 — it's not good number. Need 3232 or 88 =)
•  » » » » » 5 years ago, # ^ |   0 need 228 :D
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I see, you decided to make this rating. It is more easier than make 1616 or 1488.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Maybe his/her rating change will be 0 :)
•  » » 5 years ago, # ^ |   0 Shame on you :(
•  » » » 5 years ago, # ^ |   +1 Why ?
•  » » 5 years ago, # ^ |   +9 Why? because Shakespear died on that year?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Dixtosa Giovanni Battista Agucchi died in 1632 :p
•  » » » 5 years ago, # ^ |   -11 No, He died on 1623 :)
 » 5 years ago, # |   +3 hoping to taste div1 after the competition
 » 5 years ago, # |   0 Its good that its two division contest, otherwise merging it results in some weird rating change like #270 and GoodBye 2014 because too many top coders registered for this round.
 » 5 years ago, # |   0 My first contest, wish me luck.
•  » » 5 years ago, # ^ |   +4 My first Div1 contest, wish me luck.
•  » » » 5 years ago, # ^ |   0 Good luck.
 » 5 years ago, # |   0 Get ready to rumble!
 » 5 years ago, # |   +1 Good luck
 » 5 years ago, # |   +29 Wow, over 6000 registrants in total. Can CodeForces handle it?
•  » » 5 years ago, # ^ |   +23 Apparently no. I cannot open the first problem.
 » 5 years ago, # |   +8 Why I can't hack other code?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +4 Make sure you locked your solution for that task first.And make sure you are in the same room with that person.
•  » » » 5 years ago, # ^ |   0 He's only submitted problem A. And I really can't think of a bug someone would have in coding such a problem. :) I think he asked why nobody has made mistake in implementing A. :D
 » 5 years ago, # |   +57 That feeling when you hacked tourist :))
•  » » 5 years ago, # ^ |   -16 Liar!
•  » » » 5 years ago, # ^ |   +1 No it was mkirsche that hacked tourist, Ximera was just pointing it out. I was also confused at first.
•  » » 5 years ago, # ^ |   +89 That alone made this a successful contest as far as I'm concerned. :D
 » 5 years ago, # |   0 Oh! TAT! In my room,only I locked the code!And I was waiting a coder locked his code then I will hack him! But when I found a coder has locked his code,he used java and I can't hack him.I am so sad! Maybe I should average up and I can go to the div1....
•  » » 5 years ago, # ^ |   +6 You can hack any solution, not only those that are locked. (Of course, hacking an unlocked solution means the owner can still get to fix it.)
 » 5 years ago, # |   +13 what was the hacking case in div-1 A
•  » » 5 years ago, # ^ |   +24 2 bacrr bacit should be impossible
•  » » » 5 years ago, # ^ |   0 thnx missed it completely ....and got hacked :(
•  » » » 5 years ago, # ^ |   +3 I handled this case, still got WA in test 12 :(
•  » » » » 5 years ago, # ^ |   -10 same :(
•  » » » » 5 years ago, # ^ |   +5 Then try test 3 a ba bb. You may have counted one inequality twice.
•  » » » » » 5 years ago, # ^ |   0 I did that as well. Still WA in test 12. :(
•  » » » » » » 5 years ago, # ^ |   0 same :( :(
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Try this 5 page ping pile care arrayans is not impossible
•  » » » » 5 years ago, # ^ |   0 Have you guys figure out test 12 yet? I cannot see the whole dataset.
•  » » 5 years ago, # ^ | ← Rev. 4 →   +4 Possibly it is 2 aa a But I am not sure if it is a valid test case
•  » » 5 years ago, # ^ |   0 I suppose something like 2 abcx abc
•  » » 5 years ago, # ^ |   0 What's test 12 for Div1-A?! I can't see full test. It's a huge test and shows "...". I try all of the special test cases mentioned in this post but my code still shows "Impossible" instead of "abcdefghijklmnopqrstuvwxyz" (the answer for the test 12). Here's my submission: 9688819
 » 5 years ago, # | ← Rev. 2 →   +7 So what's the solution for D?It seems that we need to ignore nodes contained in a cycle, and do a DP on the resulting forest. I had a O(N4) DP for solving a single tree, but I'm afraid it would TL (especially with recursion). Then I thought that to count the number of eliminations of size k, we need to count the number of subtrees of size treesize - k, which results in a O(N3) DP, but that totally ignores the order of elimination. Is there a O(N3) solution after all?
•  » » 5 years ago, # ^ |   +11 To solve a tree of size S I used this algorithm: for each node, find the number of ways to remove K nodes such that the node is not removed (if K < S) or is removed last (if K = S). Then an ending subtree of size N is counted N times (once by each of its member nodes), so we adjust for overcounting by dividing by N.
•  » » 5 years ago, # ^ |   0 O(N4) with 3 seconds TL (and nothing else that could have the same complexity) and only in one small loop? Plus with O(N3) memory? I'm pretty sure it would work if you don't do something utterly stupid.
•  » » » 5 years ago, # ^ |   +3 For some reason I still have the impression (from sometimes before) that anything more than 108 is slow. Time to forget that and move on :)
•  » » » » 5 years ago, # ^ |   +3 Depends on what it is. Processor instructions: no. Actually 4 times (common with DP) less simple C++ instructions: no. Insertions in a map of constant size: probably yes.It's better to risk it and find out in such a case.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 We should exclude not only cycles but some other vertices too, for example if cycle is conected to another cycle etc.We have rooted trees (connected to some bad vertex), and unrooted trees... and well I in both cases we can compute the answer using dp in N^3. Then we can join answers for trees using binomial coefficients in O(TN) where T is number of trees.But I didnt have enough time to debug my solution, so maybe it's wrong.
•  » » » 5 years ago, # ^ |   +5 What I meant was that we should exclude nodes that are part of some cycle. That includes your case :)Yeah, I think you were doing it the right way.
 » 5 years ago, # |   +3 great contest i'm waiting for your next contest thank you
 » 5 years ago, # |   0 Last minute, CF was down! I couldn't submit my A solution :( Actually I solved A but I was waiting for solving another problem too, after I submitted B and Got Pretest Passed, I wanted to submit A too. Which is now undone thanks to codeforces :D
•  » » 5 years ago, # ^ |   +1 i wrote a submission for b, but haven't ten more secs to submit(my last round i submitted C 2 minutes before the end.) nevertheless, i need more time to get div1 membership :/
 » 5 years ago, # |   0 what was the solution for div1 b or div2 d? I tried pd with a knapsack, but the numbers were to big i think for that. Are there some tricks for big numbers? or is there another approach?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +23 A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n. Since we want that to apply to all n, then the GCD should be equal to 1. The solution is DP with state (i, GCD) (last used card and current GCD of cards). We can use a map to store the states since the number of different possible GCDs is quite small.
•  » » » 5 years ago, # ^ |   +3 that was also my idea, but forgot the fact that the number of GCD is small. thanks!
•  » » » 5 years ago, # ^ |   +3 How to prove that the number of different GCDs is quite small?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   +13 Because it should be the divisor of some number ai and ai ≤ 109. Numbers in that range can't have many divisors (less than 100 I believe). EDIT: Ooops, my guess was wrong, thanks for correction Andrei1998!
•  » » » » » 5 years ago, # ^ |   +11 In fact, 735134400 has 1344 divisors, so a safe guess would be 1500.
•  » » » 5 years ago, # ^ |   0 "linear diophantine equation" is probably an overkill ;-)Basic number theory: Given x and y, their smallest positive integer linear combination spc(x, y) is given by sx + ty = spc(x, y) = gcd(x, y). You just need to find the minimal cost subset such that spc(a1, a2, ..., ak) = gcd(a1, a2, ..., ak) = 1.Note that gcd converges quickly as the subset size increases, assume that integers in the subset are distinct.
•  » » » » 5 years ago, # ^ |   +3 Overkill or not, it's how that type of equations is called. Then again, anyone who has done a bit of number theory knows what a diophantine (I imagine the name doesn't sound horribly different in other languages) equation is, not to mention linear.
•  » » » 5 years ago, # ^ |   0 "A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n"Is there a proof for this?
•  » » » » 5 years ago, # ^ |   0 I can't find one right now, but this might help (see generalizations):http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
•  » » » » 5 years ago, # ^ |   0 Left side can be divided by GCD(a, b, ...), so should right.
•  » » 5 years ago, # ^ |   +8 Yes, you are right, the gcds are too big to do dp with them, but the right thing to do there is to note that the number of useful gcds is small enough (my calculation ended up being ~60000 different gcd's), so you can map them to 1-60000 and then do dp.
•  » » » 5 years ago, # ^ |   0 thanks! unfortunately, i'm not used to mapping and tried some tricks with big numbers, but they didn't work...i definitely have to learn how to map
 » 5 years ago, # |   0 Best message ever :v (And definitely, I didn't submit that -_- )
 » 5 years ago, # |   -19 thanks for A. sweatest shit I ever eaten...
•  » » 5 years ago, # ^ |   +4 WOW you have eaten shit ???
•  » » » 5 years ago, # ^ |   -36 -YES FROM YR MOTHERS BUTT
•  » » » 5 years ago, # ^ |   -15 Сum on!
•  » » » » 5 years ago, # ^ |   +27 Have you paid for Visual Studio ? :-)
•  » » » » » 5 years ago, # ^ |   +11 Yep, obviously, and for uTorrent too
•  » » » » » » 5 years ago, # ^ |   0 and Sublime :D
•  » » » » » 5 years ago, # ^ |   0 It's freely available to students (under some usage restrictions). Say, if you have ISIC card (or another proof of enrollment), you are eligible for DreamSpark program which includes a lot of Microsoft software free of charge (not for commercial usage, of course).
 » 5 years ago, # |   0 Div1 AWhat's the answer for: 2 aa aa ?
•  » » 5 years ago, # ^ |   +6 All the names are distinct.
•  » » 5 years ago, # ^ |   +6 There is no equal strings.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 names should be unique
•  » » 5 years ago, # ^ |   +3 Didn't the specs say that the words are different?
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Sorry, didn't notice that. I thought it will fail. Whew.
•  » » 5 years ago, # ^ |   +4 This problem can be solved by graph cycle detection, right? I didn't have time to finish the code.
•  » » » 5 years ago, # ^ |   +5 Cycle detection -> impossibleElse, topsort
•  » » » » 5 years ago, # ^ |   +1 i thought the same :) .
 » 5 years ago, # |   0 How to solve Division1 C? Task looks like a Euler path, but I don't know how to solve it.
•  » » 5 years ago, # ^ |   -8 Although i have not participated in the contest but i think this problem can be solved using topological sort this way . Please correct me if i am wrong some where ..We can take each pair of string and find the first miss match then we put a directed edge from one character to the other (offcourse miss match pair is taken) then find whether there is a cycle or not in the graph . if there is a cycle then it is impossible otherwise find the topological sorting .
•  » » » 5 years ago, # ^ |   0 He asked for Div1-C, not Div2.
•  » » 5 years ago, # ^ |   +19 No, a set of cycles.You can notice that any two neighbours need to have different parities, so you have a bipartite graph describing possible neighbourings; you want to match each vertex of each partition to exactly two other vertices.
•  » » » 5 years ago, # ^ |   0 ai >= 2. Yep, only even lenght, I miss this restrict. Thx
•  » » » 5 years ago, # ^ |   +18 Is it correct to find one bipartite matching then remove the edges of this matching from the original graph and find a second matching? I wrote the solution and it passed the sys.tests, but I couldn't prove it's correct.
•  » » » » 5 years ago, # ^ |   +61 It's not correct. Try test:610 2 26 5 3 9or its permutations. System tests are weak.
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   +16 UPD: The following proof that we need two perfect matchings is correct, but finding two perfect matchings sequentially does not always work."=>"Each breakdown of graph into cycles can be divided into 2 sets of edges, "left-to-right" and "right-to-left". Each node from left and right part has exactly one edge of each type incident to it. Therefore, each of such sets of edges forms a perfect matching."<="For a pair of two edge-disjoint perfect matchings we get a set of edges such that each node has exactly two incident edges. Since the degree of each node is even, there exists an euler tour in each connected component. Each connected component has exactly K nodes and K edges, therefor the tour is also hamiltonian. Since each node has at least two edges, each component has > 3 nodes.
•  » » » » » » 5 years ago, # ^ |   +13 A flow solution finds this order: 1 5 3 4 2 6
•  » » » » » » » 5 years ago, # ^ |   +16 Ah, I see. So the idea about two perfect matchings is correct, but finding them sequentially does not always work.
•  » » » » » » 5 years ago, # ^ |   0 The answer exists:9 10 3 26 5 2
 » 5 years ago, # | ← Rev. 2 →   0 For D1-A, what is the correct answer for this case? 26 a b c ... z According to this sentence: But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!Should the answer be Impossible? Since you cannot do any modification to make them lexicographical...I think this problem is ambiguous on this case. Could the author clarify?Edit: well my solution outputs abc...z on this case. However, my friend's outputs Impossible, because he was struggling to resubmit his hacked solution on this multiple times without success, to the point that he thought the wording of this sentence was actually the tricky case.
•  » » 5 years ago, # ^ |   +10 Identity modification :).
•  » » 5 years ago, # ^ |   0 some modification usually means no modification too.
•  » » 5 years ago, # ^ |   +3 No the answer is just the normal alphabet. I think this is pretty clear.
•  » » 5 years ago, # ^ | ← Rev. 5 →   0 Aren't they already lexicographically sorted? Edit: Oh, I see what you mean.
 » 5 years ago, # |   +6 Did somebody made mistake of writing "Impossible" as "impossible"? :P
•  » » 5 years ago, # ^ |   0 would that pass the pretests?
•  » » » 5 years ago, # ^ |   0 Of course, no.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Obviously not, as the answer for one of samples is 'Impossible' :)
•  » » 5 years ago, # ^ |   +8 Me!
•  » » 5 years ago, # ^ |   +1 I accidentally wrote impossibru though
•  » » 5 years ago, # ^ |   0 i made mistake of writing "YES" instead "Yes" :)
 » 5 years ago, # | ← Rev. 2 →   0 How is Div1 B solved?
 » 5 years ago, # |   +9 Thanks a lot for the nice C problem :) It is clear experienced coders must have seen it before but I was happy once I figured out the max flow solution. Then, I ran out of time because I didn't know how to restore the flow, and had to spend some time debugging >.<
 » 5 years ago, # |   +126 Very nice problems cgy4ever, thank you :)!
 » 5 years ago, # |   0 Thanks for this round. Though my rating will decrease I learnt a lot . Hope you will be setting problems frequently .
 » 5 years ago, # | ← Rev. 2 →   +8 Did anyone else wrote randomized algo for Div1 E? (・_・ヾ If my solution pass, I would probably look like (☉_☉')Edit: It failed (˘_˘٥)
•  » » 5 years ago, # ^ |   +3 DamianS got his random solution accepted.
 » 5 years ago, # |   +3 What a bloodbath on div1 A! I missed the opportunity of being hacked.
 » 5 years ago, # |   -11 My code (codeforces.com/contest/512/submission/9686628) got accepted but it writes "Impossible" with this simple input: 2 a a :))
•  » » 5 years ago, # ^ |   +3 Because all strings are different :)
•  » » 5 years ago, # ^ |   +3 2 a a is wrong test: "All names are different."
 » 5 years ago, # |   0 Thank you for such a wonderful contest!!
 » 5 years ago, # |   +13 Finally in top 5! Congratulations to winners and big thanks to those who created this nice contest for us.
 » 5 years ago, # |   +11 Best contest since I am on codeforces :) Thank you :)
 » 5 years ago, # |   +15 Codeforces was working perfectly during last 10 minutes. I've read so many codes, challenged so many people during that time! To help u guess how many, i say that factorial of this number is 1
•  » » 5 years ago, # ^ |   +5 so 0 or 1 ?
•  » » » 5 years ago, # ^ |   0 Contests -> Click at place.0
 » 5 years ago, # | ← Rev. 2 →   +1 Great contest with good problems,I just didn't know about 'topological sort' before the contest,and learn it during the contest ;)
 » 5 years ago, # |   +32 Very nice problems. And finally I can become international grandmaster, really excited!
 » 5 years ago, # |   +22 My short sad story:I had A and B and it was like 15 minutes to the end. I didn't have any good idea for C/D/E so I wrote some simple greedy-random solution to E but I wasn't able to submit it during last 2 minutes. And now my code from contest passed all tests: link to solutionOfc. AC with this solution would be a bit unfair but still I'm just sad... 155-th place vs. ~24-th place :(
 » 5 years ago, # |   +1 Why is this Div 1 B solution failing the system test cases. Please Help. http://codeforces.com/contest/512/submission/9690331
•  » » 5 years ago, # ^ |   +3 So easy question... Cause answer was wrong :|
•  » » 5 years ago, # ^ |   0 Are you sure it's okay to modify the container which you are currently iterating over? I guess that could be the source of the bug.
•  » » » 5 years ago, # ^ |   0 I used unordered maps. So I guess it shouldn't modify the container which i am currently iterating over.
•  » » 5 years ago, # ^ |   +25 Iterators are invalidated when you insert into unordered_map: http://en.cppreference.com/w/cpp/container/unordered_map/operator_at. Try to replace by std::map.
•  » » » 5 years ago, # ^ |   0 My goodness :D ... I chose to use unordered_maps other than maps at the last moment... God has been very kind to me :D ....Thanks anyway for finding the bug :D
 » 5 years ago, # |   +6 Won't there be a rating change for this round?
•  » » 5 years ago, # ^ |   +9 Still Pending
•  » » 5 years ago, # ^ |   0 still same :)
 » 5 years ago, # |   0 My rating increased by ranking 266 ?!?!Whoa, and here I was regretting not realizing C was a flow problem sooner and complaining about how terrible my performance was...Though I wasn't fast enough to solve it during the contest, problem C was really nice. A very good contest overall!
•  » » 5 years ago, # ^ |   +8 Actually your rank was 266 and your rating increased by 90! :P
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 Exactly. I wasn't expecting that! After the contest finished, I could have sworn I was going back to purple...
•  » » » » 5 years ago, # ^ |   +5 Lucky you!
 » 5 years ago, # |   -37 Слабые тесты в задаче B первого дивизиона! Моя программа, получившая вердикт "Полное решение" даёт неправильный ответ на тесте: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1 числа l[i] сконструированы так : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. Поэтому наименьший набор l[i], имеющий наибольший общий делитель равный 1 содержит все 9 чисел l[i]. Поэтому правильный ответ на данный тест 9. Однако моя программа, зачтённая на codeforces даёт ответ 8 (не та программа, которая прошла претесты во время соревнования, а которая была отслана после окончания соревнования).
•  » » 5 years ago, # ^ |   -9 Что не так с моим комментарием?
•  » » » 5 years ago, # ^ |   +11 You wrote that comment in Russian, but posted it as English. Many people who use English version of CF see your comment and can't understand.
•  » » » » 5 years ago, # ^ |   0 Thank you.
•  » » 5 years ago, # ^ |   +9 Weak tests in problem B of Div.1! My program that got AC gives wrong answer on test: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1. Numbers l[i] are constructed so : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. So the least set of l[i], that has gsd equal to 1 contains all 9 l[i]. So the correct answer to the test is 9. But my AC program answers 8. This is my comment.
 » 5 years ago, # |   +9 Nice problem set :)
 » 5 years ago, # |   +2 DIV 1 C --> Awesomeness!! Thanks cgy4ever!! :D
 » 5 years ago, # |   -17 How this contest can be rated since I did not connected to codeforces at least an hour ? Is that just happened to me or everyone ? I can not send my solution to B because of the network problems and now I got -80 :( I WANT MY RATING BACK !!!
•  » » 5 years ago, # ^ |   0 Just to you. Codeforces wasn't running so smooth, but rest of people were able to send their codes and get the verdicts.
 » 5 years ago, # |   0 Russian page has no links to editorial nor winners of Div1 / Div2. If anyone can fix it then do it please.
•  » » 5 years ago, # ^ |   0 Added them in Russian version, but in English since I don't speak Russian.
 » 5 years ago, # | ← Rev. 2 →   0 Take a look at this solution of div.2 D/div.1 B please. Where is bug? (WA on 24th test)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +4 Here. for (int i = 0; i < N; ++i) { cin >> c[i]; dp[l[i]] = c[i]; } Nobody guaruanteed that l[i] is not in map already. You will just lose too much information if l[i] overlaps with another one.
•  » » » 5 years ago, # ^ |   0 Sure! Thanks for help.