By AlexFetisov, history, 5 years ago, translation,

In 6 hours 2nd Round of the VK Cup 2016 programming competition is going to happen! If you haven't registered for the round — don't worry! There is an extra registration!

The teams who has advanced from VK Cup 2016 Round 1 and VK Cup 2016 Wildcard Round 1 can participate in this round. The competition has regular Codeforces rules. Also in the same time with official round there is a regular rated Codeforces round played on the same problem set for participants from both div1/div2 divisions.

This round was prepared by AlexFetisov and winger. That is the first round which we have prepared as authors. We want to thank Gleb Evstropov (GlebsHP) for his help. Gleb is doing great job as Codeforces coordinator and I wanted to tell that one more time! Also we want to thank Kamil Debowski (Errichto), Mateusz Radecki (Stonefeang), Boris Minaev (qwerty787788), Pavel Kunyavskiy (PavelKunyavskiy) for their help in testing the problems and for great suggestions. Huge shout out for Mike Mirzayanov (MikeMirzayanov) for everything he has done for all of us!

To advance to Round 3 team should have a positive score and has score not less than the score of the 100th team in the final scoreboard. Also note that all teams advanced to Round 3 will get a special edition t-shirt of the competition. Also top-50 participants of the round 3 will get this t-shirt as well.

Good luck and have fun!

Update

Round has been finished. There were some problems during round but we hope that you enjoyed problems. Congratulations to the winners!

Official VK Round 2:

1. Whos On First Base!: -XraY-, ershov.stanislav
2. Beer and lemon tea: sankear, Zlobober
3. MYCOPOBO3: overtroll, LHiC
4. Never Lucky: subscriber, tourist
5. 33% less bad jokes: ifsmirnov, Arterm

Div1 results: Congratulations to anta who is the winner of this round div1 solving the hardest problem of the contest.

Div2 results:

Congratulations to alexrcoleman who is the winner of this round div2 solving all problems less than in an hour!

Announcement of VK Cup 2016 - Round 2

• +104

 » 5 years ago, # |   +10 Auto comment: topic has been translated by AlexFetisov (original revision, translated revision, compare)
 » 5 years ago, # |   +124 Stay away tweety :p .
•  » » 5 years ago, # ^ |   +4 lol
•  » » 5 years ago, # ^ |   +73
•  » » » 5 years ago, # ^ |   0 tweety :P
•  » » » 5 years ago, # ^ |   +5 Is this Silvistar???
•  » » 5 years ago, # ^ |   +34 now many participants wish tweety was here :p
 » 5 years ago, # |   -45 What the difference between the VK round 2 and the codeforces round. Like for example if a div 2 coder participated in the codeforces round and solved few problems can he participate in VK round 3 or do I have to participate in VK round 2 exclusively. And can't I just participate in VK round 2 AND codeforces round so if I solve a problem in one of them I solve 2 so my rating will go sky high. :-)
 » 5 years ago, # |   +31 "Also note that all teams advanced to Round 3 will get a special edition t-shirt of the competition. Also top-50 participants of the round 3 will get this t-shirt as well"Is there a mistake here?
•  » » 5 years ago, # ^ |   +44 "All teams advanced to Round 3 and TOP-50 participants of online-mirror of Round 3 will get t-shirts."(Translation from Russian)
•  » » » 5 years ago, # ^ |   -33 Does it make sense? Shouldn't it be TOP-50 from today's contest? Top participants from VK round 2 are awarded with shirts, so why unofficial round 3? Am I right?
•  » » » 5 years ago, # ^ |   +5 Does that mean I won my first shirt ever??
•  » » » » 5 years ago, # ^ |   +8 Nope, this was Round 2, and T-shirts will be devlivered in Round 3
 » 5 years ago, # | ← Rev. 2 →   -7 is Div 2 for Russian speakers only ?
•  » » 5 years ago, # ^ |   +14 No.
 » 5 years ago, # | ← Rev. 3 →   -74 .
 » 5 years ago, # |   -78 First: I have opened the announcement. Second: Ctrl+F Rated, Ok, then let's go on.
 » 5 years ago, # |   -64 Wtf?What is it???A rated CF contest???
•  » » 5 years ago, # ^ |   -55 Yes, will you participate?
•  » » » 5 years ago, # ^ |   -57 Yes, if I am still awaken at that time~~
 » 5 years ago, # |   -24 No skeleton images saying waiting .... till now . Wierd!
•  » » 5 years ago, # ^ |   +45 Skeleton is too busy throwing bombs ;)
 » 5 years ago, # |   -20 rated round??? is that an extinct dinosaur ???
•  » » 5 years ago, # ^ |   -21 Yes, though you should have read the above description. ;)
 » 5 years ago, # |   -23 The number of downvoted comments is too high!
•  » » 5 years ago, # ^ |   -42
 » 5 years ago, # |   -29 The first rated round in forever and I can't compete! This sucks lol. The wait for Friday begins.
 » 5 years ago, # |   +21 Scoring — standard or dynamic?
 » 5 years ago, # |   0 Wish Good Luck you all
 » 5 years ago, # |   0 nice problem in Div.2, 669D - Little Artem and Dance
