giorgosgiapis's blog

COCI 2017/2018 — Round 3
By giorgosgiapis, 7 years ago, In English

Third round of COCI 2017/2018 season will take place this Saturday at 14:00 UTC.
You can find the full schedule for this season here and register for the contest here.

Let's discuss the problems here after the contest.

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

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Sorry if this question has been asked before, but I quickly Googled it just now and can't find it.

Is there a way to change our COCI account password? Thanks.

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

    Step 1: Go to http://evaluator.hsin.hr/login.php?redirect=index.php

    Step 2: Look at the line "Forgot username and password..." and you will see a link directed to an other website.

    Step 3: Enter your email you used to register.

    I didn't try, but I hope these will help you.

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

      I just tried this. This feature will generate a new (random) password for you and the new password will be emailed to you.

      I want to be able to change it to my own custom password.

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

        There is currently no feature that allows you to change your old password to a custom one, sorry.

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

        try to send clarification request

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

duration ?

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

Good luck to everyone!

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

Weird. I don't see tasks.

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

Is there something with 0, (2^m)-1 and subsequence that xor of all elements == (2^m)-1 in E task?

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

How to solve C, E, F?
Is there smth faster than for C?

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

    E: An interval can't win iff it contains exactly 2k pair (x, 2n - 1 - x).

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

      Do you have any proof?

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

        Proof is easy. Let its xor sum be X. Then for each element a in that interval we must have a^(2n - 1)^X also is in that interval. So we have d pairs (a, a^(2n - 1)^X). Because its xor sum is X, so X must be 0.

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

      How do you check if an interval meets the condition effectively?

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

        Denote N = 2M - 1.

        You can answer the queries of the type "maximum/minimum index i such that N - perm[i] exists in the target interval" in O(1) with O(NlogN) or even O(N) precomputation with RMQ. Then, if the answer to any of the queries doesn't belong to the target interval, the interval is winnable (as explained in chemthan's post).

        Unfortunately, as the task is to count the winnable intervals rather than answer to queries, this method is only O(N2), which is enough only for 50% of the points.

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

      How to solve it after this? It seems now it reduces to: count the number of subarrays with exactly 0 or 2 instances of every element.

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

    If my solution is correct, time complexity of my solution is O(R2 * S)

    Problem C

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

      Yeah, that was the intended solution.

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

      So can you explain it?

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

        Sure, let's first think about the game in a different light. Suppose that everything on the grid stays still and the main character can in one second move from (r, c) to (r - 1, c - 1), (r - 1, c) or (r - 1, c + 1). It is easy to see those games are equivalent.

        Let dp[r][c][o] denote the longest valid expression you can acquire if you are currently on position (r, c) on the screen and the difference between the number of open parentheses and closed parentheses in the expression you have acquired thus far equals o. Computing all dp values takes O(R3) time. This solves the part of the problem that deals with the length of the sequence.

        For the reconstruction, we'll keep around a set of dp states that can potentially lead us to the lexicographically smallest solution. At the beginning, that set contains only Mirko's initial position. We will now make transitions from those states (similar to transitions in dp) that lead to longest solutions and traverse only the empty cells of the grid (this is a standard bfs). Once we have exhausted the empty cells, we have obtained the set of cells that contain the next parenthesis in our sequence. At this point we will disregard all cells that have ')' written on them in case there exists a single cell with '(' written on it. Repeating this process yields the lexicographically smallest sequence in O(R2).

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

          Since there is no test case with expression longer than 50, separate reconstruction part is actually not needed. We can define dp value as pair of (longest valid expression, lexicographic price of expression) and then just maximize this pair using dp.

          If for some state longest valid expression is k then lexicographic price is k-bit number created from this expression with ( being 1 and ) being 0 — this k-bit number is solution itself.

          EDIT: Actually I modified this approach a bit and it works for all possible cases i.e. with expressions up to 100, just replace k-bit number with solution string, add custom operator< and then just print that string at the end.

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

            What makes you think there is no test case with expression longer than 50?

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

              Well, I meant in this specific contest there was not :). Of course there could be a test case with expression longer than 50.

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

                You made me a bit paranoid for a second because I generated the test data :)

                Now I see that we uploaded the wrong .zip archive at hsin.hr/coci which contains the test data for our local version of the contest (honi). That version of the task had looser constraints and the solution you described was supposed to get accepted.

                The correct archive should be up tomorrow.

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

                  As noted in the edit of my comment above, this approach is working for all possible test cases if the lexicographic price part is replaced by plain string, bitset could be used as well. Thus special reconstruction phase could be avoidable after all. Waiting for additional test cases.

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

Wasn't C was harder than other C's in COCI?

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

D is pretty easy right? Unless I missed something that made it hard...

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

Do you know when can i see the results?

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

    Usually, after 40 min. we can see results, but there can be delay sometimes.

    Results delayed :(

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

    in messages i saw this " Results will be available tomorrow. Thank you for patience. "

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

What is the optimal solution in problem B?

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

    Precalculate prefix sums for each letter. When answering queries, check if count of each letter in same on intervals.

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

What is the solution for C? I wrote a solution that works in O(3^R), but it is obviously too slow.

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

Will they open the analysis mode?

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

Turn on analysis mode please.

→ Reply