Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### T1duS's blog

By T1duS, history, 3 months ago,

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.

• +269

 » 3 months ago, # |   +53 When will the final ranklist be revealed ???? T-T
 » 3 months ago, # |   +341 JEE forces
•  » » 3 months ago, # ^ |   -22 Is this theory somehow related to coulomb's law???
•  » » » 3 months ago, # ^ |   +15 No, it was Dijkstra's algorithm
•  » » » » 3 months ago, # ^ |   -11 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?
•  » » » » » 3 months ago, # ^ |   -11 That also works. But you will get TLE with the given constraints.
•  » » » » » » 3 months ago, # ^ |   0 Then I think we can reduce memory to constant space by using splay tree instead of persistent segment tree and then do 12 dimensional dp on path and finally centroid decomposition with parallel binary search
•  » » 3 months ago, # ^ | ← Rev. 2 →   +17 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.
•  » » » 3 months ago, # ^ |   0 How many did you guys solve?
•  » » 3 months ago, # ^ |   +15 What is the final formula for this problem? We came up with a formula but unfortunately it had precision errors (might be incorrect).
•  » » » 3 months ago, # ^ |   +12 we faced the same issue due to precision errors. we combined a bunch of formulas to get an answer but were facing precision issues. :(
•  » » » 3 months ago, # ^ |   0 Was your formula accounting for the change in velocity after every bounce? 'Cause ours did, but still it was producing incorrect results.
•  » » » » 3 months ago, # ^ |   0 yes, it was the same as you described with small precision errors.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +11 $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) •  » » 3 months ago, # ^ | -33 i think codeforces should add problems like this.math n physics>cp •  » » 3 months ago, # ^ | +28 SpoilerThis problem isn't even original lol  » 3 months ago, # | ← Rev. 2 → +102 •  » » 3 months ago, # ^ | +54 Press F to pay respect •  » » 3 months ago, # ^ | +9 What did you google search exactly? •  » » » 3 months ago, # ^ | 0 I guess he remembers each and every problem he solves! •  » » » 3 months ago, # ^ | +13 "codechef find a permutation with exactly k longest increasing subsequence" gave me the MAKELIS editorial. •  » » » 3 months ago, # ^ | 0 I guess , using any other site was not allowed during the contest. •  » » 3 months ago, # ^ | ← Rev. 2 → +19 This question and all its submissions must be removed  » 3 months ago, # | 0 Where can I access the contest? I could not find it on CodeDrills. •  » » 3 months ago, # ^ | +58 Because it is hosted on the best website (read worst) in the world algocodemarshal. •  » » » 3 months ago, # ^ | +6 Could someone upload the problems in pdf format as even registering on the website seems a bad option. •  » » » 3 months ago, # ^ | +7 I literally heard of this website the first time. •  » » » » 3 months ago, # ^ | +31 Lucky you •  » » 3 months ago, # ^ | 0 It is on codemarshall  » 3 months ago, # | +195 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. •  » » 3 months ago, # ^ | +24 This is really sad to hear :( •  » » 3 months ago, # ^ | ← Rev. 2 → +35 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! :(  » 3 months ago, # | +6 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. •  » » 3 months ago, # ^ | +4 Yup, they were very similar problems.  » 3 months ago, # | ← Rev. 2 → -8 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.  » 3 months ago, # | +20 How to solve F? •  » » 3 months ago, # ^ | +25 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. •  » » » 3 months ago, # ^ | +9 Really cool, we did the first part but couldn't figure out how to actually do the queries in time.  » 3 months ago, # | +243 HC Verma be like: As a problem setter ...  » 3 months ago, # | +11 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. •  » » 3 months ago, # ^ | ← Rev. 3 → +9 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 and right_part, calculate dp[mask] for all subsets in left_part and right_part separately in O(3^{10}). Now consider a pair of subsets from left_part and right_part i.e {m1, m2}, Calculate dp[m1 | m2] by iterating over all subsets of m1 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. •  » » » 3 months ago, # ^ | 0 Can you plz. help in problem D A Splash of Rain ? •  » » » » 3 months ago, # ^ | 0 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. •  » » » 3 months ago, # ^ | 0 What if the optimal solution required people from left_group and right_group to live in the same home? •  » » 3 months ago, # ^ | ← Rev. 2 → +16 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. •  » » » 3 months ago, # ^ | +4 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. •  » » » » 3 months ago, # ^ | +9 Yes, the solution is same as you mentioned. The point is, that combination process is much faster using FWHT (Fast Walsh Hadamard Transform). •  » » » 3 months ago, # ^ | 0 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)) •  » » » » 3 months ago, # ^ | +21 Yes, we can do this. But AC comes first in a contest then optimizations lol. •  » » 3 months ago, # ^ | +13 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  » 3 months ago, # | +12 How to solve G: K-ary Game? •  » » 3 months ago, # ^ | +8 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. •  » » 3 months ago, # ^ | ← Rev. 3 → +4 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 •  » » » 3 months ago, # ^ | +3 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.
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 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 :)
•  » » » » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   0 How to use matrix exponentiation.
•  » » » » 3 months ago, # ^ |   0 Errichto has a very nice playlist for that, just search on youtube!
 » 3 months ago, # |   +43 Is there any notification or expected time for final ranklist? I am tired of checking every hour.
•  » » 3 months ago, # ^ |   +17 Lmao, why even wait for rank list when no other team even solved 7 XD. Anyways, congrats!
•  » » » 3 months ago, # ^ |   +6 F
•  » » » 3 months ago, # ^ |   +12 Yeah, we were sure of the win but still we wanted to see our name in final ranklist xD.
 » 3 months ago, # |   +24 The final ranklist is out!
•  » » 3 months ago, # ^ |   0 Can you share the link for the same
•  » » » 3 months ago, # ^ |   0
 » 3 months ago, # | ← Rev. 2 →   +16 Is this ICPC 2021-22 or 2020-21? Can we expect 2021-22 india regionals this December (if exists)?
•  » » 3 months ago, # ^ |   +14 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.
 » 3 months ago, # | ← Rev. 2 →   +1 Are there no prizes or certificates this time?
 » 3 months ago, # | ← Rev. 2 →   +15 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
•  » » 3 months ago, # ^ |   0 and in ICPC certificateHave the certificates been issued? I gave Gwalior Regional for context.
•  » » 3 months ago, # ^ |   0 where did you find the certificate? If you're talking about Kanpur regional
•  » » » 3 months ago, # ^ |   +2 In dashboard by logging into icpc global
 » 3 months ago, # | ← Rev. 2 →   +5 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?
 » 3 months ago, # |   -47 Does anyone know when will the regional contest be hosted? Also how many teams are going to the regional?