•  » » 5 years ago, # ^ |   0 How to solve it.
•  » » » 5 years ago, # ^ |   +6 You can sum all the rotations and remember that value. And for swaps, only parity of the current rotation sum matters. When you do two swaps with the same parity, they cancel each other. So you simply need to count the final number t of non cancelled swaps, and the parity of the first swap in this sequences.Each number goes to t positions left or right, depending on the first swap parity and the parity of the number. And then you rotate the whole array by the sum of all rotations.
•  » » » » 5 years ago, # ^ |   0 Solved it in 5 minutes, spent the rest of the contest debugging. Fix a test another one fails, fix the other the first one fails. I wanna kill myself >_<
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   -24 very well , do it.maybe we will get more rated contests :v
•  » » » » » » 5 years ago, # ^ |   -12 Well that's rude...
•  » » » » » 5 years ago, # ^ |   0 Was similar for me. I had the solution which passed all samples and all my tests. But got 7 WAs. And 3 minutes before the end I realized that parity of the first swap matters, and managed to submit it.
•  » » » 5 years ago, # ^ |   +14 just store number of moves for odd positioned boy and even positioned boy and finaly calculate the position of all I don't know its right or not but it has passed pretest :)
 » 5 years ago, # |   +4 Was it possible to avoid TLE on problem D with a O(n+q) solution ?
•  » » 5 years ago, # ^ |   +30 I got TLE using even ios_base::sync_with_stdio(false);, cin.tie(NULL) and cout.tie(NULL)AC after switching to printf and scanf.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0
•  » » 5 years ago, # ^ |   0 At the end I did, but I had to buffer my readers and writers directly instead of using Scanner and StringBuilder.
•  » » 5 years ago, # ^ |   +8 How could we do in Python, then ?
 » 5 years ago, # |   +15 How to solve Div2E?
•  » » 5 years ago, # ^ |   0 Hash table mapping an integer to a binary search tree of integers.
•  » » 5 years ago, # ^ |   0 Hi, My solution was maintain a Binary index tree with unordered_map in each node, which is o(1) , then just do classical update, query on it.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +14 I used one Segment Tree for each unique value. Just store  ± 1 for each insertion/deletion and perform sum queries.
•  » » » 5 years ago, # ^ |   0 Shouldn't having a big array for each unique value memory limit?
•  » » 5 years ago, # ^ |   +1 I used STL map which maps each integer to a set of time.The solution passed pretest but it got TLE in Test case 11.I think that this solution take O(n*(log(n)^2)) Can you please tell me time complexity of the solution that uses segment tree or fenwik tree?
•  » » » 5 years ago, # ^ |   +8 Mine is O(nlog(n)) using Fenwick Tree
•  » » » » 5 years ago, # ^ |   0 Ok, Thank you. I tried another solution where I stored pairs of integers in c++ STL sets and this solution is O(nlog(n)) still it is giving time limit exceeded. Can anyone explain why the solution is slower than than other O(nlog(n)) solutions?
•  » » » » » 5 years ago, # ^ |   +10 Your submission is actually N^2; std::distance used on set iterators takes time linear in the distance between the two iterators.
•  » » » 5 years ago, # ^ |   +3 My solution with Segment Trees: 17494007This is O(NlogN)
 » 5 years ago, # | ← Rev. 2 →   +20 I have a doubt : Sometimes like today's D scanf/printf seems to perform exceptionally well over cin/cout. Though I was using ~~~~~ ios::sync_with_stdio(0); ~~~~~with no endl i.e. flushing of output yet my program ran in about 1.9 seconds changing cin/cout to scanf/printf reduced time by 3.What is the reason behind it? I lost more than 150 points due to re-submissions
 » 5 years ago, # |   +6 I realy don't understand why linear solution for D (O(n + q)) gets TLE...
•  » » 5 years ago, # ^ |   +4 You need very optimized I/O... this particular problem pushed the limits of what can be done in 2 seconds in that regard.
•  » » » 5 years ago, # ^ |   +11 I always use C#. And never got this problem before. Something went wrong today...Of course i will investigate the problem after systests. But I think time limit should be such that the solution has passed not only on C++...
•  » » » » 5 years ago, # ^ |   +1 I passed it with Java but needed to do several things I wasn't used to with the I/O (namely, use a BufferedReader directly instead of a Scanner, and use a BufferedWriter rather than println()ing a string made with a StringBuilder).
•  » » 5 years ago, # ^ | ← Rev. 2 →   +4 got 4 TLE on pretest 11, even by using ios::sync_with_stdio(0) on a O(n+q) solution. But as anh1l1ator told that scanf/printf were running on time, I think it was more of language based question.
 » 5 years ago, # |   +46 Am I the only one who consider that precision problems in div1C were more than annoying? I still don't consider I've made any mistake and I don't know why sometimes I get WA on pretest 8 sometimes on 9...The intended solution was with product and sum of the partial sums?
•  » » 5 years ago, # ^ |   -18 Div. 1 D maybe?
•  » » » 5 years ago, # ^ |   0 I don't think so. I was talking about div1C from unofficial contest. Maybe in official contest they were numbered some other way
•  » » » » 5 years ago, # ^ |   0 Oh, my bad :)
•  » » 5 years ago, # ^ |   +10 Its very weird. My solution with long double didn't pass pretests but when I changed it to double it did. B/w I also did the same thing.
•  » » » 5 years ago, # ^ |   +8 ... Nice avatar :)
•  » » » » 5 years ago, # ^ |   0 Thanks! you too :P
•  » » » 5 years ago, # ^ |   +23 My solution uses long doubles, fails pretests under G++, passes pretests under MS VC++ (when all else fails: change compiler :) ). Let's see after systests, though...
•  » » » » 5 years ago, # ^ |   +23 Btw, MSVC doesn't have long double type, it's the same as double on it.
•  » » 5 years ago, # ^ |   0 I also got a few WA on pretest 8. It seems it was because I was taking the square root of a negative number when it should have been 0.
 » 5 years ago, # | ← Rev. 3 →   +6 I tried to hack a solution with O(n) on problem A div2 but it was unsuccessful (n=10^9) :(why?!
