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

Автор tokitsukaze, 5 лет назад, По-английски

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)
  • Проголосовать: нравится
  • +96
  • Проголосовать: не нравится

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

Can someone explain div2D

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

    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.

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

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.

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

Can anyone explain div2 C please

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

    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

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

    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.

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

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;

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

    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

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

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?

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

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

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

    In that case the second player wins.

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

      why

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

        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.

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

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

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

a

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

i personally felt that VASYA is much better than TOKITSUKAZE.

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

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.

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

Please someone explain 1191B solution by skywalkert

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

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

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

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

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

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

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

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?

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

    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?

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

    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.

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

      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

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

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

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

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

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

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.

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

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.

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

    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.

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

      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.

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

        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.

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

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

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

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

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

    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.

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

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

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

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

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

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

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

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)

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

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

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

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.

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

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

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

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