MikeMirzayanov's blog

By MikeMirzayanov, 8 years ago, translation, ,

Hello!

Informal contest Codeforces Testing Round #2 is scheduled on 10/29/2011 01:00PM (UTC). We will test the latest innovations on Codeforces that they do not affect the contests. If not, we will fix it quickly :) So, this round will take place "as is", no warranty about it.

Problems for the round may be famous to someone, but I'll try to make them such not for any of you. It will be about 4 problems, as quite simple and something more tricky.

I say thanks in advance to all those who will come and test the system. Thank you!

The contest moved to start on 10/29/2011 01:00PM (UTC) (it has been announced to start on other time, be careful).

It will be unrated round.

Thank you all for your help. I think it turned out pretty fun for you and useful for us!

MikeMirzayanov
Announcement of Codeforces Testing Round #2

• +63

 8 years ago, # | ← Rev. 3 →   +3 Will it be rated?Edit: To those who minused this, when I originally asked this question, the "It will be unrated round" part wasn't present in the text above (this was added later), which is why I asked it.
•  8 years ago, # ^ |   +1 No.
•  8 years ago, # ^ |   +2 The difficult problem is for Div 1, Div 2 or both ?
 8 years ago, # | ← Rev. 2 →   -15 I have tried enough but I cannot understand problem C.Now taht the contest is over could someone explain me what the problem wanted to say.
•  8 years ago, # ^ | ← Rev. 3 →   +2 Find the largest complete graph with at most N edges.
•  8 years ago, # ^ |   +3 Yes, since a man can only be invited 0 or 2 times.At this view, a Day is actually a node, a man is an edge, the problem then becomes so obvious
•  8 years ago, # ^ |   0 It is amzing that it can tranform to this graph.How can you think this?
•  8 years ago, # ^ | ← Rev. 5 →   0 I didn't notice this until I saw hex539's post. I passed pro.C by a construction method something like: 1 2 3 4 5     1 2 3 4 5     1 2 3  4  5 1             1 6 7 8 9     1 6 7  8  9 2         =>  2 6       =>  2 6 10 11 12 3             3 7           3 7 10 4             4 8           4 8 11 5             5 9           5 9 12 ...
•  8 years ago, # ^ |   +5 I didn't notice this until I saw hex539's post. I passed pro.C by a construction methodsomething like:1 2 3 4 5     1 2 3 4 5     1 2 3  4  51             1 6 7 8 9     1 6 7  8  92         =>  2 6       =>  2 6 10 11 123             3 7           3 7 104             4 8           4 8 115             5 9           5 9 12 ...
•  8 years ago, # ^ |   0 For every pair of days (A,B) a person must be invited to both. But no person can be invited to more than 2 days.
•  8 years ago, # ^ | ← Rev. 4 →   0 I think it can be solved this way. For n=3 you have this solution:1 21 32 3You can extend this solution by adding the smallest number available (4).1 21 32 34Now, you have to "adjust" all the rows, in order to keep the property described in the statement.This is a way to do that:1 2 41 3 52 3 64 5 6This one is a valid configuration for n >= 6 (because you must have the 6th hobbit).Extending the solution to higher N is fairly simple:1 2 4 71 3 5 82 3 6 94 5 6 107 8 9 10(Valid for N >= 10)And so on...Here's an implementation: http://www.codeforces.com/contest/125/submission/816816
•  8 years ago, # ^ |   +1 1051 2 3 41 5 6 72 5 8 93 6 8 104 7 9 10every 2 lines at least have one same hobbit, and one hobbit can't be in 3 lines.
•  8 years ago, # ^ |   +1 Why the answer for 66 1 2 1 3 2 3 4 5 4 6 5 6is wrong?
•  8 years ago, # ^ |   +1 Yes, there is no common hobbits for 1st and 4th day.
•  8 years ago, # ^ |   +5 вновь туплю на ровном месте . . .
•  8 years ago, # ^ |   0 Problem C is special judge. And can be constructed in many ways , My method is that :For 3 :1  2  1         3     2    3For  4:1   2   3 1              4   5     2         4         6           3         5   6For 5:1   2   3   41                   5   6    7     2              5               8   9           3             6          8          10                4              7         9     10ans so on..Hope this may help you.
 8 years ago, # | ← Rev. 2 →   +3 Sorry wrong observation!.
 8 years ago, # |   +3 first i make unsuccessful hacking then i discover my A problem will fail because different values of output between my code and this code thenI make 8 successful hacking  with this value -->35code output 0 12 and the result have to be 1 0and also my code ouput 0 12 but passed system test :)
•  8 years ago, # ^ |   +1 SmartCoder
•  8 years ago, # ^ |   0 thanks, this thing happen to me before in last SRM topcoderi make code to problem 900 Div2 passed system test & you can make successful challenge to ityou can see this post Here try to write the passed system test code in arena and then challenge it :)
•  8 years ago, # ^ |   +1 I think your code failed system test as shown by this page.
•  8 years ago, # ^ |   0 yes i think admins make rerun to system test adding to it this hack.
•  8 years ago, # ^ |   0 Oh, bro, it's my failure too xDDhttp://www.codeforces.com/contest/125/standings/2/page/9
 8 years ago, # |   +1 please can someone explains how to solve problem D?Thanks in advance.
