### hmehta's blog

By hmehta, history, 4 months ago, , Hey All!

Topcoder SRM 762 is scheduled to start at 07:00 UTC -4, July 3, 2019. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.

Thanks to teja349 and Errichto for writing and Vasyl[alphacom] for testing the problem set.

This is the fifth SRM of Stage 4 of TCO19 Algorithm.

Good luck to everyone! srm, Comments (54)
•  » » Fixed thanks! :)
•  » » » Gentle Reminder! The match begins in around 2 hours and 30 mins from now!
 » There is a typo. Should be 762 and not 761.
 » how to solve Strawberry?
•  » » 4 months ago, # ^ | ← Rev. 2 →   I guess it can be solved by polynomials polynomial multiplication with $O(n \times k \sqrt{k}))$.(reference: link from GeeksforGeeks)But it definitely is not what the solution of writer...
•  » » I solved with time complexity $\text{O}(nk^2)$. I guess it is not intended. The practice room system test shows that it passed in 4.9s while the TL is 5s.
•  » » » 4 months ago, # ^ | ← Rev. 2 →   I tried to TLE you and got -25. :( Then my 250 failed from not seeing the length 200 constraint and now I am last place.
•  » » » » I also tried to TLE another solution with the same time complexity since I don't believe mine will pass. Then got -25 as well. :)
•  » » » I got 5.0s in practice room
•  » » » I tried hacking a couple of O(NK^2) solutions but they both failed :(You can replace the inner dp with fft to get a runtime of O(N*Klog(K)).
•  » » » » How can you do FFT? $10^9 + 6 = 2 \cdot 500000003$.
•  » » » » » Well... tourist can help herehttps://github.com/the-tourist/algo/blob/master/numeric/fft.cpp
•  » » » » » Just compute on doubles ;p
•  » » » » » It could be non-obvious, but: Calculate the convolution modulo $7 \cdot 2^{26} + 1, 5 \cdot 2^{25} + 1, 45 \cdot 2^{24} + 1$. Use Garner's Algorithm to retrieve the value modulo $10^9 + 7$. With my implementation with using Montgomery Reduction while multiplying in two modints, it passed in about 0.3 seconds in max testcase.
•  » » » » » » How were the three numbers in step 1 chosen?Is the idea that the three numbers P, Q, R in step 1 are pairwise coprime, and that PQR is so large that the answer modulo PQR is equal to the actual value of the answer?Or am I missing some relationship between P,Q,R and $10^9+7$?
•  » » » » » » » Yeah, the idea is the same as you mentioned. Here is the condition At least $PQR > (M-1)^2 \cdot N \simeq 1.4 \cdot 10^{22}$ should hold, because of the maximum possible value of after-convoluted value. So we need at least three integers if we use 32-bit. I used the algorithm called Number Theoretic Transform (NTT). This only works in mod $p$ when $p$ is the prime of form $c \cdot 2^d + 1$ where $d$ is the least integer that is $2^d \geq N$.
 » I'll have a rant this time, for a change.Div1 250 would have been a nicer problem with $n$ up to $200$. Test generators in the statement generally reduce problem interest, especially when the problem is not that hard.Unintuitive and inconsistent test generators (state taken modulo $2^{31}$ after use in Div1 250, but before use in Div1 500) don't add value to the problemset. Combined with weak samples, they just add frustration for the contestants.
•  » » Also in Div1 250: We have to choose the lexicographically smallest sequence $B$, and only then prepend the length and return. We have to reduce the length of $B$ to 200, but the returned length must be the original length. There are no examples to check we got the above points right. All in all, the problem is a minefield, and not in an interesting way.
•  » » But Div1 250 with $n \leq 200$ can be solved with a very easy $O(n^2)$ DP...
•  » » » Sure, but consider two scenarios: Give the problem as it is. Give it with $n \le 200$. Is then contest in scenario 1 really better than in scenario 2 overall?If the problem is that much more interesting when only the linear solution is allowed, the author may consider using it on a platform which fully supports it, without the generator in statement and without output truncation.
•  » » » » The linear solution is the reason to have this problem. I'm sorry its beauty got spoiled by the workarounds needed for the platform. Honestly, I dislike having to do them as much as you all do and I really hope we'll finally get to use a decent backend soon.
•  » » » » » If you are using test generators, why not to give a big example?
•  » » » » » » There should have been one, and it's a mistake that there wasn't one. Sorry.
•  » » » » » I see how the problem is better when it's $O(n)$. Just, if the author is not locked into writing for TopCoder exclusively, they could use it elsewhere, and come up with another problem which suits TopCoder format better. There are many problems which lose little, if anything, when they are constrained in "olde TopCoder style", with $n$ up to 50 or so. Would be a win-win.
•  » » » » » » I wholeheartedly agree. It's very important to think which platform is best for your problem. Big constraints aren't good for Topcoder. If some statement is very long or it describes an existing process/game/whatever that some people know and some don't, it might be a good idea to use it in a long contest like the 10-day contest in Codechef. In Codechef, I also used some problem with local python interactor that was given to contestants and they could use it without hurry. Subtasks are good for OI-style competitions etc.It's ofc. easier to distribute problems like that when having some experience but you should still try. In most platforms, it's ok if you just propose one problem btw.
•  » » » » » » I think 250 was ok if big example test was provided (but you may have made a mistake in your solution that made you dislike it compared to others), we have seen similar output format before even long time ago.500 was not ok though. I would buy this "educational" thing a bit if TopCoder was producing any education content (with FFT tutorial for example). But they haven't produced any new content in ages, so better stick with what is common knowledge in Algorithms.
 » The missing constraint that the resulting array should have positive integers is an important part of the Div 2 500 problem. It took me a while to figure out what to do with elements that were not included in the restriction and lost some points. Though I earned 250 points for challenging other solutions.
•  » » 4 months ago, # ^ | ← Rev. 2 →   Update: In div1 250 the validator allowed some invalid inputs. The validator is being fixed and the offending challenges will be nullified.Div I results and ratings will be updated later in the day.
 » Wow, return only first 201 elements. What a great technology!
•  » » TC has not change since 2005 LOL
•  » » Still a better system than Boeing MCAS.
 » After submitting the Div.1 250 pt, I recall that I forget the constraint that we need to just return the first 200 elements as what I do in TCO 18 round 4.And in the challenge phase, I get 200 points from others by bug about this constraint...I think the constraint is terrible and affect final rank too much.
•  » » Oh no
 » I was writer for the 5 problems (apart from Div1 Hard). I am sorry for many things. I think this is lowest I have ever felt with my mistakes in preparing tasks.Firstly Div1 Med,I should probably have stuck to NTT instead of Karatsuba, But we felt NTT might be harder for people so we went with Karatsuba. And I as a stupid compared times of both my Java n*k*k solution and n*k^1.6 and felt it was fine(instead of using an optimised C++ solution). Now, Div1 Easy, I missed the condition (Aprefix.length < = n)in checkData, which sadly no one noticed. (:Hope you liked the questions. Thanks for participating!
•  » » Why do you want to set such a straightforward Karatsuba/NTT problem?
•  » » » You are not the target group for the problem. People who are now learning the technique are. From time to time, straightforward $technique problems are needed for all techniques, so that other people can learn and practice the stuff you already know. If all the problems on$technique use it in complex ways, it makes learning harder.If you already know it well, the problem should have been straightforward for you to give you more time to try to solve the hard.
•  » » » » OK. So maybe I can send such problems to TC:given two polynomials, output their product.
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   That's unfair, and you know it.This is nowhere near the same situation. Here you still had to do the correct modeling of the process described in the statement, discard unneeded parts of the polynomials after each multiplication, and reverse directions appropriately. In order to do that, you need to understand what the algorithm actually does instead of just blindly using a black box.
•  » » » » » » bad problem for topcoder: multiply two polynomialsgood problem for topcoder: generate using given generators two polynomials and after that multiply them
•  » » » » » » » And then print the xor of the coefficients, I think u forgot this
•  » » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   probably some formula with long long overflow in it instead of xor will suit more.of course, without any examples on it.
•  » » » » » » » » » return the length then min(200, size) elements in it XD
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   discard unneeded parts of the polynomials after each multiplication, and reverse directions appropriately This sounds very silly, and I think one doesn't need to be red to think as such. I agree the modeling is nontrivial, but it's still straightforward.However, I liked the Hard. Thanks to Errichto for a nice problem.
•  » » » » I agree that this problem requires some observation. At least we first need to find $O(nk^2)$ solution (which is d2 hard), and also need to understand that the transition is of the same form as convolutions. Still, we need to compare the ratio between technical parts and observation parts. We can say that a problem with level 1 known technique and level 2 observation is good, but a problem with level 10 known technique and level 3 observation is completely straightforward. I believe 90% of the difficulty of this problem comes from FFT with arbitrary modulo (which is more advanced than a simple FFT) and thus I don't see much difference from sunset's exaggeration. I also agree that problems that (almost) directly ask the knowledge of advanced techniques are valuable for educational purpose. However, please don't put them in rated d1 contests. There are other places for them — online judges, CF edu rounds, ABCs, etc. (personally I try to make ARCs more idea-oriented.) Speeds on d1 meds have great impact for reds too. What's the main factor of the speed in this problem? Preparedness of your pre-written FFT. (Do you have NTT or just double FFT? or you have a code for arbitrary modulo? Do you have Karatuba instead?) It's not interesting if the ratings of reds are greatly affected that way.
•  » » » I do not know if I can say it was straightforward NTT (maybe for you it was very obivous). I felt it was a good problem for the Div1 Med level (only some 35 odd people did it (even in them I think there are few optimised bruteforces which passed.)). why do you think if someone found it to be straightforward, try to write optimised bruteforce?
•  » » » » Because 17 * 7k * 7k = 833m, and you gave us 5 seconds.Assuming the author is not that good at setting TLs (which turned out to be true), it seemed reasonable to consider this problem just an exercise on modular arithmetics and dp with probabilities, something like a 450-pointer to move on to the hard problem.If you wanted only a o(n*k*k) solution, you definitely needed larger limits.
•  » » » » » 4 months ago, # ^ | ← Rev. 2 →   Its not 7k, but 14k?Anyways, I surely agree it was my mistake as I said above.
•  » » » » » » Yep, my fault. And still we see both C++ and Java solutions with no smart optimizations passing in 5s.
•  » » Cheer up. Mistakes happen. We can use the experience, and ask ourselves how to improve the process so that they can't happen next time, or at least are less likely to happen.
•  » » I think a lot of issues would be easier to avoid with some changes made by Topcoder. Changes that we need to wait for. I would like to see better problem setting software where an author can and should have a lot of solutions, not just one in Java. Validator tests would be nice too. Or let's just use Polygon and export problems to TC from there :DAnd I'm a fan of platforms with different types of contests. CF can use less interesting (more standard and thus educational) problems in Edu rounds, Atcoder has ARC for that. I agree with misof that problems like this one should exist, but experienced competitors don't want to see them in main contests of any platform (SRM for Topcoder, div1+2 round for CF). It hurts much more in case of Topcoder because of a small number of problems in a round.
 » Code for div1hard with comments: Spoilerfinal int MOD = 1000 * 1000 * 1000 + 7; List[] w; int[] height, subtree; int[][] cntDistance; // cntDistance[A][d] - in subtree of A, how many vertices are at distance d from A void dfs(int a, int parent) { cntDistance[a] = 1; height[a] = 0; subtree[a] = 1; for(int b : w[a]) if(b != parent) { dfs(b, a); height[a] = max(height[a], height[b] + 1); subtree[a] += subtree[b]; for(int i = 0; i <= height[b]; ++i) cntDistance[a][i+1] += cntDistance[b][i]; } } public int solve(int[] parent) { final int N = parent.length + 1; if(N == 1) return 0; int[][] C = new int[N+1][N+1]; for(int i = 0; i <= N; ++i) { C[i][i] = C[i] = 1; for(int j = 1; j < i; ++j) C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD; } w = new List[N]; for(int a = 0; a < N; ++a) w[a] = new ArrayList(); for(int a = 1; a < N; ++a) { int b = parent[a-1]; w[a].add(b); w[b].add(a); } int[] totalGoodSubsets = new int[N+1]; // how many subsets of N vertices are enough to detect the special vertex for(int root = 0; root < N; ++root) { height = new int[N]; subtree = new int[N]; cntDistance = new int[N][N]; dfs(root, -1); List childrenAndRoot = new ArrayList(); for(int x : w[root]) childrenAndRoot.add(x); childrenAndRoot.add(root); height[root] = 0; // fake value for(int child : childrenAndRoot) for(int my_dist = 0; my_dist <= height[child]; ++my_dist) { boolean isRoot = child == root; // treasure is in the root if (cntDistance[child][my_dist] == 1 || isRoot) { int[][] subsets = new int[N]; // subsets[S][SUB] - how many subsets of N-1 vertices have size 'S' and are from 'SUB' subtrees subsets = 1; for (int c : w[root]) if (c != child) for (int S = N - 1; S >= 0; --S) for (int SUB = 2; SUB >= 0; --SUB) if (subsets[S][SUB] != 0) { for (int here = 1; here <= subtree[c]; ++here) { int S2 = S + here; int SUB2 = min(SUB + 1, 2); subsets[S2][SUB2] = (int) ((subsets[S2][SUB2] + (long) subsets[S][SUB] * C[subtree[c]][here]) % MOD); } if (height[c] >= my_dist && !isRoot) subsets[S][SUB] = 0; // we must take a vertex from this subtree // so it's forbidden not to take anything (here = 0) } // now we must consider taking the root for (int size = 0; size <= N - 1; ++size) { totalGoodSubsets[size] = (totalGoodSubsets[size] + subsets[size]) % MOD; // no root for (int SUB = 0; SUB <= 2; ++SUB) totalGoodSubsets[size + 1] = (totalGoodSubsets[size + 1] + subsets[size][SUB]) % MOD; // with root } } } } int[] fac = new int[N+1]; fac = 1; for(int i = 1; i <= N; ++i) fac[i] = (int) ((long) fac[i-1] * i % MOD); long answer = 0; for(int size = 0; size <= N; ++size) { long badSubsets = (long) C[N][size] * N - totalGoodSubsets[size]; answer = (answer + badSubsets % MOD * fac[size] % MOD * fac[N-size]) % MOD; if(answer < 0) answer += MOD; } return (int) answer; } 
 » [user:hmehta]Problem archive page shows the round as SRM 764. Shouldn't this be SRM 762 : https://www.topcoder.com/tc?module=ProblemArchive&sr=&er=&sc=&sd=&class=&cat=&div1l=&div2l=&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=
•  » » yup, that was a typo! this will be fixed in a while