tokitsukaze's blog

Codeforces Round #573 Editorial
By tokitsukaze, 5 years ago, In English

1191A - Tokitsukaze and Enhancement

Idea: tokitsukaze

Tutorial
Solution (by Claris)
Solution (by tokitsukaze)

1191B - Tokitsukaze and Mahjong

Idea: tokitsukaze, 2014CAIS01

Tutorial
Solution (by skywalkert)
Solution (by isaf27)

1190A - Tokitsukaze and Discard Items / 1191C - Tokitsukaze and Discard Items

Idea: tokitsukaze

Tutorial
Solution (by tokitsukaze)

1190B - Tokitsukaze, CSL and Stone Game / 1191D - Tokitsukaze, CSL and Stone Game

Idea: tokitsukaze

Tutorial
Solution (by tokitsukaze)
Solution (by skywalkert)

1190C - Tokitsukaze and Duel / 1191E - Tokitsukaze and Duel

Idea: teitoku, winterzz1

Tutorial
Solution (by quailty)
Solution (by skywalkert)
Solution (by winterzz1)

1190D - Tokitsukaze and Strange Rectangle / 1191F - Tokitsukaze and Strange Rectangle

Idea: tokitsukaze

Tutorial
Solution (by tokitsukaze)
Solution (by winterzz1)

1190E - Tokitsukaze and Explosion

Idea: chenjb, Subconscious

Tutorial
Solution (by chenjb)
Solution (by quailty)

1190F - Tokitsukaze and Powers

Idea: skywalkert

Tutorial
Solution (by skywalkert)
Solution (by quailty)
  • Vote: I like it
  • +96
  • Vote: I do not like it

Comments Comments (61)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Can someone explain div2D

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

    It is always optimal (except for on the first move) to take a stone from the smallest pile that isn't empty or one that would make a double. This ensures the sizes of two piles never "cross" and become the same in the middle of the game, which would imply that some player chose a losing move. In other words, the piles never change their order based on size. If there aren't any doubles to start with, this eventually ends up with the permutation described. Since there can't be any doubles after tokitsukaze's first move (or she would lose), do a bunch of casework for doubles on the first move. Then, count parity in total number of moves to reach the permutation.

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

      A bunch of casework may be avoided. You can instead enumerate her first possible move and see if there are two piles of the same size.

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

Div1F:

[for m=2^k] we can find a pseudo-primitive root g′ to use its powers to represent all the elements in the form of (4t+1) in S.

It's actually pretty known that one can always set $$$g' = 5$$$ for $$$m = 2^k$$$; for $$$k \ge 2$$$, each odd remainder is uniquely represented as a number of the form $$$\pm 5^j$$$. (AFAIR this can be proved by induction.) Each number of the form $$$5^j$$$ is 1 mod 4, and each number of the form $$$-5^j$$$ is 3 mod 4.

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

Can anyone explain div2 C please

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

    things you care about in any step is which item should i discard now and how many items discarded before this step and from which page should i start discarding this time, so we start with page part, it could be done using binary search, you want to find the minimum x which is satisfying this

    X*k >= a-b

    where a is the next item to be discarded and b is number of discarded items before this step , by doing this every time you discard all items in current page, start shifting items and do it again until you finish all the items

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

    we have to keep track of number of numbers discarded. let's denote it by cnt

    Now we can start the process of discarding the elements. The position of the current element p[i] on the page can be calculated as pos = ( p[i]- cnt)%k; if(pos == 0) pos = k; Now delete all the elements with p[ j ] — p[ i ] <= k — pos for j>i increment cnt for every discarded number and increment ans for each iteration.

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

can someone explain me the approach on how to come up with the formula in div2 C ll r=((p[now]-sum-1)/k+1)*k+sum;

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

    it just a sort of enumerating the right border to me, for p[now] , its right border is the current pages + deleted number ? forgive my poor eng

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

I am a bit confused with test 43 of div2D (Tokitsukaze, CSL and Stone Game):

2

1 1

