Inspired by similar blogs in the past and contestants' reaction about the Kanpur Regional on various CP groups, making this blog...
Just to clarify, I have nothing to do with the contest. I am neither a contestant nor a setter/tester, just a regular contribution beggar.
When will the final ranklist be revealed ???? T-T
JEE forces
Is this theory somehow related to coulomb's law???
No, it was Dijkstra's algorithm
Are you sure we cannot apply Persistent SegmentTree with Lazy Propogation and then do sqrt decomposition on the ball with 6-D path Dp on the path of ball and finally do binary search on segments?
That also works. But you will get TLE with the given constraints.
The constraints in this question were so tight for no reason at all. We kept getting TLE while calculating a simple two line formula in Python3 and C++. The same code in Python 2 passed.
How many did you guys solve?
What is the final formula for this problem? We came up with a formula but unfortunately it had precision errors (might be incorrect).
we faced the same issue due to precision errors. we combined a bunch of formulas to get an answer but were facing precision issues. :(
$$$v = sqrt(2gh)$$$ (Initial velocity)
$$$X = v*sinΘ*T+0.5*gsinΘ*T^2$$$
$$$verTime = 2v/g$$$ (Time to go up and back down)
$$$t = T-floor(T/verTime)*verTime$$$
$$$Y = v*cosΘ*t-0.5*gcosΘ*t^2$$$
$$$answer = sqrt(X^2 + Y^2)$$$
(SS of the code: here)
This problem isn't even original lol
A: https://www.codechef.com/SNCKPA16/problems/MAKELIS , https://csacademy.com/contest/beta-round-6/task/lis_generator/
Press F to pay respect
What did you google search exactly?
I guess he remembers each and every problem he solves!
"codechef find a permutation with exactly k longest increasing subsequence" gave me the MAKELIS editorial.
I guess , using any other site was not allowed during the contest.
This question and all its submissions must be removed
Where can I access the contest? I could not find it on CodeDrills.
Because it is hosted on the best website (read worst) in the world algocodemarshal.
Could someone upload the problems in pdf format as even registering on the website seems a bad option.
I literally heard of this website the first time.
Lucky you
It is on codemarshall
Our team received WA verdicts for two of the questions. Tried debugging for ~2 hrs but failed. Eyebrows were raised when a O(1) submission was exceeding TL. Tried printing just '0' just to be sure and yet it gave TLE and we realized something is messed up with the platform. Re-submitted the same solutions afterward and both of them got accepted. Turns out we tried to debug two correct solutions for more than half of the contest.
Technical glitches are a part of the game, and I as a participant have learned to accept them but this was something new and surely a new rock-bottom. Never thought such deplorable circumstances would arise in a regional round of the prestigious ICPC. Also, this was our last attempt and we planned to bid adieu on a pleasant note but it has left a bad taste.
This is really sad to hear :(
That is very sad to hear! Something similar happened to us. We submitted problem G and got TLE. Spent 45mins debugging what's wrong and couldn't figure out. Then we submitted the Physics question and still got TLE.
This TLE submission was $$$\mathcal{O}(T)$$$, so we were very surprised. Immediately, we converted both our problem G and problem C codes to C language (instead of C++), and submitted, and got both the probelms AC! :(
The problem D was very similar in idea to a recent codeforces problem "Aquamoon and strange Sort".
In fact using the method given in this comment would give one an AC.
Yup, they were very similar problems.
The rank list that they provided at the end of 3 hours, shows only the number of problems solved by the teams but not teams don't correctly match the number of problems they solved.
How to solve F?
For a fixed starting position, prefix gcd changes only log(A_max) times. So we can find n*log(A_max) tuples of type [g,L,R1,R2] , where subarrays [L,R1] to [L,R2] has gcd g.
Let's consider queries for single gcd g :
we maintain a segment tree where ith value stores maximum length of subarray ending at that index. For a single tuple [L,R1,R2] we add R1-L+1 at index R1, R1-L+2 at index R2 and so on. Process all the tuples and queries offline in reverse sorted order of L.
Really cool, we did the first part but couldn't figure out how to actually do the queries in time.
HC Verma be like: As a problem setter ...
How to solve E?
We were able to find all subsets of people who could be placed in the same house using dp in $$$\mathcal{O}(n2^n)$$$. Then we tried doing a mask-submask dp to get the actual answer, but that worked in $$$\mathcal{O}(3^n)$$$ which was too slow. We also tried making some optimizations, like consider only valid subsets of people if they are maximal, but the solution still TLEd.
We have a solution which we believe is correct but we were getting WA.
Apply meet in the middle. Divide the people into two groups
left_part
andright_part
, calculatedp[mask]
for all subsets inleft_part
andright_part
separately in $$$O(3^{10})$$$. Now consider a pair of subsets fromleft_part
andright_part
i.e{m1, m2}
, Calculatedp[m1 | m2]
by iterating over all subsets ofm1
i.e.dp[m1 | m2] = min(dp[m1 | m2], dp[m1 ^ b]+dp[m2 | b]
, where b is the subset of m1.Overall complexity: $$$(O(T*(3^{10} * 2^{10})) = O(T*(6^{10}))$$$
The total number of operations are roughly $$$6e8$$$ and 4 sec is a little strict but it should pass.
Can you plz. help in problem D A Splash of Rain ?
Sure, observe that parity of initial index and final index should remain same as i <-> i+2. But there can be duplicates, so for all values the number of odd/even indices in initial array must be equal to number of odd/even indices in the final sorted array.
What if the optimal solution required people from left_group and right_group to live in the same home?
Ok so we had a solution using fwht which passed in around 2.8s. Lets enumerate all "good" masks as you stated above. Now consider a polynomial $$$P$$$(of degree $$$2^{n}$$$), where coeff of $$$i$$$ is $$$1$$$ if mask $$$i$$$ is good. Suppose mask $$$2^{n} - 1$$$ is good, then answer is 1 for sure. It can be seen that the optimal solution is bitwise xor of some good masks, so we need to figure out how many minimum good masks are required to get $$$2^{n}-1$$$. Now we add one by one taking xor convolution of current polynomial $$$Q$$$ with intial polynomial $$$P$$$. After $$$n$$$ iterations we will surely find our answer, and if our answer is $$$x$$$, then $$$P^{x}$$$ must be having coeff of $$$2^n-1 > 0$$$. So just take fwht $$$n$$$ times and print the very first moment where we can obtain mask $$$2^n-1$$$. This is a bit weird solution acc to me. But it was completely random hit and trial.
I'm not familiar with fwht, but we tried an idea that I think was similar to yours.
We found the set $$$S_1$$$ consisting of all "good" masks. These masks require only one house. We computed $$$S_2$$$ by combining all pairs of masks from $$$S_1$$$ and taking the unseen masks. Then we compute $$$S_3$$$ by combining $$$S_1$$$ and $$$S_2$$$. Similarly, we compute $$$S_4$$$ by combining $$$S_1$$$ and $$$S_3$$$, and by combining $$$S_2$$$ and $$$S_2$$$. We do this until we place the mask $$$2^n - 1$$$ in some set.
Unfortunately, this solution TLEs. The size of $$$S_1$$$ could be potentially $$$2^n$$$. So we thought we could consider the effective set $$$S_1^{*}$$$ which is $$$S_1$$$ after removing any mask that is a submask of some other mask in $$$S_1$$$. This solution TLEd as well.
Yes, the solution is same as you mentioned. The point is, that combination process is much faster using FWHT (Fast Walsh Hadamard Transform).
I think you can speed it up using OR convolution, pre computation of fwht transform and binary search on the answer. During binary search we can get inverse fwht of mid convolutions. Time Complexity should be T*(N log N + log(log(N)) * N * log(N))
Yes, we can do this. But AC comes first in a contest then optimizations lol.
Find all bitmasks that represent valid house assignments. Then use fast subset transform to OR "polynomials" of these bitmasks till you get the polynomial which has all bits 1 mask present. Answer is number of times you had to use FST+1. Complexity n^2*2^n
How to solve G: K-ary Game?
Alice will always pick the root node first. After that, all the edges are split into k different/disjoint components and since K is even, Bob will take exactly half and Alice will take the other half of the remaining edges. Let the total number of edges be: N. Then the answer should be K + (N-K)/2.
The number of non leaf nodes in a k-ary tree would be : 1 + k^2 + k^3 + ....... k^(d-1). Since D<=1e9, a simple loop will give TLE so we use matrix exponentiation to calculate the abouve expression in log(d). After this, the answer is simple to calculate
Rather than using Matrix Exponentiation, we can also use the Divide and Conquer approach used in FFT.
Assuming d = 11:
$$$1+k+k^2+k^3+k^4+..k^{10}$$$
can be written as
$$$(1+k^2+k^4+k^6+k^8)+k(1+k^2+k^4+k^6+k^8) + k^{10}$$$
$$$k^{10}$$$ can be calculated separately using binary exponentiation. Expression inside brackets can be transformed to $$$1+x^1+x^2+x^3+x^4$$$ where $$$x = k^2$$$ and putting it back in the equation.
This can be performed recursively to give a $$$O(log d)$$$ complexity.
I don't know FFT. Maybe I will learn it now xd.
But I solved it using Mat Expo, gave TLE at first, but then after some optimizations it passed :)
You don't need to learn FFT to understand this.
I am just using the value computed once for both even and odd parities of power (which will be almost half in any equation). And I am doing this recursively passing $$$k$$$ as $$$k^2$$$, dividing powers by 2 and again making them in 2 sets of even and odd parities.
How to use matrix exponentiation.
Errichto has a very nice playlist for that, just search on youtube!
Is there any notification or expected time for final ranklist? I am tired of checking every hour.
Lmao, why even wait for rank list when no other team even solved 7 XD. Anyways, congrats!
F
Yeah, we were sure of the win but still we wanted to see our name in final ranklist xD.
The final ranklist is out!
Can you share the link for the same
https://algo.codemarshal.org/contests/kanpur_2020/standings
Is this ICPC 2021-22 or 2020-21? Can we expect 2021-22 india regionals this December (if exists)?
Amritapuri RCD in the online round's problem discussion session said he would try to hold next season's regional in December this year. He won't wait for long in hope of an onsite regional.
Are there no prizes or certificates this time?
The ranks are not same in Final standings on codemarshall and in ICPC certificate. Why is it so? PS. My team jumped 31 ranks in ICPC certificate xD
where did you find the certificate? If you're talking about Kanpur regional
In dashboard by logging into icpc global
We ranked in top 40 and have received a certificate of type regional champion. Is it like a participation certificate or what?
Did everyone get it?