### kostka's blog

By kostka, 17 months ago, Round E starts in less than 12 hours (on August 22nd at 03:30 UTC). Comments (64)
| Write comment?
 » Yes
 » Why am I getting TLE for problem A for an O(1) solution.
•  » » 17 months ago, # ^ | ← Rev. 2 →   Because time complexity != execution time
•  » » $O(10^{100})$
•  » » is while(true) considered O(1)?
•  » » » 17 months ago, # ^ | ← Rev. 2 →   It depends (but probably not)
 » Why is it so hard ?
 » Who else solved problem A (Shuffled Anagrams) using max flow?
•  » » What kinda overkill is this, I got ac with O(n^2) algo
•  » » » 17 months ago, # ^ | ← Rev. 2 →   Edit : It is same to the analysis solution.Ok I will share my nlogn solution to A as I can't see any better approach than O(n*n) in this blog. This solution can be made to work even in On with some optimisations which I won't discuss, but will give hints to :P SpoilerNotice that if any element has frequency > n/2 then it is impossible to make a required anagram.Now we construct two strings p and q and initialise them to given string s. Sort them both. Now rotate q by n/2 and match p and q character wise and store pair p[i] and q[i] in a multimap. As no character has frequency greater than n/2, we can say that no p[i] and q[i] are same. Now iterate over s and construct a required anagram by these pairs. It will be a great exercise to implement it on your own. Pls ask if you need the code, I am writing from my phone so can't give now. Optimisations to make an On solutionThere are two places where we can optimise this approach. 1. sorting the strings p and q. we can do it in On by using counting sort as we have only 26 letters. 2. Using a multimap. We can use a vector of vectors to store for each character the elements we can replace it with. Its space will be On onli.sorry if I made any mistakes, I will go celebrate rakshabandhan. Happy Rakshabandhan to you guys too :)
•  » » » » How to construct s using strings p,q
•  » » » » » now that you have pair from p and q in a multiset, you can traverse through s and check what character you should put in answer string for that character in s. here is my implementation.https://p.ip.fi/-w-i
•  » » How to solve with Flows?
•  » » » Let $c$ be the maximum of unique characters ($c = 26$ in our case). Create a graph with $n = c + c + 2$ vertices (assume $0$-indexed). Let $\text{source} = 0$ and $\text{sink} = c + c + 1$. For every character $\text{a, b,...,z}$ create two nodes $2 \cdot i + 1$ and $2 \cdot i + 2$ (nodes from $1$ to $2 \cdot c$). here $i =$ rank of character. i.e. $0$ for $\text{a}$, $1$ for $\text{b}$,..., $25$ for $\text{z}$.Add an edge of capacity equal to the frequency of that character from $\text{source}$ to particular character on the left side ($2 \cdot i + 1$). Add an edge of capacity equal to the frequency of that character from character to the right ($2 \cdot j + 2$) to $\text{sink}$. Add an edge between characters from left ($2 \cdot i + 1$) and right ($2 \cdot j + 2$) of capacity $\infty$ iff they are not equal ($i \neq j$). if the maximum flow is $< |S|$ then answer is $\text{IMPOSSIBLE}$.If maximum flow is $= |S|$ then you can easily construct any valid anagram using the flow passing through each edge. Link of the code for more details.
•  » » » » Wow, that's pretty cool. Thanks
•  » » » » Is there somewhere I can find this more detailed manner? I'm new to graphs and I definitely want to learn this FLOW method.
•  » » » » » CP Algorithms $\to$ Flows and related problems.
•  » » 17 months ago, # ^ | ← Rev. 2 →   Yes, me.I was unable to find a proper greedy. So, I had to use it. I had never implement flows correctly before in a contest (iirc) and using it in A made me more reluctant but still, it went smooth for two green ticks (tho I had 2 penalties trying to find a proper greedy :( ).BTW it would be good if you could explain the time complexity. I thought it was higher degree polynomial time.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   My greedy solution. Not sure how O(n^2) didnt get TLE tho. Solution#include using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; for (int i = 1; i <= t; ++i) { string s; int impossible = 0; cin >> s; string temp = s; int siz = s.size(); for (int j = 0; j < siz; ++j) { if (count(s.begin(),s.end(),s[j])>siz/2) { impossible = 1; break; } } if (impossible) cout << "Case #" << i << ": " << "IMPOSSIBLE" << "\n"; else { for (int k = 0; k < siz-1; ++k) { for (int m = 0; m < siz; ++m) { if (s[k]!=s[m] & temp[k]!=s[m] & s[k]!=temp[m] & temp[k]!=temp[m]) swap(s[k],s[m]); } } cout << "Case #" << i << ": " << s << "\n"; } } } 
•  » » » » Time limit was 40 seconds :)
 » Dude what the heck was that difficulty curve?? For me, B was the hardest problem.
 » Solution for the problem D "Increasing Sequence Card Game" test set 3 (N > 10^6): https://www.quora.com/What-is-the-sum-of-the-series-1+-1-2-+-1-3-+-1-4-+-1-5-up-to-infinity-How-can-it-be-calculatedIt was by far the easiest problem of them all. Which awarded the largest amount of points.
