### pikmike's blog

By pikmike, history, 23 months ago,

1065A - Vasya and Chocolate

Tutorial
Solution (Ajosteen)

1065B - Vasya and Isolated Vertices

Tutorial
Solution (Ajosteen)

1065C - Make It Equal

Tutorial
Solution (Ajosteen)

1065D - Three Pieces

Tutorial
Solution (PikMike)

1065E - Side Transmutations

Tutorial
Solution (PikMike)

1065F - Up and Down the Tree

Tutorial

1065G - Fibonacci Suffix

Tutorial
Solution (BledDest)

• +43

 » 23 months ago, # |   0 44220948Why does my D WA on test 25? I had a similar solution, except I bruteforced the shortestdistance instead of using bds/djikstras, and used a bunch of selections for the dp instead of a pair.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +11 You probably didnt consider that in the optimal solution you need to change the chess piece on the way between position a and b and not only change pieces on position a or b?
•  » » » 23 months ago, # ^ |   -6 but a rook can always reach your desired position in 2 moves, so even if you switch to a rook at the beginning your total cost will be 3Now if you're using a bishop and move to a position which isn't your destination, and switch to another counter and then move to your desired position, your total cost would still be 3The same goes for switching between other counters. Your maximum cost will always be 3 (which is the same as switching to a rook at the beginning and then reaching your desired position)
•  » » » » 23 months ago, # ^ |   +8 4 14 10 3 7 4 15 11 13 12 1 16 9 2 5 6 8 Consider, when you are in number 2 with a bishop. You can go to number 3 with a rook in 3 steps: replace bishop with rook, goto 14, goto number 3. You can go to number 3 with a knight in 3 steps: go back to 1 with bishop, replace bishop with knight, goto number 3. (Note that, you cannot replace bishop with knight in number 2 because, in that case, you need 4 steps to go to number 3)
•  » » » » 16 months ago, # ^ |   0 Well, what if you number the positions as the positions of a knights tour? Then the optimal solution would be to start with a knight and the distance between each location would be 1.
 » 23 months ago, # | ← Rev. 2 →   +16 O((N + M) * M) or O(M * (M + log(N))) solution for G:Same solution but changing 1 part, the part of counting the number of occurences. Instead of using an automaton, keep pref[i] ans suf[i] as the M first characters of the prefix/suffix of the i-th string. Using this, freq[i] = freq[i-2] + freq[i-1] + occurences that use the suf[i-2] + pref[i-1]. This gives us an O(N * M^2) solution like in the editorial. But you can note that starting from one point (the position where |F[i]| >= M), pref[i] == pref[i + 2] and suf[i] == suf[i + 1]. This means that the "occurences that use the suf[i-2] + pref[i-1]" will actually repeat with period 2. So you can calculate it in one phase until that point, the cost of this is O(F[0] + F[1] + F[2] + ... + F[i]) = O(F[i + 1]) = O(M) and from that point on, you can reuse the number of occurences that happened in the previous calculations (or do 4 more just to be safe and use from that point on, doesn't change the complexity). Total complexity: O((N * M) * M) with one phase (additional character) happening in O(M + N) because you need to calculate the borders for KMP. You can actually use this fact to create a linear recurrence relation for freq[i] and use matrix exponentiation (the column matrix keeps freq[i], freq[i-1], the transitions and keep swapping them) starting from the point that it repeats, this would result in a O(log(M) + M + log(N) * 4^3) phase per character in the answer. The log(M) comes from the fact that fib is exponential, so the point that it starts repeating is O(log(M)). This would result in a O(M * (M + log(N))) solution.Code for O((N + M) * M) solution: http://codeforces.com/contest/1065/submission/44225229Edit: If there's an occurence in the transition, you can also keep calculating until it breaks K. It will break K in O(logK) steps and if there's no occurence, you just break. So I guess the second part wouldn't be necessary for the O(M^2) complexity.
•  » » 23 months ago, # ^ | ← Rev. 2 →   +5 That also implies that a big N doesn't matter as can be seen here: http://codeforces.com/contest/1065/submission/44226008. n = min(n, 100) works. To be more exact, the bound on N mattering would be O(log(M) + log(K)).
 » 23 months ago, # |   0 https://codeforces.com/contest/1065/submission/44147964For C,my approach is a bit similar can anyone help me,where i am wrong?
 » 23 months ago, # |   +1 Can someone explain d.
 » 23 months ago, # |   0 Can anyone please suggest what is wrong with my approach? SubmissionI am first sorting the input array in descending order followed by storing a vector of blocks sliced to reach the subsequent lower level. For instance, if the input array is 4 3 2 2 1 my vector is 1 2 4 5 Finally, I am traversing to find out if a single or combination of blocks is less than or equal to k or not and incrementing the counter as a result.
 » 23 months ago, # |   0 Hi! I have a problem can anybody help? if u submit this solution for problem D with MS C++ u get accept! Link to code! but gnu++ gives WA! do u know why?
 » 23 months ago, # |   +1 Can E solve by polya?
•  » » 23 months ago, # ^ |   +1 Yes, you can. 44419650As the editorial said every subset of segments [0..l1), [l1, l2), …, [lm−1, lm) is achievable. There is a bijective relation between the set of subsets of segments and the set of transformations G and every transformation add An - k where k is the sum of the cardinalities of the segments in the associated subset.
•  » » » 23 months ago, # ^ |   +1 Yes! Actually, the formula solve by polya is the same as the official tuitual. Wonderful!
•  » » » » 22 months ago, # ^ |   -6 what is polya?
•  » » » » » 22 months ago, # ^ |   0 This may help you https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem
 » 23 months ago, # |   0 This for problem D, can anyone tell me why my solution times out (http://codeforces.com/contest/1065/submission/44417842)
 » 23 months ago, # |   -6 In the tutorial of Problem E: cnt function : why is there *(mod+1)/2 instead of /2 directly in the return. I am getting wrong answer with /2 but I am not able to understand why.
 » 22 months ago, # | ← Rev. 2 →   0 Why this this solution for problem 1065C is not correct ?Since the attainable equal height is the Smallest number.then Number of Chops can be : ceil((SumOfHeight - N * minHeight) / K)
•  » » 16 months ago, # ^ |   0 Because we cant remove blocks parially from any particular height
 » 22 months ago, # | ← Rev. 2 →   -6 Problem D can be solved with a single BFS using a state of four dimensions: current x, current y, piece type, current square we are at. The result is the minimum among final states. https://codeforces.com/contest/1065/submission/46351519
 » 19 months ago, # |   0 Can someone please explain how to solve "1065E — Side Transmutations"? PikMike forgot to explain what l is?Sorry for my amazingly bad english.
 » 5 weeks ago, # |   0 Can anyone explain 1065C?I didn't understand the editorial.thanks in advance.
•  » » 2 weeks ago, # ^ |   0 here is my code that may help u. if u don't understand then sorry. https://codeforces.com/contest/1065/submission/91731954
 » 2 weeks ago, # |   -8 Problem E is so nice. A subtle change in perspective, by viewing the string as a whole, solves it instantly!
 » 2 weeks ago, # |   0
•  » » 2 weeks ago, # ^ |   0
•  » » » 2 weeks ago, # ^ |   0 ![ ]()
•  » » » » 2 weeks ago, # ^ |   0 As memes are trending in this comment section I thought lets start with basics