We will hold AtCoder Beginner Contest 175.
- Contest URL: https://atcoder.jp/contests/abc175
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200815T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: satashun
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
chokudai Please upload the English editorials so that we noobs can learn from them. Still waiting for this one's.
Yeah! This is much needed. I saw Second Thread's Videos to cover last two Atcoder Beginner Contests.
I am writing an unofficial editorial. You can have a look at it for problem C on this page
Unofficial Editorial for B & C. Here
The contest starts in ~40 mins, see you on the leaderboard :)
How to solve F?
We 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| \gt |b|$$$ or $$$|a| \lt |b|$$$
Actually only prefix or suffix of given strings can be the "remaining part", so the number of nodes is just O($$$N * \max|S|$$$)
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!
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!
...
The constraints on k are too big here for the time complexity to be O(k). Think O(N^2)
can you explain the O(n^2) approach? Thanks.
It is by finding cycle in permutation. Although I could not debug my code. It was showing WA on 4 cases
Here's a clue by if it can help. Hint
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.
Hey tribute_to_Ukraine_2022, can you explain how D can be done $$$O \left( n \log\left( n \right) \right)$$$ ?
How to solve it in O(n logn)
First 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 \lt 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 \lt 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.
Code: https://atcoder.jp/contests/abc175/submissions/15929590
Thanks tribute_to_Ukraine_2022.
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.
cis_pie
I 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?
Here is a tutorial for the subarray sum part. https://www.geeksforgeeks.org/maximum-sum-subarray-of-size-range-l-r/
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
Same happened with me
Should have rushed for E before D.
i agree
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.
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?
Ohh, I forgot it.
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
submission i am also getting WA on same test cases .
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?
no
Do 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.
Thanks bro, I completely missed that case.
Getting 4 cases wrong on D. Can anyone suggest any corner case I am failing to include? Thank you :)
Submission
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
Damnn, silly of me.
Thanks, man :)
This silly thing made a penalty of 20 minutes for me.
Completely missed this :-(
Thank you. Was losing my mind over here with those damn 4 tests. sigh
Got really frustrated because of this!! Thanks.
You have done exactly my mistake. WA
AC
let'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.
I am getting WA on 2 test cases in problem D.
My solution
It'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 :'-(
Crap
Same 4/44 WA in D as people above
And failed to fit E into timelimits with python
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.
nope It is bottom-up. It's just a matter of small optimizations inside the loops
In E, we cant greedily chose the value to be taken. How to go ahead with the DP approach ?
dp[k][i][j] get k items on i-th row and j-th column
for evert kk, i, j
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?
In most time
dp[10][100000]is faster thandp[100000][10], because of Spatial Locality。It may be cache friendly.Oh, didn't know that.
Ah, I see. I thought your for loops were
i, j, kbut if you hadk, i, j, then you would indeed have spatial locality.Since I had
dp[r][c][4]and iterated overi, j, kit amounts to the same thing. (I think? If wrong, please point it out.)Right.
But In this problem we have 3 dimensions, so it may not have too much difference...
$$$dp[i][j][k]$$$ be the answer till cell $$$(i, j)$$$ using $$$k$$$ items in row $$$i$$$, transitions are pretty straightforward.
So straightforwared that you can tell with understandable words?
The state is CurRow, curCol, CurNoOfItems
The 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:
Hope that will help. You can look at my code here: My Submission
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.
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?
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.
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.
Getting WA on D in 4 Test Cases...Can anyone help me out here? Link: https://atcoder.jp/contests/abc175/submissions/15955049
Missing AnandOza and Geothermal's editorial.
https://youtu.be/HmbZiI0rAk4-- This might be helpful, it certainly helped me :)
In problem C-
using
gives WA on 10 tcs but using
gives AC.
Can someone plz help, by giving an example where the 1st one fails.
k*d can be $$$10^{30}$$$ : overflow.
Thanks a lot. My bad, I did not notice the constraints of k and d. :(
how can i print any index value of a set???? it's possible in c++????
It's possible if you use Policy-Based Data Structure, though generally, some other alternative would work too.
So, How to solve F?
See this -> https://mirror.codeforces.com/blog/entry/81458?#comment-681148
I am getting WA on 2 test cases in problem D.
My solution
It'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 :'-(
For D :
Took me couple of "ifs" to code correct logic Submission.
Can someone explain better way to do this?
Getting WA on D in 3 Test Cases...Can anyone help me out here? Link: WA on TC 7,11,22
How to solve C?
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.
Thanks for the screencast. In problem D , what's the use of below code, why only the first f0r(i, n) doesn't work ?
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:
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).
Am I the only one who gets demotivated by questions like todays D?
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 :(
Getting runtime error for some big cases for problem E can anyone tell what's wrong with this
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
I have AC code for D https://atcoder.jp/contests/abc175/submissions/15996588
Store 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)
IF Anyone Need Detail explanation for D Here