•  » » Can you explain how the answer is of that form?
•  » » » 17 months ago, # ^ | ← Rev. 2 →   Just implemented a simple straightforward bruteforce solution for N <= 10 and looked at the results: SpoilerCase #1: 1.0000000000 Case #2: 1.5000000000 Case #3: 1.8333333333 Case #4: 2.0833333333 Case #5: 2.2833333333 Case #6: 2.4500000000 Case #7: 2.5928571429 Case #8: 2.7178571429 Case #9: 2.8289682540 Case #10: 2.9289682540 Based on these results, it's obvious that the answer is 1 + 1/2 + 1/3 + ... + 1/N. And this makes it a pure math problem, which is generic enough to be searchable on the Internet.
•  » » » » Wow, really need this kind of observation skills by looking at result. :))
•  » » » » » It's not just looking at the result alone. For N=1, the answer is 1. Then if we add one more card, it can go either to one side of the deck or to the other side and thus adds 1/2 to the expected score, making the formula 1 + 1/2. Next looking at N=3, we can see that ~0.3333333333 gets added to the answer and makes it 1 + 1/2 + 1/3. Further checking cases N=4,5,6,... confirms that this pattern continues. The top rated answer from quora provided the $H_n=ln(n)+0.5772156649$ approximation for large $n$ and it does the job. Here's a link to my submissions for this contest.Looking at the editorial, appears that the expected solution was supposed to be a bit more complicated.
•  » » » » How to solve problem A ?
•  » » » » » Just open one of the solution. You’ll learn more than from pure answer. If you’ve got WA its probably because for string like ‘abc’ you are doing ‘ba’ and can’t put ‘c’.
•  » » » » It's always dangerous to say that something is obvious. You should try to prove if you think you found a pattern. For this problem I think there may be a simple proof by induction. I demonstrated in other way by first solving test set2 with dp and then replacing the dp definition of the previous states. As an example of how this kind of thinking may mislead you, I give you the following classical problem find the Maximal number of regions obtained by joining n points around a circle by straight lines. The sequence starts with 1, 2, 4, 8, 16, ... So it's obvious that the next number is 32? But it's actually 31 A000127.Many times the attempt to prove that your assumption is true may lead you discover that you were wrong and save you time implementing the wrong solution.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   Using Errichto "contribution Technique" — The $i^{th}$ card from the top will have contribution in the final answer $<=>$ all previous card appeared are smaller than it. and probability of this is $1/(n-i+1)$. So you just need to do $\sum_{I=1}^{i=n}1/i$ SpoilerI tagged him because he is responsible for me able to observe such "Find Expected value" related problems
•  » » » » TIME LIMIT EXCEDED
•  » » » » » That's why for bigger N, you do as explained in this comment.
•  » » » » Is there a blog or video for that of errichto, if yes please share link.
•  » » » » » https://codeforces.com/blog/entry/62690 I wish I had seen the complete video when I first saw the post :(
•  » » Easy for those who could find the appropriate link by googling...nightmare for others !!
•  » » » Not really. You could code O(n^2) solution for test n = 10. And observe that dp[i] depends on sum of dp[1:n-1] and you could precalculate with accumulator. This would make your solution linear and n = 1e6 would pass.
•  » » » » ik...I was talking about Test set 3
 » I tried doing problem C(Palindromic Crossword) using some dfs kind algorithm(I stored nearest blockages for each row and column) and kept getting runtime error, can someone point out the mistake in my logic? Thanks link: https://pastebin.com/Xx3KHbGU