•  8 years ago, # ^ | ← Rev. 2 →   +1 The first element in any case goes to  the first sequence.Then for any two adjacent elements  we have 4 variants of their placement -  both in the first sequence, both are in the second one, or  first of them is in the first sequence or the first is in the second sequence.Every time we check each variant of partition, if at some stage we were not able to do so - no decision at all, otherwise continue. In the end we print the answer
•  8 years ago, # ^ |   +1 so will we do a backtracking to try each of the 4 variants or what ??
•  8 years ago, # ^ | ← Rev. 3 →   0 Did you guys ACed it to explain solution here?General idea is right, but I think many failed on, e.g., the following test:71 2 3 8 4 0 -4So, important thing: after finding the largest progression (by inclusion) for every two elements of the first three, you should check whether we get solution if delete first or last elements of the progression obtained (and, correspondingly, add them to the second progression).
•  8 years ago, # ^ |   0 out of first 3 numbers 2 will belong to a particular seq. rest is easy.
•  8 years ago, # ^ | ← Rev. 2 →   0 could you please explain the rest - it is not easy for me. if you know 2 numbers, say, A and B, from particular sequence, and there are lots numbers (2B-A) further in the sequence, how you deal with that situation. which one you take, which one - release for the second sequence?
•  8 years ago, # ^ |   +1 If there is a solution, one of the two progressions must have its first two elements among a[1], a[2], a[3].  That makes three separate cases to check.  Now, read the a[i] from left to right, put them in either one list or the other.  The problematic i are those for which a[i] could be in both lists.  If i=n, it doesn't matter which one.  Otherwise, look at the difference a[i+1]-a[i]:- If it's the difference of the first list, put a[i] in the first list. - If it's the difference of the second list, put a[i] in the second list.- Otherwise, a[i] is the end of the first list, a[i+1] is in the second.See my submission here; the first and second list are called b and c.
•  8 years ago, # ^ | ← Rev. 2 →   +11 a naive approach based on this observation is probably wrong try 7 0 3 4 5 6 12 18 you can't use greedy algorithm here, it will occupy [3, 4, 5, 6]and leave [0, 12, 18] unsolvable.
•  8 years ago, # ^ |   +9 I agree with bjin , my submission on D is wrong on this test but is passed the system test.
•  8 years ago, # ^ |   +10 I found the way how to skirt this around: after you bilt a candidate for answer (some progression largest by inclusion), try to check as an answer this progression without the first element, and this progression without the last element.
•  8 years ago, # ^ |   0 Why this can skirt this around? Is it another progression can only use the first element or the last element?
•  8 years ago, # ^ |   0 Yes. Try to understand why.
•  8 years ago, # ^ |   0 Since the greedy algorithm is not correct,I want to know what is the best solution.Thank you!
 8 years ago, # |   +5 I'm having trouble looking at source code sometime. Not sure this is a part of what you're testing but sometimes i get a blank view of source (nothing inside the white box... happened during the contest too when i was trying to hack) or it shows the source i lastly checked (which is not the one i clicked)... however when i refresh the page and click on it again it works no prob. But then when i check a couple of source codes more it happens again. I'm using chrome btw. Just wanted to let you know
 8 years ago, # |   +5 Is Pro.E = MST + cycle detection ??I've tried greedy approach which firstly selecting k capital road with min weight and select the rest non-capital roads with min weight, but it seems to be incorrect idea....
•  8 years ago, # ^ |   +5 K capital roads with min weight is WAe.g.k = 21 2 1001 3 1001 4 1102 3 1the right solution is (1,2),(2,3),(3,4)
•  8 years ago, # ^ |   +5 Then can anyone give some ideas Orz....
•  8 years ago, # ^ | ← Rev. 2 →   +5 The question in problem E is to find a minimum spanning tree, such that the degree of node 1 is equal to k.  It is easy to find if we don't have this additional constraint with k.  The trick is to modify the graph a bit so that the MST in the new graph is the one we are looking for.Separate all the spanning trees into groups, depending on the degree of node 1.Consider the MST within each group.What happens if you increase by the same value x all the weights of edges incident to 1? In group i, the MST is the same set of edges, but the optimal weight is now increased by i*x.So the optimal weight of group i+1 increases more than that of group i: (i+1)*x>i*xSo the MST of group k is the MST of the new graph with the right increment x.  This increment can be found with binary search.See the code by MBabin.UPDATE: systems test are a bit too weak; some solutions break on this example:4 3 32 1 623 2 34 2 27
•  17 months ago, # ^ | ← Rev. 3 →   0 Can anyone explain why this solution is correct?UPD:Sorry, I already understand.
•  15 months ago, # ^ |   0 Can you please explain me?
 8 years ago, # |   0 Problem C is special judge. And can be constructed in many ways , My method is that :For 3 :1  2  1         3     2    3For  4:1   2   3 1              4   5     2         4         6           3         5   6For 5:1   2   3   41                   5   6    7     2              5               8   9           3             6          8          10                4              7         9     10ans so on..Hope this may help someone that not so clear about C.
 8 years ago, # | ← Rev. 5 →   0 Try this input for problem D : 13-10 -5 0 1 2 3 4 5 6 7 8 9 10we can split this sequence , but output of many accepted solution's are "No solution".
 8 years ago, # |   0 For problem D, my solution is like this: i used pigeon hole principle: max of 3 element is enough to get a sequence, and if we analyze 5 elements, one of the sequence will definitely get 3 elements..so i made all the cases for 3 out of 5 elements. This way one sequence is fixed, if we cant get a match for a number in this sequence we will put it into another sequence if it fits there otherwise try next case. This is greedy approach. The only problem is when both the sequence allows a number and this will happen only once for a case...so a simple backtrack would work. My solution is here: http://www.codeforces.com/contest/125/submission/821110
•  8 years ago, # ^ |   0 tl;dr