So player 1 will take a stone, hence we have (0 1). Then player 2 will take another stone, so now we have (0 0). So player 2 loses (because two piles are the same number) and player 1 wins. However the answer gives player 2 as the winner. Am I missing something?

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

    Yes. You missed the first player's name.

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

      I don't understand. What do you mean?

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

        When I checked that test case, I found the answer(winner) is sjfnb, who is the first player.

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

          Ok I got it. I mistyped something in my code. Thanks.

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

I am a bit confused with div2D (Tokitsukaze, CSL and Stone Game): 4 1 1 1 1 it is the first peopeo win

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

    In that case the second player wins.

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

      why

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

        Because the first player cannot remove any stone — whatever stone the player removes, the state of stone piles will be like this :

        0 1 1 1(1 0 1 1, 1 1 0 1, 1 1 1 0 are all same)

        and because there are three piles that contain same number of stone, the first player loses.

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

        Because no matter how the first player removes the stones, there are always two piles contain the same number of stones ($$$1\ 1$$$)

        → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it -9 Vote: I do not like it

a

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

i personally felt that VASYA is much better than TOKITSUKAZE.

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

In Div2C for test case :-

15 3 5

3 15 9

Shouldn't the answer be 3 and not 2 (editorial code gives 2 as answer)? We first discard 3,then 9 and then 15. All 3 of them are on different pages at all times.

Edit:- I am sorry, I didn't see the constraints that input should be in ascending order.

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

    you may try 15 3 5 3 9 15

    for the second line is in ascending-order

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

      So what should be the answer ? It should be 3 right?

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

        yeah

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

          Your code/Editorial code gives answer as 2.

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

            I mean the input you offer is illegal (since the second line has to be ascending order)

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

Please someone explain 1191B solution by skywalkert

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

    $$$c[i][j]$$$ means the number of tiles with suit $$$i$$$ and digit $$$j$$$, which is $$$\leq 3$$$.

    If you want Toki to form a triplet with suit $$$i$$$ and digit $$$j$$$, it will need $$$(3 - c[i][j])$$$ extra tiles.

    If you want Toki to form a sequence $$$[(i, j), (i, j + 1), (i, j + 2)]$$$, it will require at least one tile in each type. !!c[i][j] in C/C++ can be explained as (c[i][j] == 0) == 0 or c[i][j] != 0, which is a boolean value.

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

How does the second player win with [4 4 4] as the given array in Div2 D

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

    No matter how the first player moves, there will 2 piles of equal count of stones after his move

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

In Problem 1C:

In contest

I added a brute force part on my random solution and passed system test.

I have no idea how to hack it or could prove it works.

here is the link: 56941913, hack is welcomed :p

and, what if the problem is xor 1 but not (or 1 / and 0) ?