•  » » 5 years ago, # ^ |   +4 If it was just a while loop with addition/subtraction it's more than possible they could have gotten a billion operations done in 2 seconds.
•  » » 5 years ago, # ^ |   +4 the same happened to me, I tried to hack a O(n^2) in B div2 and it passes!!!!!
•  » » » 5 years ago, # ^ |   0 I hacked O(N^2) solution succesfully.
•  » » 5 years ago, # ^ |   0 Some sort of compiler optimization?Like This
•  » » 5 years ago, # ^ |   +14 I try it on custom invocation and this is the result
 » 5 years ago, # |   0 How to solve problem 4 Div 2. i was encountering the problem when x is odd.
 » 5 years ago, # |   +10 I think ABCD should be circular-shifted.
 » 5 years ago, # | ← Rev. 2 →   +3 In problem B div2, little artem and grasshopper, second sample test 3 >>< 2 1 1  area starts from 1 and ends at 3.start from cell 1, jump 2 steps right, reach cell 3. direction is again right, jump 1 step ahead reach cell 4 and get out of the area. but the note in the problem says, Second sample grasshopper path is 1 — 3 — 2 — 3 — 2 — 3 and so on. can someone explain why?
•  » » 5 years ago, # ^ |   0 Because each cell had a direction and length associated with it... this was not a sequential list of commands but rather the grasshopper sees a sign on the cell giving the directions... the problem asked whether the grasshopper would ever step out of bounds or whether it would keep hopping in an infinite cycle.
•  » » » 5 years ago, # ^ |   0 In the example given, the grasshopper sees a sign on the first cell saying to go right 2. Then it sees a sign on the third cell saying go left one. The dutiful grasshopper then sees a sign on the second cell saying go right one. These last two loop forever, and hence the solution is infinite.
•  » » » » 5 years ago, # ^ |   0 understood, thanks.
•  » » 5 years ago, # ^ |   0 No you should move in the direction of the '<' in cell 3 you will back 1 cell so you will be in cell 2
•  » » 5 years ago, # ^ |   0 Initially You are at position 1. At 1 the direction is '>' and jump length is 2 therefore new position is 1+2= 3. At 3, the direction is '<' and jump length is 1, so the new position is 3-1= 2. At 2, the direction is '>' and jump length is '1', therefore the new position is 2+1= 3 and so on...I got MLE in my 17492812 . Can you debug it?
 » 5 years ago, # |   +80 Solution to problem E: #66TUPOI mean you really think it is a bit hard? Or I should expect some unexpected verdict?
•  » » 5 years ago, # ^ |   +3 Nice! I mapped each x to a segment tree :D
•  » » 5 years ago, # ^ |   +6 I didn't write the round, but it's the first thing came into my mind. Very straightforward. Even without this cheat, coordinate compression + fenwick trees don't make it less straightforward.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 This problem is very hard when you are shocked by unknown WA of C. (and this problem makes one angry, when you realize some crappy precision error was the one who blewed up such easy problems)Actually, I searched for your policy-based data structure article in contest — because n <= 1000000 and segtree solution will get MLE. (I calculated 240MB with dirty compression) sadly OSX clang can't compile gnu__pbds, so I used ideone to debug — it was painful.Soon it turned out that these efforts were useless because 1. n <= 100000 2. I read statements wrong.
•  » » » 5 years ago, # ^ |   0 I can't compile that either, but what I do is use a set and once I'm sure it works I just change the code to use the policy based ds, which should be around 2-3 lines, go into custom test and check if my code still works, worked fine for me during contest :)
 » 5 years ago, # |   +10 Too bad there wasn't a lot of hacking happening this round — strong pretests I suppose
