### chokudai's blog

By chokudai, history, 5 weeks ago,

We will hold AtCoder Beginner Contest 175.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +72

 » 5 weeks ago, # | ← Rev. 3 →   +5 chokudai Please upload the English editorials so that we noobs can learn from them. Still waiting for this one's.
•  » » 5 weeks ago, # ^ |   +13 Yeah! This is much needed. I saw Second Thread's Videos to cover last two Atcoder Beginner Contests.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I am writing an unofficial editorial. You can have a look at it for problem C on this page
•  » » 5 weeks ago, # ^ |   +3 Unofficial Editorial for B & C. Here
 » 5 weeks ago, # |   +2 The contest starts in ~40 mins, see you on the leaderboard :)
 » 5 weeks ago, # |   +10 How to solve F?
•  » » 5 weeks ago, # ^ |   +13 Solution for FWe will be constructing left and right half of our palindrome in parallel.We can store current state as two strings $a = S_{i_1}S_{i_2}\ldots S{i_k}$ and $b = S_{j_l}S_{j_{l - 1}}\ldots S_{j_1}$ for some indices $i_1, i_2, \ldots, i_k$ and $j_1, j_2, \ldots j_l$. To have any chances of constructing a palindrome we need to have strings $a$ $b$ such that $\min(|a|, |b|)$ first characters of $a$ exactly match last characters of $b$. Moreover if they do we only care about characters left after we remove matching prefix of $a$ and suffix of $b$.Now we can just run Dijkstra algorithm, where state is pair of strings left from prefix and suffix. So far the number of states can grow exponentially, but if we only append $S_i$ to shorter of $a$ and $b$ (i.e. empty string from pair representing state) we're guaranteed that one of strings in pair is empty and the other is substring of one of $S_i$. There are at most $50$ input strings, each of them has length at most $20$, so at most ${21 \choose 2} = 210$ substrings, which gives us at most $2 \cdot 210 \cdot 50 = 21000$ different states. Now any time Dijkstra enters a state with known distance from start we can just check if it's a palindrome by checking if string cut from prefix/suffix is, and if so update answer.The only thing left is to get through all the cases on how the state changes as we append a string shorter/longer then current string stored in state and is $|a| > |b|$ or $|a| < |b|$
•  » » » 5 weeks ago, # ^ |   +14 Actually only prefix or suffix of given strings can be the "remaining part", so the number of nodes is just O($N * \max|S|$)
•  » » » 5 weeks ago, # ^ |   0 Hi,How can you tell when it's impossible to form a palindrome string from Dijkstra? From your demonstration, you have a finite amount of states to explore, so after running them out you would print -1.I get that you have to choose a string at most once for a certain half. (from 21 choose 2, either is a palindrome or not, so it's not worth putting it in both halves), but still, you would have to reuse them in a way that is hard to implement.Thank you!
 » 5 weeks ago, # |   0 How to remove TLE in D? My code gives TLE due to large K but how can i make my solution batter? any hints will help alot.thanks in advance! My Codeconst int MX = 5011; vector> adj(MX+1); vector vis(MX+1); std::vector aa(5011), bb(5011), vv(5011); ll n, k; ll ans = INT_MIN, cnt = 0, mov = 0; void bfs(int p, int src) { queue q; q.push(p); while(mov> n >> k; for(int i = 0; i < n; i++) { cin >> bb[i]; bb[i]--; // add_edge(adj,i,bb[i],1); adj[i].push_back(bb[i]); } for(int i = 0; i < n; i++) { cin >> aa[i]; } for(int i = 0; i < n; i++) { cnt = 0; mov = 0; bfs(i,i); } cout << ans << '\n'; } ...
