ToniB's blog

Croatian Open Competition in Informatics (COCI) 2024/2025 — Round #5
By ToniB, history, 4 days ago, In English

Hi everyone!

The final round of COCI will be held tomorrow, February 15th at 14:00 UTC. You can access the judging system here. If you are not familiar with the COCI contest format, we encourage you to read the announcement.

The round was prepared by dorijanlendvaj, ppavic, fbabic, jcelin, and me.

Feel free to discuss the problems in the comment section after the contest ends.

Hope to see you tomorrow!

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

»
4 days ago, # |
  Vote: I like it +10 Vote: I do not like it

My brute force code gave me all the subtasks except the 4th one (61 points) for problem tornjevi

code

a tescase with the same number repeated N times would fail this code

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

    Test cases were weak.

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

Where can I submit for this round?

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How can one solve Crtez for a full score? Managed easily to pass the $$$N<=10^5$$$ subtask (~29MB) and couldn't fit my sparse segment tree solution to the memory limit of the last subtask

→ Reply
»
3 days ago, # |
  Vote: I like it +29 Vote: I do not like it

I don't understand how the solution for P4 Crtež.

solution

For example if n=2: {0, 0}, {0, -1}, {1, 1} = {2, 2}, {-1, 0}, {-1, -1}, {-1, 2}, {1, 0}, {1, -1} There are only 8 possibilities and not 9 ({0,1} is impossible)

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

    I will try to prove it by induction. (excuse me if i missed something)

    claim: the contribution $$$s(k)$$$ of $$$k$$$ zeros between $$$-1$$$ or at some border of the array is independent and equal $$$3^k$$$.

    Base case:

    $$$k = 1$$$ obviously have $$$3$$$ cases $$$-1, 0, 1$$$. so $$$s(1) = 3^1 = 3$$$

    Inductive step:

    $$$s(k) = 3^k \implies s(k+1) = 3^{k+1}$$$ for all $$$1 \leq k$$$

    Inductive hypothesis:

    we assume $$$s(k) = 3^k$$$.

    Adding another zero to the start of the array has three cases:

    • Its value will be $$$-1$$$, we can still achieve the same ways to the rest of the $$$k$$$ zeros

    • dont operate on it, its value will be equal to the next number

    • operate on it, its value will be a new distinct value

    this is independent of any other number that was initially in the array (and the order of operations). Thus $$$s(k+1) = 3 \cdot s(k) = 3^{k+1}$$$

    The answer is the multiplication of $$$s(k)$$$ over all maximum subarrays consisting of zeros.

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

      The thing is, operating on the new 0 will effectively set a new color on it but when we operate on a zero further in the array, the color of our new zero will be overwritten. What implicates that the new zero cannot present a distinct value.

      So if I have {0,0,0} and I set the first 0 to 1 --> {1,0,0}

      Setting the second or the third zero to 2 will overwrite the first 0 --> {2,2,0}

      Changing the order of operations does so that a new value cannot be set the first 0 cause setting a value can only start on a 0.

      In order to keep the distinct value on the new 0. You have to set a -1 after it or not set new values after it (so you keep 0's or only set -1).

      → Reply
»
3 days ago, # |
  Vote: I like it +18 Vote: I do not like it

I don't understand why my solution for Crtež doesn't work.

I'm using a dp where $$$s(k)$$$ is the number of possibilities when you have k zeros in a row.

Obviously, $$$s(0)=1$$$ and $$$s(1)=3$$$ : $$$-1, 0, 1$$$.

For all $$$2≤k$$$, $$$s(k) = 3 ⋅ s(k-1) - s(k-2)$$$

My first observation is that if you always paint in the same color, you'll get the same number of different possibilities because if you have a space filled with zeros (without any -1), you'll always use one color (each time you add a new color, you overwrite on the past color), so if you take in consideration that only one color is used, you have 3 possibilities for each position: -1, 0, 1, but you can't have a 0 to the left of a 1. So I found this formula that works for this "subproblem" I think. I suppose my observation is wrong but I can't figure out how.

→ Reply
  • »
    »
    3 days ago, # ^ |
      Vote: I like it -43 Vote: I do not like it

    Hi, this is my task. The coordinators(and me) have wrongly transferred the task statement from the task we were solving to official COCI statement. We were solving the task where the operation is stopped being performed when you reach a position with a number different than 0. In that case there is a simple proof for the formula. For the task which has appeared on this COCI round, your formula is correct. We are very sorry for the inconvenience.

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

      Ok, I understand. Could you still publish one of the 2 versions on the platform?

      → Reply