awoo's blog

Educational Codeforces Round 68 Editorial
By awoo, history, 5 years ago, translation, In English

1194A - Remove a Progression

Idea: adedalic

Tutorial
Solution (adedalic)

1194B - Yet Another Crosses Problem

Idea: MikeMirzayanov

Tutorial
Solution (PikMike)

1194C - From S To T

Idea: Roms

Tutorial
Solution (Roms)

1194D - 1-2-K Game

Idea: adedalic

Tutorial
Solution (adedalic)

1194E - Count The Rectangles

Idea: adedalic

Tutorial
Solution (Roms)

1194F - Crossword Expert

Idea: adedalic

Tutorial
Solution (adedalic)

1194G - Another Meme Problem

Idea: vovuh

Tutorial
Solution (BledDest)
  • Vote: I like it
  • +83
  • Vote: I do not like it

Comments Comments (64)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does it say tutorial for E is unavailable. Was it not posted yet or is it just me?

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

Could anyone provide some classic mathematical resources for question Like D.Rather than by using generalized test cases,and finding cases.how to solve it mathematically.I was thinking of matrix exponentiation but I guess it would not work as we cannot represent Logical-OR operation mathematically.Please provide some Generalised solution for set{$$$a_1$$$,$$$a_2$$$..$$$a_n$$$}. Thank you any kind of help will be appreciated.

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

    For game theory problems it is always better to write a program that generates the solution for a very small instance of the game. For example

    My Generator

    It prints the game state for random values of K for n<=20, after running this gen a couple of times, you'll get the pattern easily.

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

    After you know the pattern it usually is pretty easy to prove it. Particularly, you only need to prove it for the first two iterations of the period of the pattern (in this case of period k+1) since as you can only move at most k, then if the whole k+1 earlier elements of an element are the same as another one in the winning/losing table are the same, then both elements will have the same winning/losing position value.

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

Another solution for F:

Iterate over the number $$$m$$$ of crosswords that will be solved completely, and iterate over all feasible values $$$k$$$ for the number of crosswords that took one second longer. Then add

$$$\frac{1}{2^m} \binom{m}{k} \cdot m$$$

To the answer. This is trivially $O(n^2)$, but it's actually linear: If $$$s_i = t_1 + t_2 + \dots + t_i$$$ then the pair $$$(m, k)$$$ is only feasible if $$$s_m + k \le T \le s_{m + 1} + k$$$. If the first doesn't hold we don't have enough time to solve $$$m$$$ and if the second doesn't hold then we have enough time to solve $$$m + 1$$$.

So for each fixed $$$m$$$ we only consider $$$k$$$ in the interval $$$[T - s_{m + 1}, T - s_m]$$$, and because $$$s_i$$$ is strictly increasing this means that we will consider a certain $$$k$$$ for at most two values of $$$m$$$. There are $$$O(n)$$$ possible values of $$$k$$$ so we'll consider only $$$O(n)$$$ pairs $$$(m,k)$$$

One small detail: If $$$s_{m + 1} + k$$$ is equal to $$$T$$$ then we must divide the value for the pair $$$(m, k)$$$ by two, because we have to take one second longer on the $$$(m + 1)$$$-st crossword to not solve it.

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

    how to compute m choose k in constant time?

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

      Just pre compute the factorials and inverse factorials

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

        thanks! i feel like an idiot for not noticing that

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

      Precompute $$$x!$$$ and $$$\frac{1}{x!}$$$ $$$\bmod{10^9 + 7}$$$ for $$$x$$$ from $$$1$$$ to $$$n$$$ in linear time and use $$$\binom{m}{k} = \frac{m!}{m! (m - k)!}$$$

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

        In editorial for F ,why is $$$P(i)$$$ not multipiled with i (=m ,as in your solution) , and why the sum starts from k=0 to k = m_i , it should not be from 0 .Please help.

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

          Hello!

          P(i) in the editorial is the probability that we solve ith crosswords completely (not the prob. that we solve i crosswords completely).

          Hope this helps :)

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

In C For this test case ab acxb cax ab is not a substring of acxb. Then how the logic is correct. Someone please explain.

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

    Small mistake in the editorial, it should be a subsequence rather than a substring

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

    The substring doesn't need to be consecutive letters

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

