T1duS's blog

Indian ICPC — Kanpur Regionals trolling blog
By T1duS, history, 3 years ago, In English

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.

  • Vote: I like it
  • +269
  • Vote: I do not like it

Comments Comments (68)
| Write comment?
»
3 years ago, # |
  Vote: I like it +53 Vote: I do not like it

When will the final ranklist be revealed ???? T-T

→ Reply
»
3 years ago, # |
  Vote: I like it +341 Vote: I do not like it

JEE forces

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    Is this theory somehow related to coulomb's law???

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      No, it was Dijkstra's algorithm

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -11 Vote: I do not like it

        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?

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -11 Vote: I do not like it

          That also works. But you will get TLE with the given constraints.

          → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    What is the final formula for this problem? We came up with a formula but unfortunately it had precision errors (might be incorrect).

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      we faced the same issue due to precision errors. we combined a bunch of formulas to get an answer but were facing precision issues. :(

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +11 Vote: I do not like it

      $$$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)

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it
    Spoiler

    This problem isn't even original lol

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +102 Vote: I do not like it

A: https://www.codechef.com/SNCKPA16/problems/MAKELIS , https://csacademy.com/contest/beta-round-6/task/lis_generator/

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I access the contest? I could not find it on CodeDrills.

→ Reply
»
3 years ago, # |
  Vote: I like it +195 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    This is really sad to hear :(

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +35 Vote: I do not like it

    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! :(

    → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      Really cool, we did the first part but couldn't figure out how to actually do the queries in time.

      → Reply
»
3 years ago, # |
  Vote: I like it +243 Vote: I do not like it

HC Verma be like: As a problem setter ...

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +9 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you plz. help in problem D A Splash of Rain ?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What if the optimal solution required people from left_group and right_group to live in the same home?

      → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Yes, the solution is same as you mentioned. The point is, that combination process is much faster using FWHT (Fast Walsh Hadamard Transform).

        → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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))

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        Yes, we can do this. But AC comes first in a contest then optimizations lol.

        → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

How to solve G: K-ary Game?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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 :)

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How to use matrix exponentiation.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Errichto has a very nice playlist for that, just search on youtube!

        → Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Is there any notification or expected time for final ranklist? I am tired of checking every hour.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Lmao, why even wait for rank list when no other team even solved 7 XD. Anyways, congrats!

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      F

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Yeah, we were sure of the win but still we wanted to see our name in final ranklist xD.

      → Reply
»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

The final ranklist is out!

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Is this ICPC 2021-22 or 2020-21? Can we expect 2021-22 india regionals this December (if exists)?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Are there no prizes or certificates this time?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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?

→ Reply