tokitsukaze's blog

By tokitsukaze, 5 years ago,

1191A - Tokitsukaze и улучшение

Idea: tokitsukaze

Tutorial
Solution (by Claris)
Solution (by tokitsukaze)

1191B - Tokitsukaze и маджонг

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 и взрыв

Idea: chenjb, Subconscious

Tutorial
Solution (by chenjb)
Solution (by quailty)

1190F - Tokitsukaze и степени

Idea: skywalkert

Tutorial
Solution (by skywalkert)
Solution (by quailty)
• +96

| Write comment?
 » 5 years ago, # | ← Rev. 2 →   +4 Can someone explain div2D
•  » » 5 years 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.
•  » » » 5 years 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.
•  » » » » 5 years ago, # ^ |   0 Ohh that's brilliant!
 » 5 years 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.
 » 5 years ago, # |   0 Can anyone explain div2 C please
•  » » 5 years 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
•  » » 5 years 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.
 » 5 years 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;
•  » » 5 years 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 years 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?
•  » » 5 years ago, # ^ |   +1 Yes. You missed the first player's name.
•  » » » 5 years ago, # ^ |   0 I don't understand. What do you mean?
•  » » » » 5 years ago, # ^ |   0 When I checked that test case, I found the answer(winner) is sjfnb, who is the first player.
•  » » » » » 5 years ago, # ^ |   0 Ok I got it. I mistyped something in my code. Thanks.
 » 5 years 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
•  » » 5 years ago, # ^ |   0 In that case the second player wins.
•  » » » 5 years ago, # ^ |   0 why
•  » » » » 5 years 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.
•  » » » » 5 years 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$)
 » 5 years ago, # | ← Rev. 4 →   -9 a
 » 5 years ago, # |   +10 i personally felt that VASYA is much better than TOKITSUKAZE.
 » 5 years 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.
•  » » 5 years ago, # ^ |   0 you may try 15 3 5 3 9 15for the second line is in ascending-order
•  » » » 5 years ago, # ^ |   0 So what should be the answer ? It should be 3 right?
•  » » » » 5 years ago, # ^ |   0 yeah
•  » » » » » 5 years ago, # ^ |   0 Your code/Editorial code gives answer as 2.
•  » » » » » » 5 years ago, # ^ |   0 I mean the input you offer is illegal (since the second line has to be ascending order)
 » 5 years ago, # | ← Rev. 2 →   0 Please someone explain 1191B solution by skywalkert
•  » » 5 years 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.
 » 5 years ago, # |   0 How does the second player win with [4 4 4] as the given array in Div2 D
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 No matter how the first player moves, there will 2 piles of equal count of stones after his move
 » 5 years 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?
•  » » 5 years 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?
•  » » 5 years 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.
•  » » » 5 years 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
•  » » » » 5 years ago, # ^ |   0 Ok, that's trickier :D
 » 5 years 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
•  » » 5 years ago, # ^ |   0 I finally understand. this falls in the case of the number of movements to obtain the permutation 0, .., n-1
 » 5 years 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.
•  » » 5 years ago, # ^ |   +3 Thank you for your advice:3
 » 5 years 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.
•  » » 5 years 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.
•  » » » 5 years 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.
•  » » » » 5 years 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.
•  » » » » » 5 years ago, # ^ |   0 thanks a lot)
•  » » » » » » 5 years ago, # ^ |   0 You're welcome!
 » 5 years ago, # |   0 Can someone please explain 1190D strange rectangle problem... The editorial seems quite confusing. Thanks in advance :D
 » 5 years 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?..
•  » » 5 years 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.
 » 5 years ago, # | ← Rev. 3 →   +1 for problem D (div2) does anyone know a good source for game theory or how to be better at it
 » 5 years ago, # |   0 Please someone explain DIV2 D. I can't understand what to do after checking the 4 cases given in editorial.
 » 5 years 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
•  » » 5 years ago, # ^ |   0 You can choose '0' to '0', or '1' to '1'. So it is a draw.
 » 5 years 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<
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 64 bit integer in c++ is long long not long. Maybe the problem is caused by it?
 » 5 years 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
 » 5 years 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.
•  » » 5 years ago, # ^ |   0 You can choose '0' to '0', or '1' to '1'. So it is a draw.
 » 5 years ago, # |   0 Prime number and root are good things! Without them problems like 1190F will become so difficult and complex. :(
 » 5 years 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