MikeMirzayanov's blog

Codeforces Testing Round #2
By MikeMirzayanov, 13 years ago, translation, In English

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
  • Vote: I like it
  • +63
  • Vote: I do not like it

Comments Comments (44)
| Write comment?
13 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

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.

→ Reply
  • 13 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    Find the largest complete graph with at most N edges.

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      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
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        It is amzing that it can tranform to this graph.How can you think this?
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 5   Vote: I like it 0 Vote: I do not like it

          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 ...
          → Reply
        • 13 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it
          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 ...
          → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I think it can be solved this way. For n=3 you have this solution:

    1 2
    1 3
    2 3

    You can extend this solution by adding the smallest number available (4).

    1 2
    1 3
    2 3
    4

    Now, 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 4
    1 3 5
    2 3 6
    4 5 6

    This 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 7
    1 3 5 8
    2 3 6 9
    4 5 6 10
    7 8 9 10

    (Valid for N >= 10)
    And so on...

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    10
    5
    1 2 3 4
    1 5 6 7
    2 5 8 9
    3 6 8 10
    4 7 9 10
    every 2 lines at least have one same hobbit, and one hobbit can't be in 3 lines.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Why the answer for 6
      6
1 2
1 3
2 3
4 5
4 6
5 6
      is wrong?
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Sorry wrong observation!.

→ Reply
13 years ago, # |
  Vote: I like it +3 Vote: I do not like it
first i make unsuccessful hacking then i discover my A problem will fail because different values of output between my code and this code then
I make 8 successful hacking  with this value -->35
code output 0 12 and the result have to be 1 0
and also my code ouput 0 12 but passed system test :)

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    SmartCoder
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      thanks, this thing happen to me before in last SRM topcoder
      i make code to problem 900 Div2 
      passed system test & you can make successful challenge to it
      you can see this post Here 
      try to write the passed system test code in arena and then challenge it :)


      → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I think your code failed system test as shown by this page.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      yes i think admins make rerun to system test adding to it this hack.

      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Oh, bro, it's my failure too xDD
    http://www.codeforces.com/contest/125/standings/2/page/9
    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
please can someone explains how to solve problem D?
Thanks in advance.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      so will we do a backtracking to try each of the 4 variants or what ??
      → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Did you guys ACed it to explain solution here?

      General idea is right, but I think many failed on, e.g., the following test:

      7
      1 2 3 8 4 0 -4

      So, 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).
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    out of first 3 numbers 2 will belong to a particular seq. rest is easy.
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        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.


        → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      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.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it
        I agree with bjin , my submission on D is wrong on this test but is passed the system test. 
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it
          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.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Why this can skirt this around? Is it another progression can only use the first element or the last element?
            → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Since the greedy algorithm is not correct,I want to know what is the best solution.Thank you!
        → Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
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
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
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.... 
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    K capital roads with min weight is WA
    e.g.
    k = 2
    1 2 100
    1 3 100
    1 4 110
    2 3 1
    the right solution is (1,2),(2,3),(3,4)
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Then can anyone give some ideas Orz....

      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it


        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*x

        So 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 3
        2 1 62
        3 2 3
        4 2 27


        → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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 
→ Reply