•  » » Try to run it for a 1000x1000 grid filled with '.'
•  » » » Thanks man, turns out I was not setting the columns in result grid and was trying to access columns without setting them, it was a stupid mistake :(
•  » » I did that too. I calculated horizontal and vertical palindrome equivalent positions of each non blocked cell. Spoiler#include #define int int64_t using namespace std; const int N = 1e3+7; int H[N][N], V[N][N]; bool vis[N][N]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for(int _ = 1; _ <= t; _ ++) { cout << "Case #" << _ << ": "; int n, m; cin >> n >> m; string s[n + 1]; for(int i = 0; i < n; i++) cin >> s[i]; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) { H[i][j] = V[i][j] = -1; vis[i][j] = false; } s[n] = string(m + 1, '#'); for(int i = 0; i < n; i++) { s[i] += '#'; int prev = 0; for(int j = 0; j <= m; j++) if(s[i][j] == '#') { for(int k = prev; k < j; k++) H[i][k] = j - k + prev - 1; prev = j + 1; } } for(int j = 0; j < m; j++) { int prev = 0; for(int i = 0; i <= n; i++) if(s[i][j] == '#') { for(int k = prev; k < i; k++) V[k][j] = i - k + prev - 1; prev = i + 1; } } int ans = 0; function dfs = [&](int i, int j) { vis[i][j] = true; if(H[i][j] != -1 and !vis[i][H[i][j]]) { if(s[i][H[i][j]] == '.') { ans++; s[i][H[i][j]] = s[i][j]; } dfs(i, H[i][j]); } if(V[i][j] != -1 and !vis[V[i][j]][j]) { if(s[V[i][j]][j] == '.') { ans++; s[V[i][j]][j] = s[i][j]; } dfs(V[i][j], j); } }; for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) if(isalpha(s[i][j]) and !vis[i][j]) { dfs(i, j); } cout << ans << '\n'; for(int i = 0; i < n; i++) { s[i].pop_back(); cout << s[i] << '\n'; } } } 
 » I have a much different solution to $D$ that allows for a more general statement that makes the problem slightly more interesting (and definitely harder).Using one-indexing, if we try to find the number of times card $i$ is at position $j$ and ends up in the final hand, we find that this number is ${i-1 \choose j-1}(j-1)! (N-j)!$. In short, this is choosing $j$ cards lower than $i$ and placing them in front of position $j$, then permuting everything but card $i$ and position $j$. To find the total number of times a single card $i$ is in the final hand, sum over all positions $j$ and expand. This nets you $\sum_{j \le i} \frac{(i-1)!}{(i-j)!(j-1)!} (j-1)! (N-j)!$. Simplify to get $(i-1)!\sum_{j \le i} \frac{(N-j)!}{(i-j)!}$. Notice that the subtraction of numerator and denominator removes $j$ from the summation, so we can try turning the fraction into a binomial coefficient. $(i-1)! (N-i)! \sum_{j \le i} \frac{(N-j)!}{(i-j)! (N-i)!} \rightarrow (i-1)! (N-i)! \sum_{j \le i} {N-j \choose i-j} \rightarrow (i-1)! (N-i)! {N \choose i-1}$ where the last transformation is by a binomial identity. Simplifying this expression trivially we, we find that the contribution is exactly $\frac{N!}{N-i+1}$, but the entire expression will be divided by $N!$ so the contribution to the expected value of card $i$ is exactly $\frac{1}{N-i+1}$The problem could have given a set $S$ and asked to find the expected value of the intersection between the final hand and $S$ or, if you want to keep the $H_n$ approximation, you can ask for the intersection between the final hand and all cards not in $S$. Even so, it's easily bruteforceable if one knows about the linearity of expectation, but the statement no longer screams to be brute forced.
 » for last problem Why I was getting WA for 3rd test case when I was trying to solve this recurrence $f(n)=f(n-1)+1/n$ by matrix exponentiation.
•  » » Matrix expo allows for adding $constant \cdot n$, not $constant / n$. Either you made a breakthrough or your matrix doesn't make sense :D
•  » » » 17 months ago, # ^ | ← Rev. 2 →   Thanks! I was not aware of it and wasted hours. Can you please provide any reference or some reason for "why it doesn't work with double?"
•  » » » » It works with doubles. You can add 0.3*n. It doesn't support division. Because how you would do that? You choose matrix coefficients and they get multiplied by something, not divided.
 » for me A was harder than D.
 » 17 months ago, # | ← Rev. 2 →   For D problem, I found a solution easier than analysis solution. Suppose that we found answer for n-1 (base case is n=1 which is 1). Think all of the permutations from n-1, increase every number with 1. Now, we should just insert 1 into somewhere into them, there are two cases: 1. Insert 1 at the beginning, it gives us (n-1)!, because there are (n-1)! permutations. 2. Insert 1 at anywhere expect the beginning, it won't be included in any increasing subsequence. So it gives us for every answer from n-1, (n-1) times of it + from the first case there is 1 more f(n-1) too. So f(n)/n! = (f(n-1) / (n-1)!) * n + (n-1)! / n! = f(n-1) + 1/n. Then for n <= 1e6, brute force, otherwise use formula for harmonic sums, which is f(n) = ln(n + 1) + (Euler–Mascheroni constant =~ 0.5772). (edit: fixed plagiarism)
•  » » This is genius. Thanks :)
 » It was a nice round! I secured rank 1085 in it
 » Is C some form of a well-known problem ? I noticed a lot of people do C but fail at D.