•  » » 5 years ago, # ^ |   +1 problems were relatively easier than previous round #347
 » 5 years ago, # | ← Rev. 4 →   +46 Edit : Div2 A
 » 5 years ago, # | ← Rev. 7 →   +71 Div1 C: Also, probabilities should be non-negative and their sums should differ from 1 by no more than 10 - 6 I wonder, how many solutions will fail because of this case? Mine certainly will :/ EDIT: Actually, it seems like I passed.https://www.dropbox.com/s/08m764rlxuvnd6q/hack.txt?dl=0 Python 2 Generatorimport sys sys.stdout = open("hack.txt", "w") a = [] for i in xrange(12500): p = 8e-5 * (i + 1) q = 8e-5 * i a.append("%.8f" % (p * p - q * q)) print 12500 print " ".join(a) print " ".join(reversed(a)) 
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I will get WA too. I tested it on your hack and my program output all nan. It was meant to be purely a math problem, not a programming problem -_- EDIT: I somehow passed systests...
•  » » 5 years ago, # ^ |   0 Is there anything specific in this case? My solution works fine with it.
•  » » » 5 years ago, # ^ |   +8 I think people who use sqrt function in their solution will see something like 1.00007 and 0.999934 when they add up the sum of their output, which will be > 1e-6 error.
•  » » 5 years ago, # ^ |   +50 I can see that you did not make any hack with this case.. Thank you, I can still hope to pass systest! :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +90 Is that a good probability? They are produced by my solution that passed pretests :Pa[i]=15083328916245932279840823609130527921079628476947190293794832049848427950033787764642925414628390330310916731933701947465371533061711148760114759803382653601121625233155946862022851427067088008522984157822017083296402464626853429590473211951849790874316769424402880358084931661613943529882190463340932869005131383232439121936748517148328737418372810911926497042735900081847898594371012194165746830896795480609079081172302829734639014034645165655017825088703634305866700555015137682443072942387017868033906236880579419521133614288513156362590844990804612816574232074299859735223614812296545257397381507457860747751574308225499542843354186170024701235438344817574100140731253729526497350066797319223996129851165727915197654461897429418079299555662797004798095895094086282391980738121825921877282118365893597035261873904749959394553190509543153197575014620757453443744428830827654721563319109783119882310723355051640716023096845418774027557237149504187519938022673234264064.0000000000, b[i]=-15083328916245932279840823609130527921079628476947190293794832049848427950033787764642925414628390330310916731933701947465371533061711148760114759803382653601121625233155946862022851427067088008522984157822017083296402464626853429590473211951849790874316769424402880358084931661613943529882190463340932869005131383232439121936748517148328737418372810911926497042735900081847898594371012194165746830896795480609079081172302829734639014034645165655017825088703634305866700555015137682443072942387017868033906236880579419521133614288513156362590844990804612816574232074299859735223614812296545257397381507457860747751574308225499542843354186170024701235438344817574100140731253729526497350066797319223996129851165727915197654461897429418079299555662797004798095895094086282391980738121825921877282118365893597035261873904749959394553190509543153197575014620757453443744428830827654721563319109783119882310723355051640716023096845418774027557237149504187519938022673234264064.0000000000
•  » » 5 years ago, # ^ |   +16 What is the correct answer to this test? My solution said that there is no such one, because of negative discriminant(it is not precision issue).
•  » » » 5 years ago, # ^ |   +5 According to statement, The answer will be considered correct if each value of max(a, b) and min(a, b) probability distribution values does not differ by more than 10 - 6 from ones given in input. When each die has equal probability for each number that condition is satisfied. Specifically, 12500-sided dice with each number occurring with probability 8 × 10 - 5.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Yes, but that doesn't say anything about validity of the input. Values from the input should represent exact probabilities of min(a, b) and max(a, b). So I assume probabilities from your input are rounded probabilities for the dice you described.Problem would be way harder if you just had to find probability distributions such that min(a, b) and max(a, b) are within 10^-6 from ones given in the input.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 import sys sys.stdout = open("input.txt", "w") a = [] n = 12500 for i in xrange(n): a.append("%.20f" % (((i + 1) ** 2 - i ** 2) / 1.0 / n / n)) print n print " ".join(a) print " ".join(reversed(a)) This generator produces right probabilities. My solution works ok on such test.
 » 5 years ago, # | ← Rev. 2 →   +133 Announcement that n is up to 1e6 not 1e5 in D after 1h and 20 min passed, really --__--???EDIT: Ofc, I meant the other way around xD
•  » » 5 years ago, # ^ |   +14 Be happy it wasn't the other way around :)
•  » » » 5 years ago, # ^ |   +24 Actually it was.
•  » » 5 years ago, # ^ |   +37 Wait, it was the other direction. We announced it was 1e5 NOT 1e6. But still this is no ok (
•  » » 5 years ago, # ^ | ← Rev. 2 →   +10 well, not sure if changing TLs (in at least two problems) sliently is much better
 » 5 years ago, # |   0 When will system testing begin
 » 5 years ago, # | ← Rev. 2 →   -9 I don't know why i read rotation being done as right rotation instead of left rotation initially in Div 2 C.How to solve Div 2 D?
•  » » 5 years ago, # ^ |   +4 The relative positions of boys at odd position will remain same and boys at even position will remain same. So count shifts of odd places and even places individually. After counting, just check from which position you have to start.Code
 » 5 years ago, # | ← Rev. 2 →   +5 Why did this solution of mine get TLE on pretest #9 on problem div1C? (I can virtually see no way it will do worse than O(n))http://codeforces.com/contest/668/submission/17498093Or pastebin: http://pastebin.com/0hCpNWx6
•  » » 5 years ago, # ^ |   0 Could it be because of the use of cin, cout?
 » 5 years ago, # |   +4 Can not wait for system testing!
 » 5 years ago, # |   0 What was the pretest 4 Of Little Artem And Dance ?
•  » » 5 years ago, # ^ |   0 I don't know what exactly was the test case, but my solution which failed on test case 4 gives wrong answer on this test. 6 2 2 2 The answer should be 1 2 3 4 5 6
 » 5 years ago, # | ← Rev. 2 →   +111 I got TLE on pretest 3(problem F). I tried to optimize my code in ~20 min, finally found(after contest) my code failed on testcase n=1,k=1. T_T
•  » » 5 years ago, # ^ |   +48 My solution passed after fixing this small bug. T_T (what a sad story.
•  » » » 5 years ago, # ^ |   +19 I guess it was too difficult to find during the contest...
 » 5 years ago, # |   +2 Can anyone explain why this solution gets WA3 and this solution passes pretests?
 » 5 years ago, # |   +8 Can someone explain why my solution with scanf/printf gets WA on pretest 6 and the exact same solution with cin/cout passes the pretests?http://paste.ubuntu.com/16038368/http://paste.ubuntu.com/16038378/
•  » » 5 years ago, # ^ |   +32 I'm assuming it is because z is uninitialized.
•  » » » 5 years ago, # ^ |   +3 oh, you're probably right. I can't believe I missed that!
 » 5 years ago, # | ← Rev. 2 →   0 Can anyone tell why did I get MLE verdict on my solution of Div2B 17492812 ?
