### PikMike's blog

By PikMike, history, 3 months ago, translation, ,

1194A - Remove a Progression

Tutorial

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

Tutorial

1194E - Count The Rectangles

Tutorial
Solution (Roms)

1194F - Crossword Expert

Tutorial

1194G - Another Meme Problem

Idea: Vovuh

Tutorial
Solution (BledDest)

• +83

 » 3 months ago, # |   0 Why does it say tutorial for E is unavailable. Was it not posted yet or is it just me?
•  » » 3 months ago, # ^ |   +2 It's available now
•  » » » 3 months ago, # ^ |   +3 Thanks
 » 3 months ago, # | ← 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.
•  » » 3 months ago, # ^ |   +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 int z=10; srand(time(0)); while(z--) { int k=rand()%10+3; int arr[21]; arr[0]=0; arr[1]=1; arr[2]=1; for(int i=3;i<21;i++) { if(arr[i-1]==0) arr[i]=1; else if(arr[i-2]==0) arr[i]=1; else if(i>=k&& arr[i-k]==0) arr[i]=1; else arr[i]=0; } for(int i=0;i<21;i++) cout<
•  » » » 2 months ago, # ^ |   0 How u write the generator what is the idea behind it
•  » » » » 2 months ago, # ^ |   +3 That's kind of a secret ;)
•  » » 3 months ago, # ^ |   +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.
 » 3 months ago, # | ← 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.
•  » » 3 months ago, # ^ |   +8 how to compute m choose k in constant time?
•  » » » 3 months ago, # ^ |   +22 Just pre compute the factorials and inverse factorials
•  » » » » 3 months ago, # ^ |   +19 thanks! i feel like an idiot for not noticing that
•  » » » 3 months ago, # ^ |   +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)!}$
•  » » » » 3 months ago, # ^ |   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.
•  » » » » » 3 months ago, # ^ |   +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 :)
 » 3 months ago, # |   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.
•  » » 3 months ago, # ^ |   +15 Small mistake in the editorial, it should be a subsequence rather than a substring
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Can anybody pls tell for which input my code is giving WA?? https://codeforces.com/contest/1194/submission/57146778
•  » » 3 months ago, # ^ |   0 The substring doesn't need to be consecutive letters
 » 3 months ago, # | ← Rev. 2 →   +12 The first game problem I came across! Thanks for great problems and solutions ^^
 » 3 months ago, # |   +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.
•  » » 3 months ago, # ^ | ← Rev. 5 →   0 I was wrong.
•  » » » 3 months ago, # ^ |   0 NVM, I just used bipartite property to lower the constant of the solution.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Hi, could you please explain how come the O(n3) solution worked without getting TLE?
•  » » » 3 months ago, # ^ |   +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$.
•  » » » » 3 months ago, # ^ |   0 Thanks.
•  » » » » 3 months ago, # ^ |   0 appreciate the explanation, was also confused about not getting TLE.
•  » » » » » 2 months ago, # ^ |   0 bitset is magic.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Does your solution work without the pragmas?
•  » » » 3 months ago, # ^ |   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.
 » 3 months ago, # |   0 Can someone please elaborate the explanation for problem B "Yet Another Crosses Problem"?
•  » » 3 months ago, # ^ | ← 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).
•  » » » 3 months ago, # ^ |   0 WoW brilliant man thanks for the beautiful explanation really appreciated.
 » 3 months ago, # |   0 Is there any general approach to tackle game theory problems such as D ? What approach do you use to solve problems like these?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I just painted in the paper situations(winning or losing positions) for different k and noticed regularity
•  » » » 3 months ago, # ^ |   0 Upto what sample size did you do this?
•  » » » » 3 months ago, # ^ |   0 I think upto 5 and dividers of 3 (6, 9) were enough
•  » » 3 months ago, # ^ |   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.
•  » » 3 months ago, # ^ |   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.
 » 3 months ago, # |   +4 Isn't the complexity of solution given for E O(n3)?
•  » » 3 months ago, # ^ | ← Rev. 3 →   -14 Nope n*lognBecause you running around 5000 segments and for every one you make some operation that have complexity logn(n ~= 10000) -> result complexity n * lognP.s. Correct me if I'm wrong(Yeap, I wrong)
•  » » » 3 months ago, # ^ | ← 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.
 » 3 months ago, # |   +1 does anyone know a good source for game theory or how to be better at it
•  » » 3 months ago, # ^ |   +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 :)
•  » » » 3 months ago, # ^ |   +4 THANK YOU
 » 3 months ago, # |   +6 Can someone explain the time complexity analysis of problem E editorial solution ?
