DBradac's blog

COCI 2016/2017 round 2
By DBradac, history, 8 years ago, In English

Join us this Saturday on the 2nd round of this year's COCI!

Click to see where the coding begins in your timezone.

We can discuss the problems here after the contest.

  • Vote: I like it
  • +64
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

This is the first time I'm taking part in COCI. When I submit my code and it shows "Passed", has it been run on all cases, or only the samples given in the problem statement (will system testing be done later)? Also, how can I see the leaderboard/ranklist if available? :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Just the samples. You can only see the results(yours, and other's) when the contest ends.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      When exactly does the results come out?

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If I submit multiple times will all my submissions count or only the last one.

→ Reply
»
8 years ago, # |
  Vote: I like it +16 Vote: I do not like it

How to solve E and F? For F I tried some "smart" greedy solutions, I hope it gets enough points :D

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Fact in F, if k is more than 20 then the answer is yes, i didn't prove it but had a really strong intuition that thats correct, you can do a greedy like thing — then the problem will be dfs dp bitmask, there's always a solution that marks points with heights 2 3 4 ... k, (delete every vertex that its height is more than k + 1 and every vertex such that it doesn't have any descendant that its height is k + 1), so do bitmask on those heights the dp is on starting and ending time of the vertices (just do a dfs and update the dp while entering a vertex and leaving it)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Let me guess, at each level from 2 to k+1 you mark the node that can be reached and which is the widest?

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 6   Vote: I like it +18 Vote: I do not like it

    I am the author of problem F. Believe me, I spent a lot of time making tests against such greedy solutions and most of them didn't get many points. However, unfortunately, there was a randomized solution that got full score :(. Also, congrats to Reyna, he was the only one who had the intended solution and Laakeri who solved it in better complexity than the official solution!

    The solution goes something like this: We can ignore all nodes that don't have a node on depth k in their subtree (this includes the nodes with depth greater than k). Now let's examine the following greedy strategy: let f(v) denote the lowest depth for which a descendant of v has more than one child. In i-th move we will remove a reachable node v on depth i with the lowest value f(v). This solution isn't optimal, but it can be proved that if k2 ≥ n, it will always work.

    This means that we only need to worry about the case where k2 < n, i.e. k < 20. Now we can start thinking about non-polynomial solutions!

    Obviously, it is optimal to mark a node on depth i, on the ith move. Assign each node on depth k with an integer, in the order of their dfs traversal. Now, the problem can be solved using dynamic programming. Let dp[T][mask] denote whether we can "cut off" all the nodes at depth k with index less than T, and mask is a bitmasks which shows the moves we made (i.e. the depths of the marked nodes). The relation is whether we mark a certain node, and we only need to consider a node for one value of T, so the overall complexity O(2k * n)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks! Your comment, combined with Reyna's answer made everything clear expect for the proof. I hope there will be a proof in the tutorial :)

      PS: I got 32 with my greedy, I think karma reached me because I somehow idiotically missed exactly 32 points on the second task :D :D :D

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        We can prove it using induction over k.

        Let's say that using the greedy algorithm described above, d is the smallest integer such that after making d moves there is a node v with f(v) = d that is not cut off. If there isn't such a number, then we are done, because in each move we have removed at least k nodes from the tree(counting those above and below the marked node).

        Now, after d moves, we removed d nodes with f(v) ≤ d. This means that each time we removed at least d + 2 * (k - d) nodes(d nodes at depth d or lower, and at least 2 * (k - d) at greater depths, because there is more than one branch that goes till depth k). Now we have k' = k - d, n' ≤ n - d * (d + 2 * (k - d)).

        These inequailties give k'2 ≥ n', so by induction the proof is complete.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          It's almost perfectly clear to me now, thank you very much for your help! :)

          → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems that we both did the same, we got 32 pts

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Sorry, missed your previous comment. Well, I guess so :D

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

Can someone explain solutions of last 3 problems?

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

    I will explain D. Let's suppose that we have found some numbers x1,x2,...,xN for the first column such that (x1+x2+...+xN)/N=x1 and the difference between those numbers is huge. With those numbers we can fill the whole table the following way: The second column will contain the numbers x1+1,x2+1,...,xN+1, the third column will contain x1+2,x2+2,...,xN+2, the N-1st column will contain x1+(N-2),x2+(N-2),...,xN+(N-2). It's easy to see that all columns till now are "good" but not the rows. So to make all rows good, we put x1-(1+2+...+N-2),x2-(1+2+...+N-2),...,xN-(1+2+...+N-2) in the N-th column.

    Finding suitable values for x's can be done the same way, fix some large x1 (I used 10^8), then x2=x1+10^4, x3=x1+2*10^4 and so on, xN=x1-(1+2+...+N-2)*10^4. I use some big values so that all numbers will be distinct.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      How can be (x1 + x2 + ... + xN)/N = x1 if all values have to be different?

      UPD: Sorry, I assumed that numbers are increasing. Thank you very much.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you find what's wrong in this idea:

      if n is even output -1 else we print this:
1 2 3 ... n
n+1 n+2 n+3 ... 2n
2n+1 2n+2 .. .. 3n
.
.
n*(n-1)+1 .... n^2
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I had exactly the same solution, but Secta found solution, that works for even grid too.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if n is even output -1

        That's wrong in this idea...

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It is OK only in case when n = 2.

          → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain full solution for B?

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

F can be presented as integer programming with constraints that say we should choose at most 1 vertex from each depth of the tree and that we should choose at least 1 vertex from each path from the root to a vertex at depth k (the root is at depth 0 and it cannot be chosen). Now any feasible solution to this integer program is a solution to the problem.

Is it correct that we can relax the integer programming to linear programming and say that if there is a feasible solution to the linear program then there is a feasible solution to the problem? I did this and my code passed all the tests, but I am not able to prove it correct. This would yield polynomial time solution to the problem as linear programming can be solved in polynomial time.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Well, your solution gets full score, congrats! However, I don't know much about integer programming problems, so I didn't find this solution and can't prove it's correctness, but it certainly seems to be.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wonder if it is possible if you reveal your code only for Integer Programming part? I just want to learn Integer Programming. I am the type that find code more comprehensive than documentation. Thank you.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      There is no integer programming in my code. The idea is to formulate the problem in terms of integer programming and then solve the integer program as linear program. The only thing that changes when going from integer program to linear program is that non integer solutions are allowed. In general case integer programming is NP-hard and cannot be solved directly with linear programming, but in this case it worked. For linear programming I used this implementation and here is the solution for the problem. I think its really hard to learn these things from the code so you should read about them from somewhere else (for example Wikipedia).

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Somehow I forgot to submit my code :( the good thing is that I almost passed all seriously-taken tasks (ACed ABCD, 98/140 E). By the way, are there any solutions for E without using hash? My submission with disjoint-set + hash got WA on first 3 test groups and got AC on the last 7 LOL

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Any solution for C? Mine didn't pass, didn't even get points, how can it be solved? UPD: Saw the verdict, that is SIGSEV, what is that? I used function to calculate the answer, that's why it gives SIGSEV I changed it and wrote same code in int main(), it works well.. why was that SIGSEV?..( Lost 100 pts bcs of it.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The exact same problem is found here.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Since all numbers in the array are positive, you can greedily choose a shortest prefix that sums equal to some suffix, remove both of them, and subtract 2 to the answer.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you have no reasons of caring about your score as it doesn't mean anything for us any more :(

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I got 100 points. here is solution!

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Does anyone know solution for E?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My two teammates for ACM-ICPC had issues with Java at this contest.

They have "Wall-clock time limit exceeded." at some testcases, but when they resubmit the TLEs move to different testcases. I thing it's only a problem due to Java, their complexities seem good. You can check Pierre V to see what I mean. He had TLE at a testcase with N=3... When he resubmitted the same code it passed in 0s (but some other random testcases caused TLEs...)

EDIT : now it's fixed, thanks to the organisers :-)

Also, for people like me who use C++, I remind you to never EVER use STL list... I got 60/100 using list and got 100/100 just changing "list" by "deque". I just had to replace the word "list" by "deque" and it passed (since I only was using pop_front, pop_back, front and back). So the constants for lists are ugly.

I think it's a well-known problem but I didn't have it in mind... Sad story :-)

Anyway, the problems were super nice, congrats to the authors :-)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Never ever use STL list is not a good advice. For problems with tight TL, deque is a better choice and for problems with tight ML, list is preferred to be used from what I've seen.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah but still, the difference in time constants is so big that list seems to very often be a bad choice.

      At least you need to know that the constant is big (here I had a O(n) solution which didn't pass the TL !)

      I'm not the only one to say that, apparently Bjarne doesn't really like linked lists himself

      If you really need a linked list, I'm not sure that the STL list is the best choice, maybe that another implementation is better (I'm not sure of that)

      Anyway, at least everybody should be aware of the possible issue :-)

      → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +18 Vote: I do not like it

My solution for E (got 84 points for failing SMALL cases, got accepted after fixing a small bug)

I double-hashed the integers: each disjoint set contains the sum of the hashes (lets call it set hash). Since it is linear it is easy check if the set contains all the required integers, but not necessary in the correct order.

The difference of current set hash to sorted set hash can be used to match other sets. For example, if the set hash of current elements = {+54, +10} and expected set hash of sorted elements = {24, 15}, this set would have difference = {+30, -5}. If there is another set that has difference {-30, 5}, then these two sets can be combined to become good (answering operation 4).

Maintain a map<pair<LL, LL>, int> that contains these differences. Do not add {0, 0} (good) sets into the map. To add a set of size sz with hash {i, j} into the map, answer += sz * mp[{-i, -j}], followed by mp[{i, j}] += sz.

Operation 1: Substract the hash being swapped out and add the hash being swapped in. Maintain the map.

Operation 2: Merge disjoint sets as usual, add sum of hashes of second set to the first set. Maintain the map.

Operation 3: Check if the map is empty.

Operation 4: Output maintained answer directly.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm curious. What hash functions did you use? For me it was tricky to get it to pass all the cases. I ended up using three hash functions which were pretty convoluted.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can try to randomize the input numbers (after sorting).

      → Reply