•  » » 5 years ago, # ^ |   0 No one can view your code now, so you have to wait after system test or you can write it on Ideone and give us the link
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Here it is in ideone Solution . Thank You
•  » » » » 5 years ago, # ^ |   0 Try this case: 7 >>><><< 1 1 2 2 2 2 1 
•  » » » » » 5 years ago, # ^ |   0 Can you please explain where did I mess up?
 » 5 years ago, # |   0 what was the pretest 6 of div2 C
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 -deleted-
•  » » » 5 years ago, # ^ | ← Rev. 10 →   +14 isn't the answer7 2 53 2 4?EDIT: so hard editing...
•  » » » » 5 years ago, # ^ |   0 Yes!,It's7 2 53 2 4
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 wow it seems that I interchanged rows and columns for some reason.So bad of meEDIT: now solved
 » 5 years ago, # |   0 Could anyone solve F with matrix-tree theorem? It seems possible but when unfortunately diagonal cell becomes 0 modulo 10^9+7 I cannot continue anymore...
•  » » 5 years ago, # ^ |   +1 I think the solution is based on tree decomposition. The tree width of this graph is very small.
•  » » » 5 years ago, # ^ |   -10 What makes you think the treewidth is small? I can't really construct a good example (always hard with treewidth) but it seems to me that you could make some very unfriendly graphs.
•  » » » » 5 years ago, # ^ |   +3 Because it's k.
•  » » » » » 5 years ago, # ^ |   0 The treewidth is k? How would you construct the decomposition? I'm guessing every time you add some vertex you want to put it in a bag with its k neighbours, but how would you build the tree?
•  » » » » » » 5 years ago, # ^ |   +3 Think of it as following: for k = 1 you will always have a tree for k = 2 you will always have a planar graph whose dual is tree (the graph where triangles are vertices and edge means that two triangles share a side) for k = 3 you will always have a 3-d structure constructed of several tetrahedrons sharing their faces. Its dual (the graph on tetrahedrons where edges denote that tetrahedrons share a face) is also a tree similarly, for k = 4, 5 you will get a tree on k-dimensional simplexes where two simplexes are connected if they share a (k - 1)-dimensional face
•  » » » » » » » 5 years ago, # ^ | ← Rev. 4 →   +3 Ah, I get it now, thanks :) Then the DP-state for a bag {v1, v2, ..., vk + 1} in the tree would probably be something along the lines of: for each partition of the bag into non-empty subsets: in how many ways can we create a spanning forest covering all vertices in the subtree rooted at the bag, according to the partition we are considering (that is, two vertices are in the same set in the partition iff they are covered by the same spanning tree). Does that make sense?EDIT: Nevermind, you overestimate the answer a lot this way, for some edge {u, v}, u and v may be in a lot of different bags together, and this way you're counting adding this edge (between two spanning trees) in a lot of different bags. You probably have to somehow single out the one vertex that is added each step.. I'll think about this some more :)
•  » » » » » » » » 5 years ago, # ^ |   0 Maybe solution can be obtained on the following way. DP over the tree decomposition. State is a bag + some tree that spans vertices from the bag. And in transitions one should preserve edges which are already added in the parent bag. Number of states would be N(k + 1)k - 1 ≈ 1.2·107 and one should be careful with transitions (perhaps some precomputing will help). Does it make sense?
 » 5 years ago, # | ← Rev. 2 →   -16 Gah... cin and cout in Div 2 DWell I guess lesson learned: Be wary if they put such an easy problem as a Div 2 D. It literally took me 3 minutes to think of. This means that there's a trap.
•  » » 5 years ago, # ^ |   0 Wasn't it obvious? The limits for q are too big.
•  » » » 5 years ago, # ^ |   -7 I used fast i/o with cin and still got tle :(
 » 5 years ago, # |   +159 It's TooDifficuIt to start system testing!
 » 5 years ago, # |   +89 Please start system testing, I wanna go to bed :-(
•  » » 5 years ago, # ^ |   0 me too! But i will wait system testing!
•  » » 5 years ago, # ^ | ← Rev. 3 →   -24 it's 12 pm in my regionUPD: 12 am
•  » » » 5 years ago, # ^ |   +34 It's 4 am in my region
•  » » » » 5 years ago, # ^ |   -8 You made me hopeful :)
•  » » » 5 years ago, # ^ |   +3 I think you mean 12 AM
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   -8 You are right
•  » » 5 years ago, # ^ |   +8 They removed the three contests from the contests' list, which is unusual...
•  » » » 5 years ago, # ^ |   0 This error is probably because wild card round 2 starts before the end of this contest
 » 5 years ago, # |   +66 Waiting for sys testing is worse than waiting for game of thrones season 6 :(
•  » » 5 years ago, # ^ |   0 is it!?
•  » » » 5 years ago, # ^ |   +102 Yes, it is worse
•  » » » » 5 years ago, # ^ |   +8 I had a doubt. When your were white then your handle was also white? o_O
•  » » 5 years ago, # ^ |   +10 Oh, atleast you know what it will start.Here
•  » » 5 years ago, # ^ |   +13 is it worse than waiting for rated contest?
 » 5 years ago, # |   +44 From now on, I will try not to trust problem setters' problem difficulty estimations.
 » 5 years ago, # |   +5 Wrote a wrong and unnecessary special case. FeelsBadMan
 » 5 years ago, # | ← Rev. 4 →   +25 when you find out that you mistyped m to n in problem A after the contest had finished.... CantGetAnyACWhyAmISoWeak
 » 5 years ago, # |   0 Problem B write too difficult to know :( :( At least for me... And I waste so many time to understand... Down to 1k5 again :(( :((
 » 5 years ago, # |   +19 Could anyone find the contest on contests page? Has it gone???
•  » » 5 years ago, # ^ |   0
•  » » 5 years ago, # ^ |   0 you can access them from here
 » 5 years ago, # |   0 waiting for t-shirt...
 » 5 years ago, # |   0 any hacks on Div2 B?
