Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### Akikaze's blog

By Akikaze, 5 weeks ago, ,

All themes written by Akikaze (I am the only one in the team playing Cytus II anyway :D).

## 1293A - ConneR and the A.R.C. Markland-N

Author: xuanquang1999
Development: xuanquang1999, Akikaze
Editorialist: xuanquang1999, Akikaze

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1293B - JOE is on TV!

Author: Akikaze
Development: Akikaze
Editorialist: Akikaze

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1292A - NEKO's Maze Game

Author: xuanquang1999
Development: xuanquang1999, Akikaze
Editorialist: Akikaze

Tutorial
Video editorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1292B - Aroma's Search

Author: Akikaze feat. xuanquang1999
Development: xuanquang1999, Akikaze
Editorialist: Akikaze

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1292C - Xenon's Attack on the Gangs

Author: xuanquang1999
Development: xuanquang1999
Editorialist: xuanquang1999

Tutorial
Solution (xuanquang1999, C++)
Solution (xuanquang1999, Java 8)

## 1292D - Chaotic V.

Author: Akikaze
Development: Akikaze
Editorialist: Akikaze

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, PyPy 3)

## 1292E - Rin and The Unknown Flower

Author: low_ (Sooke Remix)
Development: low_, Sooke, Akikaze
Editorialist: low_

Tutorial
Solution (Akikaze, C++)
Solution (Akikaze, Java 8)
Solution (Akikaze, Python 3)

## 1292F - Nora's Toy Boxes

Author: xuanquang1999 × MofK
Development: xuanquang1999
Editorialist: xuanquang1999

Tutorial
Solution (xuanquang1999, C++)
Solution (xuanquang1999, Java 8)
Solution (xuanquang1999, PyPy 3)

• +192

 » 4 weeks ago, # |   +13 When the codes will be available for tutorials?
•  » » 4 weeks ago, # ^ |   +19 After system testing. I want to be sure the solutions worked correctly (even though I tested them quite thoroughly on Polygon).
 » 4 weeks ago, # |   +109 If you play Music Game well, you must have quick hands.If you have quick hands, maybe you'll publish the fastest editorial!Thanks for the fast editorial!
•  » » 4 weeks ago, # ^ |   +34 You already knew how fast the editorial of #538 was out right? :D
 » 4 weeks ago, # |   0 Can someone explain C for div2 ?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 There are two cases in which it will not be possible to reach from 1,1 to 2,n, it will be if a diagonal or a straight vertical line is all lava, so keep track of current lava, and each time you get a new query chech if it creates or removes any diagonals. Maintain a count variable that will keep a track of such diagonals and vertical blockages.Here is my solution https://codeforces.com/contest/1293/submission/69125834
•  » » » 4 weeks ago, # ^ |   0 ooh,i see, thanks <3
 » 4 weeks ago, # |   0 In problem D, I run my code and the result on test 1 is 3 but codeforces gives my result is 34 Can someone help me? Sorry for my bad english
•  » » 4 weeks ago, # ^ |   +3 maybe you define a variable and have not set it to zero and it takes a random value from memory and memory of your system and codeforces are different !
•  » » » 4 weeks ago, # ^ |   +3 Thanks a lots
 » 4 weeks ago, # |   0 Thanks for the fast tutorials and the music games!
 » 4 weeks ago, # | ← Rev. 2 →   +11 As a rhythm game enthusiast, I was happy to see a round having rhythm game concept. Thanks for the round and fast editorial too!
 » 4 weeks ago, # |   +146 after the round
