Atreus's blog

COCI 2018/2019 Round 5
By Atreus, history, 6 years ago, In English

Hello!

This blog is to let you know that tomorrow another round of Croatian contest, COCI will be held.

Feel free to discuss problems here after the contest ends.

Update: Result

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

»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

2017/2018?

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

Does anyone know the duration of the contest?

Edit: Thanks!

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

why there is no editorial for this year's contests?

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

How to solve 4th and 5th problem ?

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

    Great tasks, it was interesting to do it.

    For the fourth task, I have one TLE, but generally it can be easily solved (on codeforces it was working enoguh fast).

    I stored bitmasks for all strings: 0 if character is '?' othewise 1. For example, string ab??c? would be 110010. Each string save in group with all other strings with that bitmask. Now iterate over all possible pairs of bitmasks (from 0 to 2m in double loop ), and find all 1 on same postions in both strings. That letters should be same, other letters are not important(at least one string contains '?' on other positions). So you have two arrays without ? and you need to count amount of same elements, one from first array one from second. It can be done with std::map.

    The complexity of this solution is O(2m * mn logn). Each group(mask) will be compared with 2m other masks, and everytime in one comparation we go over whole group + mlogn for using maps.

    Code

    This complexity can be decreased a little bit if we are using hashing, even with sorting (not maps), it would be much faster.

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

    D was also solvable with bitset in O(n * m * 26 + n ^ 2 * m / 32) which passed for all points

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

      Could you please share your solution that uses bitset?

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

        We have a bitset of size n (number of words) for each letter of the alphabet, set the i-th bit to 1 in the bitset corresponding to the letter ai. If the letter is '?' set i-th bit to 1 in all bitsets. We do this m times.

        Now we can just start with a bitset where all bits are set to 1 and the number of matching strings with the i-th string is bitwise and (&) of bitsets corresponding to the letters in the string. Note that if the letter aij = '?' we don't need use bitwise and since it won't change anything. One more thing is before we find the solution for i-th word we need to turn all bits on positions less than i to 0 so we don't count some pair twice. My explanation wasn't very good but I think the code is rather clear.

        Code

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

    I haven't submitted yet, but the fifth problem should be solvable with centroid decomposition.

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

      Was the idea anyhow similar to the one used in this problem. I mean something like merging positive length paths at every node in the centroid tree so that we don't care about the fuel being exhausted somewhere in the middle but only compute the sum of vertices in the path  -  sum of edges in the path and then take the positive paths found in this way and a concatenation of such path will be a valid path?

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

        Well my idea was to compute prefix/suffix minimum of sum_v — sum_e in order to make sure that the fuel level never drops below 0, but you're probably on the right track.

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

          Please do share your code if you manage to complete coding and testing your idea. It will be helpful.

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

Are we allowed to send submissions after the end of the contest?

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

I am interested what is expected solution for the third task? Is it O(n3), or O(n2 logn) ?

I have done it in second complexity with hashing and binary search. But it looks that both solutions are passing. If you planned O(n3) solution, then you shouldn't have put subtask n ≤ 200, otherwise you should put at least n ≤ 1000.

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

    I did it in O(n^3) with execution time less than one second. The second task is very useless. Btw, can you explain your solution?

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

      Sure, it is not very hard.

      Probably you did it on following way : Iterate over every pair of rows, check whether strings are angrams (have same number of occurrence of each letter) and then find with one extra loop longest common prefix/suffix. If n - prefix + sufix ≤ k we found one pair and finished job. Now this searching for longest common prefix/suffix can be done with hashing and binary search (try prefix [1... x] compare are hashes same and move left/right border as it needed, same I did for suffix).

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

        Ohhh got it! It makes a lot of sense. My solution is a little bit complicated because of that I didn't see the way to reduce it to n^2 log n. Thanks for the explanation, very clear

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

I wrote a python script that can be used to locally test codes on the test cases being provided on the website. It runs the code on all input files one by one and then compares the output against the output file being provided in the test cases. I used diff command to compare files though it doesn't seem to work probably because of encoding or something, but I thought it may still be helpful for some people for later times maybe. You can find it here.

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

does anyone have the passed solution to E?

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

    I used divide and conquer on the tree , and 2 dp

    First dp is how much gas is needed , so that we can travel from root to vertex V

    Second dp is how much gas stayed after travel from vertex V to root

    Code Link

    → Reply