•  » » 5 years ago, # ^ |   0 3 >>< 2 3 2
•  » » » 5 years ago, # ^ |   0 Ouput: INFINITE ???
•  » » » » 5 years ago, # ^ |   0 yep.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 should it be infinite? UPD thanx
 » 5 years ago, # |   -6 what can be 6 test in problem C div2?
 » 5 years ago, # |   +19 Someone please tell me... is System Test starting or should I go to sleep? :(
 » 5 years ago, # |   +12 1:38 AM in Bangladesh. Still waiting! Hope
 » 5 years ago, # |   +1 In Div2D=Div1B it is algoritmically easy to find O(n) solution, but what the hell the bounds of input are of order 10^6?? Very intelligent method to make the problem more difficult:( Is it really interesting to play a game "Who didn't forget about scanf/printf?"?(I have 1964ms on pretests using cin-cout with standard accelerators and I noticed that it is so close to TL only after the end of the contest.)
 » 5 years ago, # |   +46 4:46 AM here, wating for system test.By the way, my mid-term exam starts at 1:00 PM..... (cries)
 » 5 years ago, # |   +9 System testing of div 2 finally started!
•  » » 5 years ago, # ^ |   +37
•  » » » 5 years ago, # ^ |   +3 I am rather waiting for tutorial...
 » 5 years ago, # | ← Rev. 4 →   0 I had some difficulty in understanding DIV 2 E / DIV1 D's problem statement.1 1 12 3 13 2 1Should the answer of this case be 1 or 0?
•  » » 5 years ago, # ^ |   0 The answer is 1.You add the number at time 1 and remove it at time 3. So the number is in the multiset at time 2.
 » 5 years ago, # | ← Rev. 2 →   0 I got TLE in fourth task. I think it isn't possible. My complexity is O(n+q) + I done it in Pascal and I don't have bad loops.My code
•  » » 5 years ago, # ^ |   0 same happened to me. I think we needed to use fast I/O
•  » » » 5 years ago, # ^ |   -8 This is really bad. My appeal to codeforces to check it again.
•  » » » » 5 years ago, # ^ |   +4 they should have mentioned to use faster I/O but there were 4*10^6 IO operations
•  » » » » » 5 years ago, # ^ |   0 Can I use fast I/O in Pascal ?
•  » » » » » » 5 years ago, # ^ |   0 Try delphi.
•  » » » » » » 5 years ago, # ^ |   0 I am not supporting the authors , i am just saying that faster I/O was needed for this problem
•  » » 5 years ago, # ^ |   +1 I got TLE too, fast I/O was needed I believe. I always trusted in codeforces servers but it looks like reading and writing 10^6 numbers isn't fast in off using cin/cout even here.
 » 5 years ago, # | ← Rev. 3 →   0 why did O(n+q) get TLE in div 2 D? And we weren't even given any warning to use faster I/O :(
 » 5 years ago, # |   +10 System testing pausing at 95% is like watching a football penalty shootout and boom, there comes the blackout. T^T
 » 5 years ago, # |   +109 Frankly saying, it would be good to have it unrated XD (inb4 I'm 29th, so that's not that bad). That one zero too much in D's (or E's) was really something with very bad influence on contest (n<=1e6 and TL=1s doesn't look like even n log n should pass and it was announced after 2/3 of contest has passed) and tests to C were really weak. I got AC in C, however in test posted by FatalEagle here my solution produces completely shitty output and I expect a big part of solutions having similar precision issues which are really hard to omit in that problem (which is pretty sad, that makes this problem a bad fit for a contest).
•  » » 5 years ago, # ^ |   +33 Also using cin and cout with ios_base::sync_with_stdio(0);cin.tie(0); passes pretests in div1B but fails system tests...
•  » » » 5 years ago, # ^ |   +16 I got lucky, because I got TLE on pretests xD. But if it is the case for some people then it really sucks.
•  » » 5 years ago, # ^ |   -10 On FatalEagle's test case, I got WA too. In addition, it took about 5 seconds to run, and n=12500,so I have no idea how I didn't get TLE for n=1e5.
•  » » 5 years ago, # ^ |   +38 I am getting a deja vu. Tweety is that you?
•  » » 5 years ago, # ^ |   +83 And I used to think that people in Poland find giving TL=1s, n<=1e6 for NlogN solutions completely OK, after looking at some of your problemsets :)
 » 5 years ago, # |   +78 Let us be able to practice please.
 » 5 years ago, # |   +10 How to solve E(about 2-SAT)?
•  » » 5 years ago, # ^ | ← Rev. 11 →   +13 Build directed graphs like what we usually do in a 2-SAT problem.Claim: If u is reachable from not u, u must be true. After you deal with these variables, you can assign other variables in any order you like.First you should check whether they are satisfiable. If both of them are satisfiable, check whether there exists a vertex pair (u,v) s.t. v is reachable from u in one graph but not the other. Then set u=True and v=False, and find a solution in the graph where v is not reachable from u. I haven't got AC though :p Edit: AC :)Note: I use bitset to build the transitive closure too.
•  » » 5 years ago, # ^ | ← Rev. 4 →   +20 Suppose that both expressions are satisfiable. Let's try to find a solution for the second expression that doesn't satisfy the first one (then we can swap the expressions and repeat this again).If the set of variables doesn't satisfy the first expression, there should be a clause which is equal to false after substitution. Let's iterate over all clauses from the first expression and try to find a solution of the second expression which makes this clause's value equal to false. If the clause of the form (a or b) is false, we know the values of these variables (in this case they should be both false). So we need to check whether there exists a solution for the second expression in which the values of these two variables are fixed. Let S(a) be the set of nodes that can be reached from vertex a in implication graph (the graph where each variable has 2 vertices and where we add edges !a -> b and !b -> a for each clause (a or b)). What we need to check is whether contains both x and !x for some x.We can use bitsets to find transitive closure of the graph and also we can use them to check if contains a pair of x and !x. If it doesn't, then we know there exists a solution where the values of the given two variables is fixed and we just need to find any such solution. First, we need to fix values of the variables reachable from a and b. Then we can repeat the following: pick any variable which is not fixed yet, try to fix any value for it and then fix all values of the variables reachable from it. If there's a contradiction, flip the value of the current variable and repeat the process again. Note that we don't need to do dfs for this as we already have transitive closure computed.Overall complexity is O(N3 + M·N) which is fast enough if you're using bitsets (my solution got AC with time 378ms).
 » 5 years ago, # | ← Rev. 4 →   +111 This is my first win on a rated (don't make it unrated please) Codeforces round ever!In problem F, my solution will fail on a test case that their answer is 0 (a multiple of 10^9+7) (I could add one line to fix this bug). Can anyone construct a hack input?PS: I was wrong. The condition of the bug of my solution is not just "answer is 0" but that must satisfy a specific condition in addition to that.
 » 5 years ago, # |   0 Why can't I submit solution to problem E now?
