Lewin's blog

By Lewin, history, 5 years ago, In English

Here's the tutorial. Code can be found in this link (more will be added there soon): https://www.dropbox.com/sh/xwxn3zrl1icp3i2/AACtYSdYH0KlTEdVgCFFgPrYa?dl=0

Zoning Restrictions Again
Double Matrix
Hide and Seek
Chladni Figure
Thanos Nim
Palindrome XOR
Rainbow Coins
Zigzag Game
  • Vote: I like it
  • +117
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Peace on you :) Thanks a lot for this Amazing contest ever at least for me :)

»
5 years ago, # |
  Vote: I like it +71 Vote: I do not like it

E was cool, D was very easy (IMO).

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

    what u think about hide and seek problem??was it easy for you??

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

      Man see his rating carefully. And then that of the question. You will get your answer.

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

        How to code like them bro...I try a lot but still every time new question of dp and trees comes i cant think of any solution...

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

          Practice, practice, practice...

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

          Either you try Questions too hard for you level in a rush to become like Grandmasters, or either you solve too easy question and then wonder why aren't you improving. My Suggestion is try to solve questions which require you atleast 5 minutes to 30 minutes of deep thinking. Not the questions that you can solve by looking at instantly and not the question which require you a whole day to solve(As they will demotivate you and make your progress really slow).

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

Nice Proof of Greedy Solution of B , how to solve B using dp (just for curiosity)

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

The problems of this contest was good. :)

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