•  » » C was just some recursion .
•  » » » 17 months ago, # ^ | ← Rev. 2 →   your rank is just +3 of mine :)
•  » » » » Any tips for a beginner, it was my first time..
•  » » » » » Try CSES problemset and Atcoder Beginner Contest , your skills will improve exponentially with time.
•  » » » » » » What level of maths is needed to aid a solution?
•  » » » » » » » Upto my level , Not much
•  » » » » Yeah , It wasn't a good Kickstart for me , :( , but still it's fine .
•  » » Just as the editorial explains in the "Test Set 2" part, it's a graph problem. I solved it by constructing an adjacency list and then doing DFS. Relatively few participants submitted a partial solution only for Test Set 1 and this makes sense, because it's actually easier to treat it as a graph rather than doing something ad-hoc.I think that Codeforces offers awfully few graph problems among Div2A-Div2D, so I recommend participating in AtCoder beginner/regular contests to improve your skills at solving this stuff.
•  » » » Why ad-hoc? I don't think a lot of people solved it as a graph problem. It's a usual board/matrix problem which is more common/simple. You can save all # indexes in a row/column and traverse them with your board and get next jump in constant time or make [up/down/left/right]-matrices, or [horizontal/vertical]-matrices and do the same. Bfs — or — dfs, doesn't really matter. This approaches seem more common and widely used to me then graphes, not something special or ad-hoc.
•  » » » » I checked your solution and it looks like you essentially used a fancy problem-specific data structure for storing and retrieving information about graph edges instead of something more conventional. I used a plain and boring adjacency list in my solution. The other differences are pretty much cosmetic/insignificant. As for which approach is more simple, I would say that mine probably better followed the teakettle principle and it was a more reliable way to get a guaranteed result (even at the cost of more lines of code).In my opinion, we both solved it as a graph problem. You may disagree, but that's similar to saying "it's not a graph, it's Takahashi's kingdom with towns and roads". Graph is a useful abstraction with useful properties and useful algorithms. Sometimes graph edges are given to us directly as a part of input data. But in this particular problem C, it was a graph with a little bit of disguise.
•  » » » » » 17 months ago, # ^ | ← Rev. 3 →   IDK, maybe. We really can find a lot of graph abstractions around. Maybe it's just hard for me to call anything a graph problem if it doesn't involve working with path's, cycles, flows and dijkstra-bellman-ford-floyd-warshall things.PS. Oh, now I've got it, your adjacency list is not cells with common edge — it is cells which must have same letter in it. Yep, got it.
 » 17 months ago, # | ← Rev. 3 →   For me is a wonderful contest experience, although terrible at first. At first I failed both problem A and B from time to time, and cannot pass a single test set in the first 1 hour 10 minutes. You can imagine how desperate I was when contest pass almost half and my score was zero!Then I pass the small test set for problem B, and then problem C (A typical DFS problem), my ranking rise from 2000+ to 600+, then I pass problem D due to my clever observation, and my current ranking rise to 250+.Finally I look back on problem A, first I use brute force to pass small test set to guarantee 4 points, then I pass large test set 8 minutes till the end of the contest. My final score is 87/100, with the ranking 205, which is the highest ranking of all times. So guys, never give up until last minute in competitive programming.
 » For anyone interested, here's a link to my screencast. I've also recorded solution explanations at this link.