•  » » 5 years ago, # ^ |   0 Because they didn't enable the practice mode yet
 » 5 years ago, # |   +22 Please don't make this round unrated. As is codeforces has very few rated events nowadays. Yes there was a minor issue with testing in problem C, but when people take time out of their schedule for a rated contest, it's really disappointing to see it made unrated just because the problem setters didn't make good tests for one problem.
•  » » 5 years ago, # ^ |   +20 Rating has already been changed :)
 » 5 years ago, # |   +8 Tutorial please !?
 » 5 years ago, # |   +118 Was reading comments... All these people saying things like "oh lord so many numbers, i'm too slow for it", "it's not right", "it's not fair!!!!!", "oh look at me I'm little girl and bad authors gave me too much numbers", "CF servers isn't good enough to provide fast I\O so my perfect solution pass all systests". Guys, are you OK? It's your problem that you didn't know that 4·106 I\O operations work not really fast. It's only your problem, not author's fault, not CF's slowness, it's your amateurism, that's all. If you want to improve your skills, stop crying like a little girls, blaming everybody for you fails and start learning from your mistakes.When I started to code on Java, I looked through code of people with high rating, found out some hints and of course took fast I\O from Petr's code. And I'd never had problems with I\O. Same with C++: when i started to use this language, Burunduk1 showed me his fast I\O template, I really liked it, and since then I use it almost always. It's nice and several times faster then usual I\O, so I never think about I\O time.What about contest... I hate myself so much! I ruined it for my team by planting amazing bug in my C solution. if (x % 2 == 1) changeParity(); See what's happening here? That's right, bullshit (-1 % 2 == -1). And I was searching for this bug more than a hour of contest. My teammate also wasted a lot of time helping me. Finally I wrote stress-testing and first test with query 1 -1 failed my solution. In conclusion I would like to say that contest was good, problems were interesting, just don't understand why E is E, but it doesn't really matter, such things happen sometimes and don't spoil anything. Thanks to authors! Now looking forward to marathon, hope I'll have chances there.
•  » » 5 years ago, # ^ |   +14 Thanks! That comment made my day :)
•  » » 5 years ago, # ^ |   +18 I used x & 1 instead of x % 2 so hadn't any troubles :D
•  » » » 5 years ago, # ^ |   +1 Oh, i told this short stupid boring story to my teammate after contest:In my Java-days I was always using bitwise operations, because it worked faster. But in C++ x /= 2, x *= 4 and all other similar operations work the same time, because of compiler optimizations. So when I started using C++, I stopped using bitwise operations and began to use usual operations, because it looks clearer and more logical, as for me. And today, when I was writing this if, at first I wanted to write x & 1, but then said to myself: "Come on, boy, why do you need to do this? Use division, it looks nicer, but works just as well". So I agreed with myself and wrote x % 2 with stupid smile on my face (I'm sure it was stupid).
•  » » 5 years ago, # ^ | ← Rev. 2 →   +64 Come on, why should "little girl" know when this freaking CF compiler work slow(Normal gcc's IO is not as slow, with speed approx. the same as scanf), which functions it doesn't support just because it doesn't (I'm about to_string, for example), etcAfter all, that's an algorithmic competition, where ability to construct algo's is intended to be checked not the knowledge of pitfails of specific wierd compilerPS: checked all your public c++ submissions, and didn't see anything like fast template.
•  » » » 5 years ago, # ^ |   -26 Normal gcc's IO is not as slow And what if next contest will contain a problem with 107 I\O operations? You'll also be talking about freaking CF compiler getting TLE with cin\cout? What does "Normal" mean? On your computer? I think you know that CF servers are not your computer, maybe have different compiler options and for sure different perfomance. So if you see some weak parts of your code which can cause some negative verdict, you should perform actions to prevent it. I think none of people who was thinking about I\O time on contest and knew how to read and write numbers fast didn't have problems with it.In my opinion, it would be more correct to say "Competitive Programming". Programming. So to participate well you need to know your language well: speed of I\O, precision of sqrt and all other features, which can be abused by problem's authors. And I also think that's sometimes authors must give problems which requires accuracy or maybe even additional efforts while using some usual built-in methods, so people know how does their language work and not just write some keywords having no idea why does it work.I don't know what did you check, my last public submissions contain it. For example: 17076273
•  » » » » 5 years ago, # ^ |   +40 Normal means this one and it means on pretty much every Linux or MacOS computer(and probably any other PC that support gcc itself)There's a difference between the language and compilers, you know.Your submission was not shown in submission tabs because it's unofficial one anyway, you said you've used in
 » 5 years ago, # |   0 How can Div2 D be solved?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +16 I solved it this way:Notice that, no matter what operation you do, the odd and even numbers will always be in increasing order ({1,3,5,7,...}, {2,4,6,8,...}) (in a circular fashion), and the whole array will never have two consecutive even or odd numbers.So you can keep track of where the 1 and 2 are after all the queries. Then you can deduce the position of the other elements.