•  » » 5 weeks ago, # ^ |   0 The constraints on k are too big here for the time complexity to be O(k). Think O(N^2)
•  » » » 5 weeks ago, # ^ |   0 can you explain the O(n^2) approach? Thanks.
•  » » » » 5 weeks ago, # ^ |   +9 It is by finding cycle in permutation. Although I could not debug my code. It was showing WA on 4 cases
•  » » » » » 5 weeks ago, # ^ |   0 Here's a clue by if it can help. Hint
•  » » » » » » 5 weeks ago, # ^ |   +1 Lol. Only after reading your comment I realised this problem has $N \leq 5000$ not something closer to $N \leq 10^5$. Nevertheless it can be solved in $O(n log n)$ and it's not that much harder.
•  » » » » » » » 5 weeks ago, # ^ |   0 Hey I_love_chickpea, can you explain how D can be done $O \left( n \log\left( n \right) \right)$ ?
•  » » » » » » » 5 weeks ago, # ^ |   0 How to solve it in O(n logn)
•  » » » » » » » » 5 weeks ago, # ^ |   +16 O(n log n) solution for DFirst we of course split the permutation into cycles and solve each of them separately.We will first solve a simplified version: given a cycle of length $l$ find a cyclic subsegment with length in range $[a, b]$ where $0 \leq a \leq b \leq l$ and maximum possible sum. To solve it we can expand the cycle to an array running through the cycle twice calculate prefix sums, iterate through them left to right and store in some structure (e.g. multiset) those prefix sums that form with the current one segment of length $[a, b]$. Any time we go to next prefix sum we only need to update our data structure by erasing/inserting constant number of elements and to query and extract minimum to get best possible with current position as the last one.Using this we can get through some cases. Let $x$ denote the length of optimal sequence, $s$ sum of all elements on the cycle, and $l$ length of the cycle.Now if $s \geq 0$, then any cycle with length $x + l$ has sum greater or equal to cycle with length $x$, and if $s \leq 0$ it has sum less or equal, so we need to consider only $x\in [0, l)$ and $x \in (k - l, k]$First let $x < l$ we just use our subproblem solver with $a = 1, b = \min(l, k)$.Let $k = la + b$ with $a, b \in \mathbb{Z}$, $0 \leq b < l$. We can split $(k - l, k]$ to $(k - l, la)$ and $[la, la + b)$ and for each of those we know we will run through whole cycle a fixed number of times and then take some leftover with length from some range, that is less than $l$ and this can be also solved using our subproblem solver.
•  » » » » » » » » » 5 weeks ago, # ^ |   0 Thanks I_love_chickpea.For those who are facing difficulty in understanding relationship between max-subarray sum and this problem.Here is explanation :In $O \left( { n }^{ 2 } \right)$ approach we are trying to start our cycle from each element of array which means we are traversing same permutation cycle from different starting points which is not at all required but optimal starting point can be found by solving max-subarray problem on that cycle.
•  » » » » » » » » » 5 weeks ago, # ^ |   0 cis_pieI understand your point that for same cycle we are doing lot of recalculation. But what is not clear is how to actually avoid that using subarray sums, can you please elaborate the solution a bit more if you have understood?
•  » » » » » » » » 5 weeks ago, # ^ |   0 Here is a tutorial for the subarray sum part. https://www.geeksforgeeks.org/maximum-sum-subarray-of-size-range-l-r/
•  » » » » » » » » 5 weeks ago, # ^ |   +3 In short, store for each k=0,1,,log n, precalculate some information from a node v for every path of length $2^k$ - $sum_{k,v}$ for sum of the path - $maxi_{k, v}$ for maximum prefix sum of the path and use them like Digit DP
•  » » » » » 5 weeks ago, # ^ |   +10 Same happened with me
 » 5 weeks ago, # |   +20 Should have rushed for E before D.