•  » » 4 weeks ago, # ^ |   +13 *angry cyan sounds*
 » 4 weeks ago, # |   +36 Sidenotes: For problem D1E, the key to solve this problem was to write a lot on scratch paper and try everything that comes to your mind possible, even if it sounds stupid. That's the key for most constructive problems xDMy initial idea was that the limit for all queries is 5/3, Sooke said that it can be lowered to 3/2, but then in the middle of the night (6 months ago), I came up with a solutions that works for 1.4! But then we had to scrap the initial limit for n, which is [3, 100].
 » 4 weeks ago, # | ← Rev. 3 →   +45 There is a simple, elegant solution for Div1E when n is at least 5. Unfortunately, I could not find a way to make it work when n = 4.First ask CC, CH, and CO. This way, all C's are revealed except for (possibly) a C as the last letter.Then ask OH and HH. Combined with the information we get from the CH query, this allows us to identify the locations of all H's except for (possibly) a H as the first letter.We have now found all C's and H's in the interval [2, n-1]. Everything else in the interval is an O. Now we have to find the first and last letters.At this point, if the first letter is still unknown, it can only be a H or an O; if the last letter is still unknown, it can only be a C or an O. Therefore there are up to 4 possibilities for these 2 letters (first and last). We ask any arbitrary 3 of these possibilities using queries of length n. If we still do not find the answer after these 3 queries, the answer has to be the remaining possibility that we did not ask.The total energy used is 5/4 + 3/n^2, which is acceptable when n is at least 5.UPDATE: Solved the n=4 case. The approach I used was to query CH, CC, CO, OH, HHH, OOO, then whenever we find some characters that match (or finish these 6 queries without finding any), we switch to brute force, searching for strings that are consistent with the results of previous queries. The energy usage analysis is too complex for me to provide in full here.My submission: https://codeforces.com/contest/1292/submission/69161739
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +16 $N=4$ can be solved by bruteforcing decision trees, maybe with pruning branches that obviously don't work if it's too slow.I have a solution that works for $N \ge 5$ too: ask for CC, if it exists then finish the rest of the string with cost $\le 2\sum_{i=3}^{\infty} i^{-2}$ ask for HCO, HCH, OCH, OCO; if one of them exists then finish the rest of the string with cost $\le 2\sum_{i=4}^{\infty} i^{-2}$ now there's no C except maybe on the border of the string, ask for HH and OO and if one of them exists, the middle of the string is completely known and only 2 more questions are needed, with cost $N^{-2}+(N-1)^{-2}$ the last case is when there's no CC, HH, OO, so the string has to look like (C|H)OHOH...H(C|O), (C|H)OHOH...HO(C|H) + strings generated from them by swapping H, O; ask for OHOH, HOHO and if neither exists, it has C at both ends; either way, one more question is enough, with total cost $1/4+4/9+2/4+2/16+N^{-2} \lt 1.36$
 » 4 weeks ago, # |   -8 Can anyone tell me why my solution is giving TLE for problem A https://codeforces.com/contest/1293/submission/69109563
•  » » 4 weeks ago, # ^ |   +3 if((s-i)>=1) { if(se.find(s+i)==se.end()) { cout<
•  » » » 4 weeks ago, # ^ |   0 got it..thnx
 » 4 weeks ago, # | ← Rev. 2 →   +30 For Div. 1 D — Chaotic V., I have a better solution:Consider find the branch with most occurences once, from node $1$.Because we have $\max p [p | x!] = \text{the biggest prime number less than or equal to } x$ for $x \ge 2$, so two number $a, b$ are in the same branch iff their previous primes(including itself) are the same.That is, $a$ and $b$ are in the same prime gap.So we pre-work $\mathrm{last}[x] = \text{previous prime of } x$, and find the most occurences prime gap. Let's say, $[p_x, p_{x + 1})$, then the distinct numbers are reduced to $p_{x + 1} - p_x$.Then we only use $k_i \in [p_x, p_{x + 1})$ to construct the tree structure, which is relatively small.So we have the complexity of $\mathcal O (MAXK \ln \ln MAXK \cdot \text{largest prime gap in } MAXK)$.Then according to A005250 and A002386, we can solve the problem even if $MAXK \le {10}^5$.Possible optimization: use virtual trees, maybe can reduce the number of nodes.
