Блог пользователя awoo

Автор awoo, история, 5 лет назад, По-русски

1194A - Удали прогрессию

Идея: adedalic

Разбор
Решение (adedalic)

1194B - Очередная задача про кресты

Идея: MikeMirzayanov

Разбор
Решение (PikMike)

1194C - От S к T

Идея: Roms

Разбор
Решение (Roms)

1194D - 1-2-K игра

Идея: adedalic

Разбор
Решение (adedalic)

1194E - Посчитайте четырехугольники

Идея: adedalic

Разбор
Решение (Roms)

1194F - Эксперт по кроссвордам

Идея: adedalic

Разбор
Решение (adedalic)

1194G - Очередная мемная задача

Идея: vovuh

Разбор
Решение (BledDest)
  • Проголосовать: нравится
  • +83
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +21 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +42 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    how to compute m choose k in constant time?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      Just pre compute the factorials and inverse factorials

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      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)!}$$$

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          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 :)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The substring doesn't need to be consecutive letters

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

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.

  • »
    »
    5 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    I was wrong.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      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$$$.

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Does your solution work without the pragmas?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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).

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -14 Проголосовать: не нравится

    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)

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

      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.

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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 :)

»
5 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

    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 :)

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 (...)".

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

did anybody solved D using DP ??

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    5 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
My solution for G
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

E solution using pbds 91306062