The first game problem I came across! Thanks for great problems and solutions ^^

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

As a nice soluton to E I would like to introduce you this Solution. This one works in $$$O(n^3)$$$ using bitsets, and solves a more general problem — find the number of cycles of length $$$4$$$ in a graph, which has $$$O(n)$$$ vertices and $$$O(n^2)$$$ edges. It gets AC due to a very low constant factor and works in just 300ms.

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

    I was wrong.

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

      NVM, I just used bipartite property to lower the constant of the solution.

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

    Hi, could you please explain how come the O(n3) solution worked without getting TLE?

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

      As I wrote it has a very low constant factor. First of all bitset gives us a speed up to 64 times. Also my solution is optimized so that the constant goes down by 8 times more (just some simple facts, like there are only $$$n(n-1)/2$$$ ordered pairs). This gives us a speed up to 512 times, and so we get that $$$\log_2 5000 \approx 13$$$ is actually more than $$$5000/512 \approx 10$$$. So with such limitations ($$$n \leqslant 5000$$$), $$$n^2log \geqslant n^3/512$$$.

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

        Thanks.

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

        appreciate the explanation, was also confused about not getting TLE.

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

    Does your solution work without the pragmas?

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

      Pragmas give a big boost, but i have a solution which AC without them. This solution uses hand made bitsets. But without #pragma GCC target("avx2") it passes in approximately 600ms. This pragma gives a boost up to 4 times, and I have a solution which passes in just 150ms.

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

Can someone please elaborate the explanation for problem B "Yet Another Crosses Problem"?

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

    For every cross we can make, we must colour all the white cells in i-th row and j-th column. So, we can precalculate the number of black cells in each row and in each column. Let cntr[i] be the number of black cells in the i-th row and cntc[j] be the number of black cells in the j-th column. Now, we can only go through all the cells and check the number of cells we must colour if the chosen cell is the centre of our cross. Let the chosen cell be in i-th row and j-th column of the matrix. We can do it in O(1) time, like (n-cntr[i])+(m-cntc[j])-(matrix[i][j]=='.'). Why this -(matrix[i][j]=='.')? Because if matrix[i][j]=='.', it was counted two times(in cntr[i] and in cntc[j]) , instead of one. Among the all possible answers, we need one with the smallest number of colouring cells. Finally, our time complexity is O(Q*NM).

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

Is there any general approach to tackle game theory problems such as D ? What approach do you use to solve problems like these?

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

    I just painted in the paper situations(winning or losing positions) for different k and noticed regularity

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

      Upto what sample size did you do this?

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

        I think upto 5 and dividers of 3 (6, 9) were enough

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

    If n would have been small the problem could have been easily solved by linear regression in O(n) instead of finding a pattern. Just maintain a boolean array arr to donate winning or losing at that index. arr[0] = false i.e. loose arr[1]=true arr[2]=true

    for i = 3 to n 
if arr[i-1] and arr[i-2] and arr[i-k] are true, then only arr[i]=false otherwise its true;

    just output arr[n] now.

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

    Call a game state 'losing' if first player loses if game starts from it, 'winning' otherwise. Game state without any possible moves is obviously 'losing'. You can then analyze a game with any fixed k manually on a paper: go through positions (length of the line in our case) and look at possible moves from it (if there is a move to a losing state, our is winning, otherwise, our is losing). This is a typical way to analyze determined games.

    Doing that, you will notice, that without k-move, sequence of winning/losing states is like that: LWWLWWLWW... K-move, though, sometimes prevents state from being losing by providing one more move. So, easy to see, if k is not divided by 3, it changes nothing. If it is divided by 3, you can analyze how k-move changes the structure.

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

Isn't the complexity of solution given for E O(n3)?

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

    Nope n*logn

    Because you running around 5000 segments and for every one you make some operation that have complexity logn(n ~= 10000) -> result complexity n * logn

    P.s. Correct me if I'm wrong(Yeap, I wrong)

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

      I feel like its O((N^2)logN) because for each horizontal segment at height y, you iterate over all the horizontal segments at a height greater than y which is N^2 and a factor of logN for using Fenwick tree query during every iteration.

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