•  » » 3 months ago, # ^ | ← 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 :)
•  » » » 3 months ago, # ^ |   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 (...)".
 » 3 months ago, # | ← 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?
 » 3 months ago, # |   0 Can someone please explain the second condition for a good vertical segment in problem E?
•  » » 3 months ago, # ^ |   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.
 » 3 months ago, # |   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?
•  » » 3 months ago, # ^ |   -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.
•  » » » 3 months ago, # ^ |   0 thank you, got it.
 » 3 months ago, # |   0 Small solution for problem 1194C - From S To T ---> 57160243
 » 3 months ago, # |   0 Problem G: Can someone give intuition for $mask$ in dp's state? What does it mean?
•  » » 3 months ago, # ^ |   +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.
 » 3 months ago, # |   0 Can anybody pls tell for which input my code is giving WA?? https://codeforces.com/contest/1194/submission/57146778
 » 3 months ago, # |   0 Can anyone explain the editorial in simpler words for E? Why are we decrementing x in tree? Thank You.
•  » » 3 months ago, # ^ |   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.
 » 3 months ago, # |   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?
•  » » 3 months ago, # ^ |   0 If a cell is winning 4 Alice, it's also winning 4 Bob.
 » 3 months ago, # |   0 did anybody solved D using DP ??
•  » » 3 months ago, # ^ |   0 It would have been easier with DP if the constraints were not so large. At least I think so...
•  » » » 3 months ago, # ^ |   0 Hmm I too think the same
 » 3 months ago, # | ← 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?
•  » » 2 months ago, # ^ | ← 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.
 » 3 months ago, # |   0 I can not understand the 4 no solution. can anyone elaborate if you got the time? thanks in advance.
 » 3 months ago, # | ← Rev. 2 →   0 In Question-D, I am not able to understand why position 2k is winning (if k is multiple of 3)?For a position to be winning, you must be able to go to atleast one losing position right?Now, 2k-1 and 2k-2 are winning (since all positions not multiple of 3 are winning) and position k is also winning (as you can go to 0) so how is position 2k-1 winning as you can only go to these 3 mentioned positions-->2k-1, 2k-2 and k?Also, the numbering is from — 0,1,2,3...k,k+1,k+2...2k,2k+1,2k+2... so, If I split it into cycles of k+1, then I will get:0,1,2,3...k | k+1,k+2,k+3,..2k+1 | 2k+2, 2k+3,... There is not uniformity since the first element is increasing by 1. How are we using the cycle of length k+1?Thank You
 » 2 days ago, # |   0 My solution for GMy solution uses dp having "only" 4 dimensions. Firstly we can assume x <= y and keep track only of whether $ay \leq n$ because if it is, then $ax \leq n$ as well. Second instead of keeping track of which interesting digits were used we will pass extra parameters to function calculating dp denoting digits allowed to appear in $ax$ and $ay$ respectively. To extract the answer from this modified dp we will use inclusion exclusion principle. Let $U$ denote set of all fractions in valid range $X_i$ denote set of fractions whose nominator contains digit $i$ and $Y_i$ set of fractions whose denominator contains digit $i$. Suppose $x = 1, y = 2$ We are interested in $(X_1\cap Y_2)\cup(X_2\cap Y_4)\cup(X_3\cap Y_6)\cup(X_4\cap Y_8)$.Using inclusion-exclusion principle we can expand its cardinality to: $|X_1\cap Y_2| + |X_2\cap Y_4| + |X_3\cap Y_6| + |X_4\cap Y_8| - |X_1\cap Y_2 \cap X_2\cap Y_4| - \ldots - |X_1\cap Y_2 \cap X_2\cap Y_4 \cap X_3\cap Y_6 \cap X_4\cap Y_8|$Let's see how we can calculate on particular set: $|X_1\cap Y_2 \cap X_2\cap Y_4| = |U| - |\overline{X_1}\cup\overline{Y_2}\cup\overline{X_2}\cup\overline{Y_4}|$, and again use inclusion-exclusion principle since intersection of some of those sets is exactly set of fractions not containing any of given digits, which we can calculate using our DP. At first it seems we will call this function lots of times, but first we can improve it in other way. First for each set of forbidden digits in numerator and denominator calculate sum of coefficients with which the result of this dp will be added to the answer and run the function only if it is nonzero. It turns out this sum is: $1$ if both forbidden sets are empty, $(-1)^\text{number of forbidden digits + number of pairs}$ if from each pair at least one digit is forbidden, and $0$ otherwise, which means we will run dp only $1 + 3^{4}$ (or in general $1 + 3^k$ where $k$ is number of pairs) times.62745786