•  » » 5 weeks ago, # ^ |   0 i agree
•  » » » 5 weeks ago, # ^ |   -13 I took 25 minutes to do E and 65 minutes to do D. If I rushed for E earlier, my position would have been a lot better.
•  » » » » 5 weeks ago, # ^ | ← Rev. 2 →   +8 Your score would be same and the penalty is the time of your last submission. So you solve E first or D first, how will it affect your position?
•  » » » » » 5 weeks ago, # ^ |   0 Ohh, I forgot it.
 » 5 weeks ago, # |   +5 please, anyone, find what's bug in my solution in D (it's giving WA on 4/42 test cases)https://atcoder.jp/contests/abc175/submissions/15952579
•  » » 5 weeks ago, # ^ |   0 submission i am also getting WA on same test cases .
•  » » 5 weeks ago, # ^ |   +8 I had the same problem, but figure this out:You do the first cycle of length A, and then you find out you can do B more of those cycles.Do all of them: B, and then brute force the rest of the steps?noDo B-1 of them, and brute-force the rest. The B-th cycle might be the last complete cycle, and so you are missing out on some update_max calls on those 4 WA.
•  » » » 5 weeks ago, # ^ |   +4 Thanks bro, I completely missed that case.
 » 5 weeks ago, # | ← Rev. 2 →   0 Getting 4 cases wrong on D. Can anyone suggest any corner case I am failing to include? Thank you :)Submission
