Блог пользователя T1duS

Автор T1duS, история, 3 года назад, По-английски

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 года назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +341 Проголосовать: не нравится

JEE forces

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -22 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +15 Проголосовать: не нравится

      No, it was Dijkstra's algorithm

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится -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 года назад, # ^ |
            Проголосовать: нравится -11 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    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 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # ^ |
      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 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится
    Spoiler

    This problem isn't even original lol

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +102 Проголосовать: не нравится
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    This is really sad to hear :(

  • »
    »
    3 года назад, # ^ |
    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 года назад, # |
  Проголосовать: нравится +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 года назад, # |
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 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

How to solve F?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +243 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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 года назад, # ^ |
    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    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 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # ^ |
          Проголосовать: нравится +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 года назад, # ^ |
        Проголосовать: нравится 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 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

How to solve G: K-ary Game?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # ^ |
    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 года назад, # ^ |
        Проголосовать: нравится +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 года назад, # ^ |
        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 года назад, # ^ |
            Проголосовать: нравится 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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How to use matrix exponentiation.

»
3 года назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

The final ranklist is out!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Are there no prizes or certificates this time?

»
3 года назад, # |
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 года назад, # |
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?