does anyone know a good source for game theory or how to be better at it

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

    If by a good source you mean reading material then you can read it from here and here. I feel like there is not much to read. If you are looking for more questions (you can become better by solving them) then you can refer to this blog (you can find questions on other topics as well in this blog).

    Good luck! I hope this helps :)

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

Can someone explain the time complexity analysis of problem E editorial solution ?

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

    The complexity is O((N^2)logN), let's analyze it using the solution mentioned in the blog. We iterate from y=0 to y=N-1 and for each y we iterate all the horizontal line at height y, note that if the solution consisted of only these two loops then the complexity would have been O(N) and not O(N^2) because these two loops only iterate total number of horizontal lines which has an order of N . Inside these loops, we find a loop that iterates from x-coordinate from x=l to x=r and for each x we iterate all the vertical line having x-coordinate from x=l to x=r which has an order of N and hence these two loops run in O(N), so complexity up to this step is O(N^2), one factor of N for the outer two loops and another for the inner two loops. Now we come across a loop which runs from y2=y+1 to y2=N and for each y2 we iterate all the horizontal lines at height y2 using similar logic used above these two loops run in the complexity of O(N) but inside these loops, we use the query of Fenwick tree which consumes O(logN) time hence the complexity of these two loops become O(NlogN) , therefore the overall complexity is O((N^2)(1+logN)) which is O((N^2)logN).

    I hope this helps :)

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

      Instead of

      "Now we come across a loop which runs from y2=y+1 to y2=N and for each y2 we iterate all the horizontal lines at height y2 using (...)"

      it should be

      "Now we come across a loop which runs from y2=y+1 to y2=N and for each y2 we iterate all the horizontal lines at height y2 and all the vertical segments with their top end at height y2 using (...)".

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

What is learned is- In game theory questions like this after determining the base conditions what you need to is based on previously computed results, you need to make the current player move such that in next chance other player reaches in such position where if the current player was there it would have loosed. If no such position is possible then current cannot win.

Is that right?

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

Can someone please explain the second condition for a good vertical segment in problem E?

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

    Well, it says that the vertical segment has its smaller y-coordinate below or at the same level as the y-coordinate of the horizontal segment. If we know that it also intersects a horizontal segment above our fixed horizontal segment, than we know that it intersects the fixed horizontal segment.

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

Can someone explain me why if $$$n = 3$$$ and $$$k = 4$$$ the winner is Bob? There are 3 cells between position of chip and 0-pos, so why Alice can't win?

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

    Nobody can go below zero. And the rule is you can only take 1 or 2 or exactly K.

    It is Not take 1, or 2, or any number up to K.

    If n=3 and k=4

    Alice can't take 4, she can only take 1 or 2, leaving either 1 or 2 for Bob.

    Bob now can always take 1 or 2 either way Alice leaves it, therefore Bob always wins on his first turn.

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

Problem G: Can someone give intuition for $$$mask$$$ in dp's state? What does it mean?

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

    If we want to check $$$\frac{1}{2}$$$ we check both $$$\frac{1}{2}, \frac{2}{4}, \frac{3}{6}, \frac{4}{8}$$$
    and the respective mask would be $$$1«0, 1«1, 1«2, 1«3$$$
    see how to init numPos and denPos in the author's code.

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

Can anyone explain the editorial in simpler words for E? Why are we decrementing x in tree? Thank You.

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

    Because we are going from bottom to top with respect to the y coordinate and a vertical segment has just ended--i.e. we are at its top coordinate--so we remove it from our container because it won't intersect any of the following horizontal segments.

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

In the editorial of D, it is given that "the game is symmetric". What does it mean that the game is symmetric and how do we know that it is symmetric?

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

    If a cell is winning 4 Alice, it's also winning 4 Bob.

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

did anybody solved D using DP ??

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

    It would have been easier with DP if the constraints were not so large. At least I think so...

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

What is the maximum number of statement executions that will get accepted?

Like for problem B -> Time complexity is n*m per query -> Total time complexity = q*n*m.

q*n*m = (5 * 10 ^ 4) * (4 * 10 ^ 5) = 2 * 10^10 approximately.

Will this get accepted?

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

    Other than constraints on n and m individually, it is also mentioned(in the problem constraints) that sum of (n*m) over all test cases is <=4e5. So it'll be fine.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My solution for G
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E solution using pbds 91306062

→ Reply