•  » » 5 weeks ago, # ^ |   +45 If k % cycle_length == 0 then reduce number_of_cycles by one and for last cycle see if adding some nodes only makes answer better or not
•  » » » 5 weeks ago, # ^ |   +12 Damnn, silly of me.Thanks, man :)
•  » » » » 5 weeks ago, # ^ |   0 This silly thing made a penalty of 20 minutes for me.
•  » » » 5 weeks ago, # ^ |   +13 Completely missed this :-(
•  » » » 5 weeks ago, # ^ |   +5 Thank you. Was losing my mind over here with those damn 4 tests. sigh
•  » » » 5 weeks ago, # ^ |   0 Got really frustrated because of this!! Thanks.
•  » » 5 weeks ago, # ^ |   0 You have done exactly my mistake. WAAClet's say, cycle length is 5 and k is 17. Then, you need to check two things, max val till 5 operation, total cycle sum * 3 + maxval till 2 operation. Hope you get the mistake.
•  » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 I am getting WA on 2 test cases in problem D.My solutionIt's on test case 2 and 22.Anyone else got the same error ?UPD: I was taking the maximum answer in the prefix of the cycle before even considering what the value of k is.How silly of me :'-(
•  » » » 5 weeks ago, # ^ |   0 could u plz explain why u did k-- in the beginning??
 » 5 weeks ago, # |   +1 CrapSame 4/44 WA in D as people aboveAnd failed to fit E into timelimits with python
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 For E, You must be writing recursive dp. I also got TLE at first but then got an AC in java with same logic. I saw many people get AC with python but using iterative bottom up dp.
•  » » » 5 weeks ago, # ^ |   0 nope It is bottom-up. It's just a matter of small optimizations inside the loops
 » 5 weeks ago, # |   0 In E, we cant greedily chose the value to be taken. How to go ahead with the DP approach ?
•  » » 5 weeks ago, # ^ | ← Rev. 4 →   0 dp[k][i][j] get k items on i-th row and j-th columnfor evert kk, i, j ckmax(dp[0][i + 1][j], dp[kk][i][j]); ckmax(dp[kk][i][j + 1], dp[kk][i][j]); if (val[i + 1][j] != 0) ckmax(dp[1][i + 1][j], dp[kk][i][j] + val[i + 1][j]); if (val[i][j + 1] != 0 && kk < 3) ckmax(dp[kk + 1][i][j + 1], dp[kk][i][j] + val[i][j + 1]);
•  » » » 5 weeks ago, # ^ |   0 Isn't that too cache-inefficient? It doesn't really matter in this problem I guess, but I can't see why you have used k,i,j instead of i,j,k. Is there any particular reason or just the dp that came into mind?
•  » » » » 5 weeks ago, # ^ |   0 In most time dp[10][100000] is faster than dp[100000][10], because of Spatial Locality。It may be cache friendly.
•  » » » » » 5 weeks ago, # ^ |   0 Oh, didn't know that.
•  » » » » » 5 weeks ago, # ^ |   0 Ah, I see. I thought your for loops were i, j, k but if you had k, i, j, then you would indeed have spatial locality.Since I had dp[r][c][4] and iterated over i, j, k it amounts to the same thing. (I think? If wrong, please point it out.)
•  » » » » » » 5 weeks ago, # ^ |   0 Right.But In this problem we have 3 dimensions, so it may not have too much difference...
•  » » 5 weeks ago, # ^ |   0 $dp[i][j][k]$ be the answer till cell $(i, j)$ using $k$ items in row $i$, transitions are pretty straightforward.
•  » » » 5 weeks ago, # ^ |   +1 So straightforwared that you can tell with understandable words?
•  » » » » 5 weeks ago, # ^ |   +7 The state is CurRow, curCol, CurNoOfItemsThe transitions are: if curNoOfItems is 3, then we only can go to the next row, and reset number of items to zero. if curNoOfItems less than 3: we have four options: Either we do not take it and move to the next item in the same row. Either we do not take it and move to the next row and resetting number of items to zero. Either we do take it and move to the next item in the same row (increasing no of items by 1) Either we do take it and move to the next row and resetting number of items to zero. Hope that will help. You can look at my code here: My Submission
•  » » » » » 5 weeks ago, # ^ |   0 Thanks, now I understood.My basic error was in "but at most three for each row". I tried to solve for at most three at all.
 » 5 weeks ago, # | ← Rev. 2 →   0 please can anyone try to explain E? I tried using dp and got 10 WA. made dp[r][c][4]. dp[i][j][0], dp[i][j][1], dp[i][j][2] for storing 3 greatest value in row and dp[i][j][3] for storing max sum obatined till r-1 rows. Here is my submission.Can anyone tell what's wrong in my solution?
•  » » 5 weeks ago, # ^ |   0 I tried this, too. But it is wrong idea. If you get on two paths say { 100, 50, 50 } and { 100, 70, 0 } you cannot say what is "better" because it depends on whhich numbers will follow later.
•  » » 5 weeks ago, # ^ |   0 I also did something similar. dp[i][j][k] denotes the maximum amount if I choose k items in i'th row after the index j. Here k can have only 3 values,.... 1,2,3. Here is my submission :https://atcoder.jp/contests/abc175/submissions/15941327. As we want to maximise our answer, k=0 state is unnecessary. Finally our answer should be max({dp[1][1][1],dp[1][1][2],dp[1][1][3]}). Note: we start calculating dp values from bottom.
 » 5 weeks ago, # |   0 Getting WA on D in 4 Test Cases...Can anyone help me out here? Link: https://atcoder.jp/contests/abc175/submissions/15955049
 » 5 weeks ago, # |   +12 Missing AnandOza and Geothermal's editorial.
•  » » 4 weeks ago, # ^ |   0 https://youtu.be/HmbZiI0rAk4-- This might be helpful, it certainly helped me :)
 » 5 weeks ago, # |   +3 In problem C-using if((x-k*d)>=0) cout<<(x-k*d)<=k) cout<<(x-k*d)<
•  » » 5 weeks ago, # ^ |   0 k*d can be $10^{30}$ : overflow.
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 Thanks a lot. My bad, I did not notice the constraints of k and d. :(
•  » » 5 weeks ago, # ^ |   0 Explaination hope this helps.
 » 5 weeks ago, # |   0 how can i print any index value of a set???? it's possible in c++????
•  » » 5 weeks ago, # ^ |   0 It's possible if you use Policy-Based Data Structure, though generally, some other alternative would work too.
 » 5 weeks ago, # |   0 So, How to solve F?
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # | ← Rev. 2 →   0 I am getting WA on 2 test cases in problem D.My solutionIt's on test case 2 and 22.Anyone else got the same error ? Someone please tell me where have done the error.UPD: I was taking the maximum answer in the prefix of the cycle before even considering what the value of k is.How silly of me :'-(
 » 5 weeks ago, # |   0 For D : Took me couple of "ifs" to code correct logic Submission.Can someone explain better way to do this?
 » 5 weeks ago, # | ← Rev. 2 →   0 Getting WA on D in 3 Test Cases...Can anyone help me out here? Link: WA on TC 7,11,22
 » 5 weeks ago, # |   0 How to solve C?
•  » » 5 weeks ago, # ^ |   +10 Fully Commented Codevoid solve() { int x, k, d; cin>>x>>k>>d; // k is the total no. of moves x = abs(x); //considering that we are on +ve x-axis int steps = x/d; // no. of steps we are away from origin if(k <= steps) x -= k*d; //if k<=steps, we will try to move as close to origin as //possible else { //if we are forced to move more steps than required k -= steps; //now k is the extra steps which we are condemned to move if(k%2==0) x -= d*steps; //if extra steps is even, we can simply waste them by //moving 1 step forward and 1 step backward again and again else { //if odd, we will cross origin (atleast) once as we have no other choice x -= d*(steps+1); } } x = abs(x); //finally getting the distance from origin cout<
•  » » 5 weeks ago, # ^ |   0
 » 5 weeks ago, # |   +32 My screencast of the round, where I clutch out F, draw an ugly chocolate bar for a grid, and explain solutions to all problems (A-F) in video format.
•  » » 5 weeks ago, # ^ |   +11 Thanks for the screencast. In problem D , what's the use of below code, why only the first f0r(i, n) doesn't work ? if (cval > 0) { cur += (k / csize - 1) * cval; rem %= csize; rem += k; } 
•  » » » 5 weeks ago, # ^ |   +4 The way of implementing I describe in the solutions is better than what my code represents, and that edge case doesn't arise. What I did in the code was, instead of counting the number of possible cycles after fixing the last few moves, I first made as many cycles as possible then found the best way to make the last few moves. This is wrong because it may make one too many cycles.The test case I find in the video which makes that part of code necessary is: 3 7 2 3 1 13 15 -27 where the optimal strategy is to start at position $3$, ride the cycle once, then end at position $2$ ($5$ moves). Without that section, the code won't even consider that as a possibility, and instead start at $1$, make two cycles, and end at $2$ ($7$ moves).
•  » » » » 5 weeks ago, # ^ |   0 Gotcha! I missed this case.
•  » » » » 3 weeks ago, # ^ |   0 Can you please help me in problem E. I did DP and quite of problems of it but couldn't do E because of that 3 moves constraint. Can you help in transitions and how that extra cell K in dp is working?
 » 5 weeks ago, # |   +2 Am I the only one who gets demotivated by questions like todays D?
 » 5 weeks ago, # |   0 Can anyone help me with this submission on problem D? It gave WA in only two cases. I have no idea what's wrong with this :(
 » 5 weeks ago, # | ← Rev. 2 →   0 Getting runtime error for some big cases for problem E can anyone tell what's wrong with this
 » 5 weeks ago, # |   0 any fault for problem E in my submission https://atcoder.jp/contests/abc175/submissions/me
 » 5 weeks ago, # |   +10 I wrote an unofficial editorial from problem A to E. If you have any question, please give me comments and let me know. I’m going to write unofficial editorials for ABC, so don’t forget to check them out. The link for this contest is https://wordpress.com/read/feeds/108186275/posts/2862983275
 » 5 weeks ago, # |   0 I have AC code for D https://atcoder.jp/contests/abc175/submissions/15996588Store values of up to 5000 moves in DP table.If K <= 5000, you can get the maximum value from the DP table.Otherwise, the maximum value can be found in several cases. (Checkable on link)
 » 4 weeks ago, # |   0 IF Anyone Need Detail explanation for D Here