Sadly I didn`t do my best at this contest, but the problems were really good!

»
5 years ago, # |
  Vote: I like it +21 Vote: I do not like it

My solution for E only used 4 queries.

https://codeforces.com/contest/1161/submission/53759655

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

    Interesting. 4 is also optimal for $$$n$$$ large enough, since 3 is impossible when $$$2^{1.5n} < 3^n/6$$$.

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

Can anyone help me with the B. If aij<=bij how does it ensure that there will always be a correct solution. Suppose aij<=bij and aij+1<=bij+1 but aij>aij+1 and bij>bij+1. Then even if the configuration is valid there can't be any solution.I couldn't understand it. Please help me with it.

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

Great contest (Y)

Wondering how everybody answered Thanos nim. Had a hard time figuring what was the insight for the game :)

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

    I wrote a brute force for $$$n = 6$$$ and $$$0 \leq a_i \leq 5$$$ and outputted the positions where Bob wins. From those positions the solution is obvious.

»
5 years ago, # |
Rev. 3   Vote: I like it +53 Vote: I do not like it

Lol, no test in div1b had n = 83160 or something close to a highly composite number. My code takes like 8 seconds on n = 83160, m = 200000 and random values of segments (this generator). The highest number of divisors seems to be 48 on 51450 when it could've been 128 on 83160.

Maybe such a test could be added to a testset?

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

    Maybe it didn't affect anybody but tests for 1161D - Палиндромный XOR seem weak too. Judging from prefixes of tests, all big tests are just random characters ?01. Maybe there is some smart pattern in some, but I don't see any test e.g. with just characters 1 or just ?.

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

    Thanks! arsijo added it to the tests yesterday. It's my bad T-T

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

I didn't fully understand why in Div. 1 — B we can simply check for the divisors of n. Could someone try to explain it a bit better or with an example ?

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

    Let's suppose that image is rotationally symmetrical and image consist of p identical blocks. Then every block has length of n/p. Then if we rotate image by n/p units, the new image will be the same as the original one. Now we can brute force the value p among the divisors of n and check if the rotation i + n/p is correct.

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

    Let a segment be [a,b] when we rotate it by k it gets [a+k, b+k] to be symmetrical there should be a segment [a+k, b+k] which after rotating will move to [a+2k, b+2k] or we can say that all possible values can be [(a+xk)%n, (b+xk)%n].

    r = (a+xk)%n = a+xk-qn

    xk — qn = r — a

    Use bezout identity euqation has solution if r-a is c*gcd(k,n) or r = a+c*gcd(n,k).

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

I recieved a system message that the solution of my first question Div2A Zoning Restrictions significantly matches with that of someone named MetaFish, but I even don't know the person and didn't use Ideone like things by which code can be shared. It may be just a pure coincidence as doing first question there are huge chances of matching the code, so I want to clarify this as it was written in message to comment on the post that I did code on my pc and then using browse submitted it.

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Actually KMP can solve D by regarding the original and rotated images as two strings and match them together. Time complexity can reach O(m) (use the correct way of vector comparison).

»
5 years ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

Can anyone explain E to me ? "The main claim is that if a player is forced to reduce the minimum number of stones over all piles, then they lose."

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I am not being able to understand the question of Div-2 (C) Hide and Seek... please someone explain me the question??

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

    Same bro

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

    Bob will ask Alice k questions (if Alice is in the i-th cell ? ) . On reply.. Alice can answer yes or no. At most one time in this process, before or after answering a question, Alice is allowed to move her token from her current cell to some adjacent cell.

    Consider the first example: << Lets say, {x,x,x} is ALice's answer on Bob's 3 question. Here , x = y(yes) or n(no). >> there is a subsequence (5,4) on Bob's question. Since Alice can change the position at most once, here 3 cases can be arrived. 1) if she changed before 5 , her answer will be {n,n,y}; 2) if she changed on between 5 and 4, answer {y,n,y}; 3) if she changed after 4, her answer {y,n,n};

    Now consider a subsequence that is not present in Bob's question list. Let it is (3,4) in this case , she can change position after 4, her answer will be {n,n,n};

    And the question says, "Alice acted in such a way that she was able to answer "NO" to all of Bob's questions." As you just see .. if there is a subsequence , Alice's answer will must contain at least 1 yes.

    And since Alice can move to an adjacent cell only, There are 2*(n-1) + n subsequence on their playing ground. So all u have to do is .. somehow erase all those culprit subsequence from our all possible subsequence set. Thats it ! :3

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

There is a bruteforce solution for B that works in O(nm * nm) time https://codeforces.com/contest/1162/submission/53760985

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

    why so hard? my solution works in O(n*m) time and it is much easier
    http://codeforces.com/contest/1162/submission/53747942

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

      It's clear that the greedy solution works but the tutorial says that brute force doesn't, so I sent this. Could be interesting to smb

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

        can you explain your bruteforce approach , code is hard to understand without knowing the approach

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

          If we have an inversion in a matrix, e.g. a[i][j] >= a[i][j + 1], we can either swap a[i][j] & b[i][j], or a[i][j + 1] & b[i][j + 1]. After we make a swap, new inversions may appear in adjacent cells, so then we try to get rid of them the same way. That's how the recursive function works. We just need to launch it from each cell, and during one launch we never visit one cell twice, so it's O((nm)^2)

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

In 1147C - Ним Таноса

Solution

I didn't get this, suppose the piles are 1,4,4,4 how can we reduce (n/2 = 2 among 4,4,4 piles) to 1,1, It's said that they must be reduced by a different amount??

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Can someone provide proof in Problem D that k must be a divisor of n?

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

    [Deleted]

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    Well, I used two facts to prove it.

    1. turning by $$$k$$$ will yield the same result as $$$2k$$$, $$$3k$$$ and so on;
    2. turning by $$$n$$$ will obviously put the circle in the same position it was initially.

    Thus there exists some $$$t$$$ such that $$$tk = n$$$, $$$k$$$ is a divisor of $$$n$$$.

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

      By your logic 2k, 3k, ... must all divide n.

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

        I can't see how to come to this conclusion.

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

          Substitute k for 2k and apply the same logic.

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

            Well, it becomes $$$2k$$$, $$$4k$$$, $$$6k$$$ and so on. If there still exists some integer $$$t$$$ so that $$$2tk = n$$$, why not?

            I don't get what can be unclear, sorry. Maybe try marking the $$$0$$$ point and checking where will it end after some turns. $$$k$$$, $$$2k$$$, $$$3k$$$, $$$\dots$$$ will be its position at each next move. Also it'll return to 0 (which is equal to position $$$n$$$) after $$$t$$$ moves.

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

    Let the minimum value to do a symmetrical rotation be $$$k$$$.

    Then for any $$$t$$$, such that $$$t \% k == 0$$$, $$$t$$$ will produce a symmetrical rotation too, and generally rotating by $$$t$$$ is the same as rotating by $$$t\%k$$$.

    It's obvious that turning by $$$n$$$ produces a symmetrical rotation.

    Let $$$n \% k != 0$$$, then that means that $$$n \% k$$$ produces a symmetrical rotation. But $$$n\%k < k$$$, hence this statement contradicts the first one.

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

    Start numbering from zero,instead of 1

    If a,b moves to (a+k)%n,(b+k)%n.Then (a+k)%n,(b+k)%n will move to (a+2*k)%n,(b+2*k)%n and so on,but there should be a (a+k(q-1))%n,(b+k(q-1))%n,which will move to a,b in next step.

    so, (a+kq)%n=a

    a+kq=dn+a

    kq=dn

    if k is not divisible by n,then it should definitely be divisible by nd.

    q can be at max n.

    SO,d cannot be greater than k.

    So if k divides nd,then k/d should divide n.

    In short if there is a solution with k not divisible by n,then there will definitely be another solution with k1 less than k and k1 divisible by n.

    Try this test case

    7 7

    0 2

    1 3

    2 4

    3 5

    4 6

    5 0

    6 1

    K=2 is a solution,but k=1 is also a solution

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can someone please explain 1147B — Chladni Figure string solution.

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

    If for some k, you rotate all segments by k units and you get the same figure back then it is also possible for 2*k, 3*k ......so on. Now you can get the same figure back when k=n. So k must be a divisor of n. Any number under 10^5 has around 100 divisors at max, so you have to check for them only if such a k exists or not

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

Problem B DIV 1

"We can do this by iterating through all segments (a,b), and checking that (a+k,b+k) is a segment (the endpoints taken modulo n if needed)."

How can we check that (a+k,b+k) is a segment in o(1)? Tutorial says that "this gives an O(nm) solution".

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

    Since there are no perfectly overlapping segments maybe we can do something like — Transform a segment [x,y] into [x%k, y%k] and check final counts of segments appearing in the first block because [(a+k)%k, (b+k)%k] = [a,b].

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

    By keeping the pair in a unordered_set or hashset. Or you could just use set or treeset with o(logn) complexity. It will still get accepted, I submitted this way

    Solution: http://codeforces.com/contest/1162/submission/55727925

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

Can anyone help me? I'm trying to implement a z-algorithm on 'Chladni Figure' problem and i get wrong answer on test 3 saying the output was "yes" and the correct answer is "no" and when i try it myself it shows the correct answer. What is the problem?

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

I am not getting the tutorial of Chladni Figure with fastest approach. please help!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In ques:- Palindrome Xor can someone tell me how to take care of case when smaller no. becomes 0 as we are not allowed to take no. equal to zero.

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

    Sorry, I got my mistake after spending a lot of time.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think a more convincing proof for problem B[problem:B] would involve induction on n+m=k in a way that we can always be sure that for k=1 it's true that if there is a configuration that works, then changing matrices to bigger and smaller would also work, and so on.