•  » » 4 weeks ago, # ^ |   0 But how do you construct the tree structure for the reduced set without factorizing all numbers below $k_i$ anyway?It would certainly be nice to have access to persistent maps/multisets...
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +18 My alternative solution using a virtual tree.(To avoid confusion, I'll use $K$ to denote $MAXK$ in what follows.)Note that $1!,2!,\dots,k!$ is a dfs-order(a.k.a Eulerian order) of the tree. Thus, computing the LCA of $k!$ and $(k+1)!$ can be done by finding the number of $k!$'s prime factors that are not less than $(k + 1)$'s largest prime factor, where a BIT works. After factorizing $1$ ~ $K$ and maintaining the BIT, we can build the virtual tree in $O(K)$, since the virtual tree has at most $2K$ nodes.Then we just add weights to the nodes according to the input. The weighted centroid of the virtual tree is the proper node $P$.The bottleneck is factorizing $1$ ~ $K$. In worst case it takes $O(K\sqrt{K})$ time, but in practice it runs rather fast. A small questionCan anybody prove whether the complexity of factorizing $1$ ~ $K$ is less than $O(K\sqrt{K})$? I test locally and find my whole program of this problem finishes in 1s even if $K=500000$.
•  » » » 4 weeks ago, # ^ |   +8 Very good solution! I think you can offline factorize $1 \sim K$ in $\mathcal O (K \log \log K)$?
•  » » » » 4 weeks ago, # ^ |   +8 Oh I see! Using Eratosthenes's Sieve works, I suppose.(I must be a fool this morning...
•  » » 4 weeks ago, # ^ |   0 Update : After carefully reading the standard program, I realized my solution is just a tiny optimization of the official solution, but it indeed optimized.Combining 11235813213455's solution (virtual trees) and my "prime gap" observation, I think we can get an $\mathcal O (N + K \log \log K)$ solution? ($\log \log$ comes from Eratosthenes's Sieve, and the number of prime factors of $k!$(factorial of $k$), check Wikipedia : Prime omega function for more information)
 » 4 weeks ago, # |   0 Thanks for the useful editorial
 » 4 weeks ago, # |   +36 My solution for E (passed in upsolving):First of all, once we know that $t$ is a substring of $s$ from position $pos$, we can find the entire string for $2\sum_{i=|t|+1}^{n}\frac{1}{i^2}$ just by trying to add all letters one by one to the left or to the right and checking if the resulting string occurs in the required position. If $|t| = 2$ then this value is approximately $0.7502654672430585$.Let's ask about CO and CH. If at least one of these strings is present in $s$ as a substring, then we apply the algorithm above, using only $\approx 1.25$. Otherwise our string is of type [OH]*C*.Let's find all occurrences of OH and HO (cost $1$ so far). If there are none then our string is (O*|H*)C*. We use that $n\geq 4$ and ask about CCC, if there is none then about OOC and HHC, if there is none then about HHH...H and OOO...O, otherwise we know the string. If there is CCC then we ask about OCCC and HCCC and find the string.If there are OH or HO then we find the whole string before the last block of non-C letter. Then we just iterate over all possible counts of C in the end and each time ask about the whole string.
 » 4 weeks ago, # |   0 small doubt: (consider s-x is zero here) if i write my cpp code like  if ((1 <= (s - x) && (s - x) <= n)){ auto it = find (lstk.begin(), lstk.end(), s - x); if (it == lstk.end()) { cout << x << endl; break; } } then the compiler does not go into the for loop but it if it is like:  if ((1 <= (s - x) <= n)){ auto it = find (lstk.begin(), lstk.end(), s - x); if (it == lstk.end()) { cout << x << endl; break; } } and x is zero, the compiler goes into the if statement. anybody know why this is happening?
•  » » 4 weeks ago, # ^ |   0 the compiler will calculate 1<=(s-x) first and the result is either 1 or 0 and then calculate1<=n or 0<=n so this condition is always true.
 » 4 weeks ago, # |   +5 Anyone noticed ? Blog was written 6 days ago.
•  » » 4 weeks ago, # ^ |   +52 Yes. I have a weird habit of preparing things early, then publishing at the right moment.
 » 4 weeks ago, # | ← Rev. 3 →   0 Very nice problems! (except too weak pretests in Div2 D)
 » 4 weeks ago, # |   +3 The complete solution set has arrived (except xuanquang1999's Python solution in Div1C, guess he's slept already so I'll contact him later).Again, thanks for your participation.
 » 4 weeks ago, # |   0 in Editorail of D how it is known that if u Move from point i to j it will cover all node from i to j?
•  » » 4 weeks ago, # ^ |   +3 For three arbitrary points on the same line, namely $p_1$, $p_2$, $p_3$, we can easily see that the Manhattan distance from $p_1$ to $p_3$ is the sum of distances from $p_1$ to $p_2$ and from $p_2$ to $p_3$.Applying for a whole segment of points will result in the same outcome, i.e. the total distance to move from point $i$ to $i+1, \ldots, j$ will be the same as moving straight from $i$ to $j$.
 » 4 weeks ago, # |   0 can someone explain why long double cannot solve div2B,even cannot pass the sample.it's right on my computer,but wa when i submit.https://codeforces.com/contest/1293/submission/69115420,https://codeforces.com/contest/1293/submission/69113841
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 While adding t / i to s in your code, you should cast to long double first. Should be s += (long double) t / i;
•  » » » 4 weeks ago, # ^ |   0 t is already long double,no need to cast it
•  » » » » 4 weeks ago, # ^ | ← Rev. 3 →   0 But i isn'tJust do it the way I mentioned above and it will work.OK I think I get your confusion, I'm casting the whole calculation and not just t.Link to submission here
•  » » » » » 4 weeks ago, # ^ |   0 it cannot work,i tried cast t to long double and the whole calculation,both wa,you can submit it
•  » » » » » » 4 weeks ago, # ^ |   0 I linked my submission above
•  » » » » » » » 4 weeks ago, # ^ |   0 thanks a lot,but these two submit is also wrong answer,(https://codeforces.com/contest/1293/submission/69166394)(https://codeforces.com/contest/1293/submission/69164992)
 » 4 weeks ago, # |   0 For div2 B, Can someone please give a mathematical proof for why not defeating all (n-1) opponents at once would not produce better result?Mathematically why, (n-1)/n +1 < (1/n + 1/(n-1) + ... + 1)I tried but failed to prove it.
•  » » 4 weeks ago, # ^ |   0 as i don't know how to write summation symbol so i'm giving a piece of code: sum = 0; for(i = 1; i <= n; i++) { sum += 1.0/(n-(n-i)); }hope you got the answer ^_^
•  » » » 4 weeks ago, # ^ |   0 Thanks for replying, but I guess you didn't get my question.I wanted a mathematical proof for the inequality I have written above, not the code for it.
•  » » 4 weeks ago, # ^ |   +2 For every $i \leq n$, it is true that $1/i \geq 1/n$ Then, $1/2 \geq 1/n$ $1/3 \geq 1/n$ $...$ $1/n \geq 1/n$ If you sum them, you have $1/2 + 1/3 + ... + 1/n \geq (n-1)/n$. Finally, add one on each side $(n-1)/n + 1 \leq 1/n + 1/(n - 1) + ... + 1$
•  » » » 4 weeks ago, # ^ |   0 Thanks, I got it.
•  » » 4 weeks ago, # ^ |   +1 view it this way to get 1 we need for sure to output 1/1 so if n=4 I could do 4/4 from the first round but if I kept decreasing 4 to 3 then two then one I will find out that the best solution is to always decrease n and I will end up with 1/1 in the end that's of course not a very mathimatical prove but more of a greedy prove but if you think it in reverse you can some how recursivly prove it .
•  » » » 4 weeks ago, # ^ |   0 Thanks..this is quite intuitive.
 » 4 weeks ago, # |   +63 I have a simpler solution for div1 E.For n>=5, query "CC","OC","HC","HO" and "HH". After that, all 'C' except that in S[1] and all 'H' except that in S[n] will be discovered. So we know S[2..n-1], and S[1] and S[n] both only have two possible values. The total cost is no more than $5\cdot\frac14+\frac1{(n-1)^2}+\frac1{n^2}\leq1.3525$.For n=4, at first query "CC","OC","HC" and "HO". If S[1] or S[4] is discovered, then do the remaining part of the above algorithm. The total cost is no more than $5\cdot\frac14+\frac1{16}\leq1.3125$. Otherwise, if S[2] and S[3] are both discovered, instead of querying "HH", we go to find S[n] and S[1] immediately. The total cost is no more than $4\cdot\frac14+\frac19+2\cdot\frac1{16}<1.2362$. Otherwise no positions are not discovered and we still query "HH". If we find "HH", S[4] must be discovered, so the total cost is still no more than $1.3125$. If not, S[2..3]="OO". Then we can determine both S[1] and S[4] by querying "OOO". The total cost is no more than $5\cdot\frac14+\frac19<1.3612$.
 » 4 weeks ago, # |   +5 It's always nice to have editorials with multiple coding languages, really helps newbie's.
 » 4 weeks ago, # | ← Rev. 2 →   +1 Can someone help me? my code for div. 2D is failing for test case 44. I am inserting first 55 nodes in an array and using binary search on it, for finding the element with lowest distance. code
 » 4 weeks ago, # | ← Rev. 2 →   0 My submission for D is failing system tests because of the upper limit I have set while calculating the co-ordinates of the points. It passed when I set the upper limit as 3e16 but failed when I set it as 1e16+10 or 1e17. Can anyone please help me in finding a possible reason for this? I am unable to figure out how to set an appropriate limit as per the given constraints.
•  » » 4 weeks ago, # ^ |   +13 1e17 fail because 1e17*200 exceeds long long limit1e16 fail because you can get to points like (1e16,2e16) if t=1e16 and (x,y)=(1e16,1e16)
•  » » » 4 weeks ago, # ^ |   0 Ahh okay. Understood my stupidity. So an upper limit just above 2e16 works. Thanks for your help!
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 It's probably because $10^{17} \cdot 100$ would overflow a 64-bit integer.
•  » » » 4 weeks ago, # ^ |   0 Understood. Thanks!! :D
 » 4 weeks ago, # |   +12 Really nice explanations and clean code, thanks for your effort! I've personally really enjoyed this round:D
 » 4 weeks ago, # |   0 Pretty nice set of questions!! Looking forward to the next round
 » 4 weeks ago, # | ← Rev. 3 →   0 Can someone tell me why i am receiving TLE veridict on C problem of Division 2.My algo is also solving the problem in O(n+q).
•  » » 4 weeks ago, # ^ |   0 Interesting enough, both my solution and yours run faster in Python 3 than in PyPy 3.However, my advice would be ditching out the dict (since a frequency 2D array can be constructed, using dict might be an overkill and waste a few more resources than needed).
•  » » » 4 weeks ago, # ^ |   0 Got it.Thank you.
 » 4 weeks ago, # |   0 Any alternative approach to solve Div2 D?
 » 4 weeks ago, # |   0 can anyone explain logic behind total no of points we need to find out that we can cover before t in Div2D?
 » 4 weeks ago, # |   0 In problem C, i tried looping for i ~ i+k+100 then checking the begin and end of the array then checking if either the floor (s-i) or the floor(s+i) doesn't exists in the array of close restaurants. but it got WA on test 2, can anyone help me fix the logic? :/
 » 4 weeks ago, # |   0 please someone explain approach of Div-2 E in easy language?
 » 4 weeks ago, # |   0 1292A — NEKO's Maze Game CAN ANYONE HELP ME SOLVE THIS QUESTION ,IM STILL A NOOB AT CODING TLE IS KILLING ME HERES MY APPROACH https://codeforces.com/contest/1292/submission/69254469
 » 4 weeks ago, # |   0 Can anyone please explain me how to implement the idea of question C (NEKO's Maze Game)? I did this https://codeforces.com/contest/1293/submission/69209978 but got TLE. Please help.
 » 4 weeks ago, # |   0 can someone explain to me div 2 D (i understand how we got all of our ax,ay only)
•  » » 4 weeks ago, # ^ | ← Rev. 6 →   0 Here's the solution I thought of first:Assume that we start on the $z$-th data node. It is always optimal to first collect nodes in decreasing order, then if we reach node $0$ and still have time, to backtrack and collect from node $z+1$ onward, because it can be proven that $2 \cdot dist(node_z, node_0) \leq dist(node_z, node_{z+1})$.For the case where we don't start at a data node, we can brute force all reachable data nodes as the first node to collect, then proceed as above with $t$ reduced accordingly. Total complexity $O((\log t)^2)$, with the possibility of further reduction to $O(\log t \log \log t)$ via binary search, but that's overkill.
•  » » » 4 weeks ago, # ^ |   0 thank you but I understood a solution at last
•  » » » 4 weeks ago, # ^ |   0 I also thought the same way as you did at first, but I am getting wrong answer on test 44 from that approach. Can you tell me why?69440793
•  » » » » 4 weeks ago, # ^ |   0 Your linked submission says accepted, not wrong answer
•  » » » » » 4 weeks ago, # ^ |   0 I am really very sorry mate. I meant this submission: 69438965
•  » » » » » » 4 weeks ago, # ^ |   0 Two potential issues:  while(x0
 » 4 weeks ago, # |   0 Who's Joe?
 » 4 weeks ago, # | ← Rev. 3 →   0 Will somebody help me understand why my code is incorrect? (https://ide.codingblocks.com/s/170178)
 » 4 weeks ago, # |   +17 https://youtu.be/mhrvlor1qH0 — video editorial for 1292A - NEKO's Maze Game, including some incorrect solutions and mistakes.
 » 4 weeks ago, # |   0 Can anyone explain to me AROMA'S SEARCH problem I'm not getting the solution?
 » 4 weeks ago, # |   0 I did nekos maze game in O(q) check out my solution
 » 4 weeks ago, # |   0 Sorry If it Sounds silly. How the first observation is made out in Div2E(Div1C)? xuanquang1999
 » 4 weeks ago, # |   0 In the A problem, the office is in floor s-th. The number of closed floors is k, k limit is 1000, so if we search from s-1000 to s+1000 the maximum complexity would be 2000000. Here is the for-function recipe: for(int i = max(1, s-1000); i <= min(lim, s + min(n-s, 1000)); ++i) { if(restaurant_at_floor[i] == 1) continue; // map it first else minfloor = min(abs(s-i), minfloor); // set minfloor = 1e9 } cout << minfloor << endl;^^ hopefully oc idea
•  » » 4 weeks ago, # ^ |   0 Isn't it completely identical to the tutorial shown above?
•  » » » 3 weeks ago, # ^ |   0 oh i dont read the tuto clear. But i think this explaination would be a bit easier to understand cuz that number 1000
 » 4 weeks ago, # | ← Rev. 2 →   0 Can someone please tell how I can solve 1292A - Игровой лабиринт Неко by DSU?
 » 3 weeks ago, # |   0 lol, am I only one who solved C Div 2 using map,set>>?)) https://codeforces.com/contest/1293/submission/69836530
•  » » 3 weeks ago, # ^ |   0 Errichto himself used set in his tutorial video too.People are more used to arrays tbh, and also they're usually quite keen on execution time (sometimes even a log).
 » 3 weeks ago, # |   0 I have an O(n) solution for 1293A. 69928477
•  » » 2 weeks ago, # ^ |   0 Your sorting made it $\mathcal{O}(k \log k )$ unfortunately.
•  » » » 2 weeks ago, # ^ |   0 Oh. Sorry