### tokitsukaze's blog

By tokitsukaze, 13 months ago, ,

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)

Idea: tokitsukaze

Tutorial
Solution (by tokitsukaze)

Idea: tokitsukaze

Tutorial
Solution (by tokitsukaze)
Solution (by skywalkert)

Idea: teitoku, winterzz1

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

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

 » 13 months ago, # | ← Rev. 2 →   +4 Can someone explain div2D
•  » » 13 months ago, # ^ |   +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.
•  » » » 13 months ago, # ^ |   +2 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.
•  » » » » 13 months ago, # ^ |   0 Ohh that's brilliant!
 » 13 months ago, # | ← 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.
 » 13 months ago, # |   0 Can anyone explain div2 C please
•  » » 13 months ago, # ^ | ← 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
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 we have to keep track of number of numbers discarded. let's denote it by cntNow 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.
 » 13 months ago, # |   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;
•  » » 13 months ago, # ^ |   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 weeks ago, # ^ |   0 I think this is more understandable, you can also see it william lin's youtube channel.Video: Video Link void Solution() { int n, m, k; sf3(n,m,k); //taken input seti s; //declared a set of integers REP(i,m) { int num; sf1(num); num--; //input reduced by 1 for pageno calc s.insert(num); } int di = 0, ans = 0; while(di < m) { int page = (*s.begin()-di)/k; //evaluating page no while(SIZE(s) and (*s.begin()-di)/k <= page) { s.erase(s.begin()); } di = m - SIZE(s); //items remaining ans++; } pf("%lld\n", ans); } (I am posting it for any of you guys who will see editorial when upsolving, thanks.)
 » 13 months ago, # |   0 I am a bit confused with test 43 of div2D (Tokitsukaze, CSL and Stone Game):21 1So 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?
•  » » 13 months ago, # ^ |   +1 Yes. You missed the first player's name.
•  » » » 13 months ago, # ^ |   0 I don't understand. What do you mean?
•  » » » » 13 months ago, # ^ |   0 When I checked that test case, I found the answer(winner) is sjfnb, who is the first player.
•  » » » » » 13 months ago, # ^ |   0 Ok I got it. I mistyped something in my code. Thanks.
 » 13 months ago, # |   0 I am a bit confused with div2D (Tokitsukaze, CSL and Stone Game): 4 1 1 1 1 it is the first peopeo win
•  » » 13 months ago, # ^ |   0 In that case the second player wins.
•  » » » 13 months ago, # ^ |   0 why
•  » » » » 13 months ago, # ^ |   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.
•  » » » » » 13 months ago, # ^ |   0 Ok I got it.thanks
•  » » » » 13 months ago, # ^ | ← 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$)
•  » » » » » 13 months ago, # ^ |   0 Ok I got it.thanks
 » 13 months ago, # | ← Rev. 4 →   -9 a
 » 13 months ago, # |   +10 i personally felt that VASYA is much better than TOKITSUKAZE.
 » 13 months ago, # | ← Rev. 5 →   0 In Div2C for test case :-15 3 53 15 9Shouldn'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.
•  » » 13 months ago, # ^ |   0 you may try 15 3 5 3 9 15for the second line is in ascending-order
•  » » » 13 months ago, # ^ |   0 So what should be the answer ? It should be 3 right?
•  » » » » 13 months ago, # ^ |   0 yeah
•  » » » » » 13 months ago, # ^ |   0 Your code/Editorial code gives answer as 2.
•  » » » » » » 13 months ago, # ^ |   0 I mean the input you offer is illegal (since the second line has to be ascending order)
 » 13 months ago, # | ← Rev. 2 →   0 Please someone explain 1191B solution by skywalkert
•  » » 13 months ago, # ^ | ← 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.
•  » » » 13 months ago, # ^ | ← Rev. 2 →   0 Thank you so much for explaining !!c[i][j]
 » 13 months ago, # |   0 How does the second player win with [4 4 4] as the given array in Div2 D
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 No matter how the first player moves, there will 2 piles of equal count of stones after his move
 » 13 months ago, # |   0 Can someone explain what is happening in the for loops in quailty's code for 1191E - Tokitsukaze and Duel
 » 13 months ago, # | ← Rev. 2 →   0 In Problem 1C: In contestat the beginning I got a wrong understanding on problemand thinks that in each step we can choose a range and xor 1 on each bitin this case I don't know how to work and just write an random solutionbut I got wa17. (I don't know how did it passed 16 pretests xdafter read problem again I got real meaningbut I have notime to code and have to just fix my random solution and submit itand in the end I got an FST on test 59 : (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 :pand, what if the problem is xor 1 but not (or 1 / and 0) ?could this be solved by random / other solution?
•  » » 13 months ago, # ^ |   0 Oh, in fact I forget to bruteforce on another side this is the new link: 56980588what I am think about is :is there any test that have only(few) valid movementand surely not only on sides but could be anywhere?
•  » » 13 months ago, # ^ |   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.
•  » » » 13 months ago, # ^ |   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 sidesso I question this :p
•  » » » » 13 months ago, # ^ |   0 Ok, that's trickier :D
 » 13 months ago, # |   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
•  » » 13 months ago, # ^ |   0 I finally understand. this falls in the case of the number of movements to obtain the permutation 0, .., n-1
 » 13 months ago, # |   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.
•  » » 13 months ago, # ^ |   +3 Thank you for your advice:3
 » 13 months ago, # |   0 someone pls explain how we got that formula in div 2 C in easy way
 » 13 months ago, # |   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.
•  » » 13 months ago, # ^ |   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.
•  » » » 13 months ago, # ^ |   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.
•  » » » » 13 months ago, # ^ |   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.
•  » » » » » 13 months ago, # ^ |   0 thanks a lot)
•  » » » » » » 13 months ago, # ^ |   0 You're welcome!
 » 13 months ago, # |   0 Can someone please explain 1190D strange rectangle problem... The editorial seems quite confusing. Thanks in advance :D
 » 13 months ago, # |   0 Where is problem rating?
 » 13 months ago, # |   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?..
•  » » 13 months ago, # ^ |   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.
 » 13 months ago, # | ← Rev. 3 →   +1 for problem D (div2) does anyone know a good source for game theory or how to be better at it
 » 13 months ago, # | ← Rev. 2 →   0 Can someone please explain how in problem div2 D you arrived at the conclusion that at the end we will have permutations of 0 to n-1?
 » 13 months ago, # |   0 Please someone explain DIV2 D. I can't understand what to do after checking the 4 cases given in editorial.
 » 13 months ago, # |   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
•  » » 13 months ago, # ^ |   0 You can choose '0' to '0', or '1' to '1'. So it is a draw.
•  » » » 13 months ago, # ^ |   0 yeah..understood thanks
 » 13 months ago, # | ← 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 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<
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 64 bit integer in c++ is long long not long. Maybe the problem is caused by it?
•  » » » 13 months ago, # ^ |   0 Wow,it worked. Thank you mate.Any idea why the particular test case wasn't working? Because it was working for me locally and on ideone/Codechef IDE as well.
 » 13 months ago, # |   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
 » 13 months ago, # |   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 explainsuppose 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.
•  » » 13 months ago, # ^ |   0 You can choose '0' to '0', or '1' to '1'. So it is a draw.
 » 13 months ago, # |   0 Prime number and root are good things! Without them problems like 1190F will become so difficult and complex. :(
 » 12 months ago, # |   0 https://codeforces.com/contest/1190/submission/57910087 can someone help me out with my soln I am getting wrong ans on 31st test case
 » 12 months ago, # |   0 On problem "Tokitsukaze and Discard Items", we use 2 pointers technique, right?