could this be solved by random / other solution?

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

    Oh, in fact I forget to bruteforce on another side

    this is the new link: 56980588

    what I am think about is :

    is there any test that have only(few) valid movement

    and surely not only on sides but could be anywhere?

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

    Sure, here you are. 2 moves lead to draw out of 100002 possible and both moves are pretty far from the start. I'm sure a test with lower probability of success exists but this is enough.

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

      thank you, but could you please check my new comment?

      in fact I constructed similar test in my code

      (it's just I forget to spj another side : (

      it's mainly I found out it's hard to build test that is draw and not on sides

      so I question this :p

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

        Ok, that's trickier :D

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

I am a bit confused with div2d, if the piles are (0 1), the second player wins but this doesn't look to fit in any of the four cases described

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

    I finally understand. this falls in the case of the number of movements to obtain the permutation 0, .., n-1

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

For future contests, please do not make contestants write out long, random strings when outputting answers. Otherwise, I found (div. 2) contest enjoyable, with a nice problem balance.

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

Hello) Can you please explain me task 1191D (Tokitsukaze, CSL and Stone Game). Exactly why we need to do s+=a[i]-(i-1) instead of just s+=a[i] ? I really can't understand this moment.

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

    They are basically computing the sum of the stones on all piles, minus 0+1+2+..+n-1,the total number of stones remaining when the game is over.

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

      Is it because after taking 0+1+2...+n-1 stones we will have at least two heaps(piles) with simmilar number of stones? I do not understand why we need to minus exactly this numbers.

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

        The idea is, that when the game ends, the number of stones in each pile will be 0, 1, 2, ... n-1, since there cannot be two equally sized piles. Before the game ends each player is forced to take some stone (doesn't really matter which), without making two piles equal. So basically it is as if there was a single pile with SUM(piles)-(0+1+2+..+n-1) stones in it.

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

Can someone please explain 1190D strange rectangle problem... The editorial seems quite confusing. Thanks in advance :D

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

Alternatively, you can do it more advanced and check more efficiently like the following.

Shouldn't I check all powers of prime factors of $$$\varphi(m)$$$ here?..

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

    In case that $$$x^k | \varphi(m)$$$, where $$$x$$$ is a prime and $$$k$$$ is an integer greater than $$$1$$$, you may assume that prime factors of phi(m) in the mentioned (roughly written) pseudocode includes $$$x$$$ at least $$$k$$$ times, in other words, lambda = lambda / x may execute $$$k$$$ times or more.

    Anyway, you are right as well.

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

for problem D (div2) does anyone know a good source for game theory or how to be better at it

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

Please someone explain DIV2 D. I can't understand what to do after checking the 4 cases given in editorial.

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

In div2E ..in input case 4 1 0 0 1 1 ans should be quality as it doesn't matter which card Tokitsukaze changes..quality will have always 1 card to change and therefore win..Please explain

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

    You can choose '0' to '0', or '1' to '1'. So it is a draw.

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

In Tokitsukaze and Discard Items The following code gives correct answer on literally any other online IDE, but not on codeforces judge.

#include <bits/stdc++.h>

using namespace std;

int main(){
    long n, m, k;
    cin>>n>>m>>k;
    long curr_start=1;
    long curr_end=k;
    long curr_count=0;
    long ret=0;  
    long i=0;
    long temp;
    bool removed=false;
    cin>>temp;
    i++;
    while(i<=m){
        if(temp>curr_end){
            if(curr_count==0){
                if(removed){
                    ret++;
                    removed=false;
                }
                long mul;
                if((temp-curr_end)%k==0){
                    mul = (temp-curr_end)/k-1;
                }else{
                    mul = (temp-curr_end)/k; 
                }           
                curr_start=curr_end+mul*k+1;
                curr_end=curr_end + mul*k + k;
            }else{
                if(removed){
                    ret++;
                    removed=false;
                }
                curr_end+=curr_count;
                curr_count=0;
            }
        }else{
            removed=true;
            curr_count++;
            i++;
            cin>>temp;
        }
        // cout<<temp<<" "<<curr_count<<" "<<curr_start<<" "<<curr_end<<" "<<ret<<endl;
    }
    if(removed){
        ret++;
    }
    cout<<ret<<endl;

    return 0;
}

The test case it is failing is 

1000000000000000000 2 1
1 1000000000000000000

(Gives 0 for the Codeforces judge while the correct answer is 2)

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

    64 bit integer in c++ is long long not long. Maybe the problem is caused by it?

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

Can someone please explain 1191E — Tokitsukaze and Duel

How is the second inspection of the solution(by winterzz1) judged?

Sorry, my English is not that good.

Thanks in advance :D

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

In div2E .. in input case 4 1 0 0 1 1 ans should be quality as it doesn't matter which card Tokitsukaze changes..quality will have always 1 card to change and therefore win..Please explain

suppose in the first step tokistuke changes it to 1011 now quality should change it to 1111 for victory. why is he choosing for a draw??

Also can anybody tell the logic how to tackle?? i read the editorial but still was not able to figure it out.

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

    You can choose '0' to '0', or '1' to '1'. So it is a draw.

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

Prime number and root are good things! Without them problems like 1190F will become so difficult and complex. :(

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

https://codeforces.me/contest/1190/submission/57910087 can someone help me out with my soln I am getting wrong ans on 31st test case

→ Reply