•  » » 5 years ago, # ^ |   +6 Let’s notice the following: offset is the same for all elements of the same parity when a swap operation happens, we have to swap the offsets for odd and even guys, adding or subtracting 1 to denote the swap when a shift operation happens, we simply have to add the same number for both odd and even offsets and swap them if the shift value is odd. Then all we have to do is print the offset values for each guy, remembering to do it in a fast way, as n can be big enough for iostream to be too slow.
 » 5 years ago, # |   0 Why are we still not allowed to practice?
•  » » 5 years ago, # ^ |   0 You can submit on VK Cup 2016 — Round 2. Note that the problem order may be different.
 » 5 years ago, # |   0 Auto comment: topic has been updated by AlexFetisov (previous revision, new revision, compare).
 » 5 years ago, # |   +27 I am not able to see others code. Is it just me or is it not unlocked yet?
 » 5 years ago, # |   +68
•  » » 5 years ago, # ^ |   +14 newbie question: after contest, looks now I can only view myself's source code? when I try to click other people's submissions, I can not view the source code? is there any way to view other people's source code? thanks.
•  » » » 5 years ago, # ^ |   0 I think soon it will be possible.
 » 5 years ago, # | ← Rev. 2 →   0 How to solve Div2C ...I am getting WA at pretest 6 ....Don't know Why ??Again .... I don't understand the Second Test Case of Sample . Can someone help please ... Thanks in Advance .
•  » » 5 years ago, # ^ |   0 Got AC .... Thanks to liuweiming1997
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 How did you solve it same is happening with meEDIT: now it's solved
 » 5 years ago, # | ← Rev. 3 →   -27 WTF?! Is E is actually E?! I didn't read it during contest because I thought that it was something like Div.1 E. After contest I read it and just wrote solution in 5 minutes using std::map >.I will always read all problems during contest... :-(
 » 5 years ago, # | ← Rev. 3 →   0 Someone please share your code of Div2 C so that others can find answers to their test case.Thanks.My CodeNow we can see others code!
•  » » 5 years ago, # ^ |   0 Stuck in Test Case 5! Can anyone help? Div2 C!
•  » » 5 years ago, # ^ |   0
•  » » 5 years ago, # ^ |   0 My code for Div 2 CLittle Artem And MatrixWhenever you encounter a query of type 3,traverse backward all 1 and 2 type queries and undo their effect by finding the offset to be added in the given r,c where we need to assign x.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +1 for those who are having trouble in testcase 6 try this 2 2 6 1 2 2 1 3 1 1 1 3 1 2 2 3 2 1 3 3 2 2 4 correct output: 3 2 4 1 
 » 5 years ago, # | ← Rev. 2 →   0 Hi what's wrong in my code why is it not passing testcase 6 solutionEDIT: now it is solved
 » 5 years ago, # |   +8 @AlexFetisov: It should be noted that mkisic also solved everything within an hour :) KILE ANIMAL!
 » 5 years ago, # |   -10 Problems were really good. but getting TLE (in problem B Div1) because of not using "scanf" was really unfair! I used cin/cout without syncing with stdio and got TLE...
•  » » 5 years ago, # ^ |   +18 I think something is strange going on in CF compiler or server. On my PC scanf/printf works as fast as cin/cout.
 » 5 years ago, # |   0 In Div-1 C, when we are solving the quadratic equation to calculate the probabilities of the two dices, can we select either one of the two roots as the required probability, or does it matter which root we select?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +15 It can be easily proven (Well I didn't think about it, I just realized) that this equation either has one answer or one of its answers are not valid (and it is 0 I guess). But in the first equation there are two answers which are the two numbers we want. (Because of symmetry).Many people failed this problem (including me) because sometimes we encounter sqrt(0 — eps) which is produced by double errors and the return value will be nan instead of 0.
•  » » » 5 years ago, # ^ |   0 How can we prove that only one of the answers is valid?
•  » » » » 5 years ago, # ^ |   0 I didn't prove and maybe I'm wrong, as I said before I just guessed :-D, also I think if there exists another valid answer, we can continue from that and find anohter answer for the problem which is a valid one.
 » 5 years ago, # | ← Rev. 2 →   +1 in problem B div2, when I run this code in my computer gives correct answer "INFINITE", but, when codeforces run this code gives "FINITE" and I receive WA.this problem happens in the Test Case 2. someone can explain to me? 3 >>< 2 1 1 `17484721
•  » » 5 years ago, # ^ |   0 Hi replacing scanf with cin seems to do the job.I guess it was some kind of sync issue as you used both iostream and stdio in the program.17511620
•  » » 5 years ago, # ^ |   -8 Change %Ld to %I64d.Accepted
 » 5 years ago, # |   0 There is something that i thought was weird during the last round after solving the A&B problems it locked to try hacking other solutions and when trying to open the submission i couldn't so i tried to open and see the hacks and i could see no hacks was there something special about this round that i missed or was there something i did wrong on my behalf?
 » 5 years ago, # |   0 Hi everybody. Why ubuntu581's all codes are skipped in Vk Cup Div2 Raound?
 » 5 years ago, # |   0 Please somebody explain in details how to solve div-2 problem D?