kshitij_sodani's blog

By kshitij_sodani, history, 3 years ago, In English

Hello everyone!

T1duS, Ashishgup,xennygrimmato and I will be capturing the live updates of the Gwalior-Pune 2020 Regionals, for teams to later refer to first-solves and the state of ranklist after various times. It is inspired by similar blogs in the past, like this, for example.

Important Information:

Announcements:

  • All problems have a memory limit of 1GB, and solutions that exceed this would be marked as RTE instead of MLE due to some memory usage issues.

Live Updates:

  • 6.06pm: Treap Trilogy from BITS-Pilani, Goa Campus gets the first AC of the contest on the problem Jeff
  • 6.15pm: Jeff is now solved by 112 teams,Vichitrödinger's Cat by 13 teams and Apple Uniformity by 9 teams.
  • 6.23pm: Problem A gets its first AC
  • 6.27pm: Hold right there Sparky!! from IIT Roorkee is the first team to solve 4 problems.
  • 6.29pm: Sheesh! from IIT Jodhpur gets 2 ACs within 30 seconds to lead the scoreboard!
  • 6.40pm: Cheese_Maggi from IIT Guwahati gets first AC on Dimitrescu
  • 6.51pm: 473 teams have now solved at least 1 problem in the contest.
  • 7.03pm: Cheese_Maggi from IIT Guwahati Takes the lead by solving 5 problems.
Ranklist at 7:23 PM IST
  • 7.35pm : The top 9 teams have solved 5 problems each. The top 2 teams are separated by 8 minutes of time penalty.
  • 7.38pm: Cheese_Maggi solve their 6th problem and move up to the top of the scoreboard.
  • 7.58pm: Cheese_Maggi still lead, followed by 23 teams with 5 problems solved.
  • 8.24pm: Evil Geniuses from IIT Madras move up to Rank #2 after solving Fermod. Cheese_Maggi continue to lead with a 90-minute time-penalty lead.
  • 8.40pm KuchBhiRandom from IIT Kanpur also solve their 6th problem
  • 9.00pm Scoreboard has freezed
Ranklist at 8.58 PM IST
  • Vote: I like it
  • +39
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 3   Vote: I like it -67 Vote: I do not like it

ICPC Amritapuri 2020 Gwalior-Pune — Live Updates .... ok

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

    It even had a problem with 'Amrita University' in it. :-|

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

      My comment was in reference to the original name of this blog post, haha.

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Fix the scoreboard

»
3 years ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

Seems that some college names are clipped? IIIT-Hyderabad is appearing as just "International Institute of Information Technology". Also, can use this userscript to fix the amp issue on frontend temporarily: https://gist.github.com/GaurangTandon/1002be83974e3702605d9334668670d6

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

Dimitrescu was tricky to implement .

Was there any case for no? We could not find any.

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

    There's no case for no.

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

      We were unable to find the exact solution for it till end , some test cases were still getting Wrong. I think that there is a cleaner way of implementing it. what path did you adopt?

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

        We solved individually for each row. For the row with a star, you can break it into left and right parts. If both of them are of length != 1, you can solve them separately in the same way as you do for other rows. If one of them is of length 1, you can put a vertical 1x2 tile on that side and solve the remaining part of the two rows normally. If both of them are of length 1, you can transpose the matrix and do the same thing.

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

What is the solution for Problem A, Buy N Large?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Spoiler
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    Consider connected components of the graph formed by the initial associations.

    Lets consider the $$$\lfloor \frac{n}{2}\rfloor$$$ cheapest nodes of a given connected component to be coloured black, and the others coloured white.

    Clearly there always exists an edge between some black and white nodes, otherwise the component wouldn't be connected.

    Also after performing an operation on the nodes connected by this edge, the nodes are removed, but the component remains connected, so the previous logic still holds.

    In the case of odd sized components, we can just remove the median value (the smallest white coloured node) on its own, which will leave the graph connected allowing us to use the previously discussed logic.

    So we can always use the $$$\lfloor \frac{n}{2}\rfloor$$$ cheapest nodes of a given connected component to eliminate the $$$\lfloor \frac{n}{2}\rfloor$$$ costliest nodes.

    Code

    I'm still confused why the problem had $$$n \leq 1500$$$

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

      We couldn't come up with this proof and decided to submit and check if it works. It worked. :P Also that n<=1500 constraint somehow forced us to think if the intended solution is dp and not greedy. :P

      If that constraint was n<=1e5, pretty sure it will rule out dp approach and teams would have directly thought greedily on this one.

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

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem L Neelu in Wanderland, could it be solved using FFT?

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

    We got TLE with NTT, though FFT is faster so maybe it might pass? We didn't end up trying it though.

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

      I managed to solve it with knapsack after a few TLEs. For details, refer to problem G2 of the codeforces Raif round.

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

    We got TLE using a (hopefully) fairly fast FFT implementation, too

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

    FFT is not required.

    Since polynomial can be converted to this form :

    (1 + x^k + x^2k + ... + x^mk)

    We can find resultant polynomial in O(n) using prefix sums taken at k distances.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    My solution
»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Final Ranklist Plox!!!

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

Can anyone help me with the approach of J problem apple uniformity?

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

    Hint: The optimal answer will come from subsegment of length 2

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

    For a given $$$l$$$, $$$r = l + 1$$$ is always the best possible choice. This can be easily proved by analyzing all possible options of the $$$r = l + 2$$$ case.

    • If $$$a_{l + 2} \leq min(a_l, a_{l + 1}) \leq max(a_l, a_{l + 1}) $$$ — $$$answer= max(a_l, a_{l + 1}) - a_{l + 2} \geq max(a_l, a_{l + 1}) - min(a_l, a_{l + 1})$$$

    • If $$$min(a_l, a_{l + 1}) \leq a_{l + 2} \leq max(a_l, a_{l + 1})$$$ — $$$answer=max(a_l, a_{l + 1}) - min(a_l, a_{l + 1})$$$

    • If $$$min(a_l, a_{l + 1}) \leq max(a_l, a_{l + 1}) \leq a_{l + 2} $$$ — $$$answer= a_{l + 2} - min(a_l, a_{l + 1}) \geq max(a_l, a_{l + 1}) - min(a_l, a_{l + 1})$$$

    So in all cases, the answer is no better than the answer of just taking $$$r = l + 1$$$.

    Now when we update the power of a position $$$x$$$, the only two subarrays which change are $$$[x-1, x]$$$ and $$$[x, x + 1]$$$, so we can just remove the old values for these subarrays and add the new values.

    So we want to perform the following operations quickly:

    • Insert an element

    • Remove an element

    • Find minimum element

    A multiset can do all these operations in $$$O(log n)$$$.

»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

How did anyone solve problem C: Fermod? We had an answer for all odd M but thats it :/

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

    Could you please tell how did you get the answer for odd M?

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

    Solve for $$$m<=6$$$ by hand. So now take $$$m>6$$$, and let $$$p$$$ be the smallest prime factor of $$$m$$$.

    First suppose $$$p \neq m$$$. Then consider the quadruple -

    $$$(x,y,z,n)=(m/p,3,m/p+3,p) \text{ if } p>2$$$

    $$$(x,y,z,n)=(m/2,3,m/2+3,4) \text{ if } p=2$$$

    To show this works, use the fact that $$$p \mid \binom{p}{i}$$$ for all $$$i \in {1,2,\dots, p-1}$$$.

    Else if $$$m=p$$$, then take $$$n=p-2$$$, and notice that $$$x^{p-2} \equiv x^{-1} \pmod{p}$$$. So take the three cases $$$(x,y)=(3,3),$$$ $$$(3,4),$$$ $$$(4,4),$$$ and find $$$z \equiv (x^{-1}+y^{-1})^{-1} \pmod{p}$$$ for all three possibilities. It's easy to see that these three values will be different, and so one of them will be $$$>2$$$. Take the corresponding $$$(x,y,z)$$$.

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

      Is there any other solution to this problem?

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

        This is what we did -
        We wrote an offline brute force and it was pretty fast for the first 1e6 values.
        $$$m=4$$$ is the only impossible case.

        For most cases, one of the numbers was $$$3,5$$$. So we took $$$x=3,4,5,7,11$$$.

        We hardcoded the first 30 values.
        For other $$$m$$$, we had 2 different cases.

        If $$$m$$$ isn't prime then $$$n=phi(m)+1$$$ is less than $$$m$$$
        Euler's theorem $$$x^n \equiv x$$$ mod $$$m$$$
        So we ran a for loop for y from 2 to m-1 and tried all values of x among $$$3,4,5,7,11$$$ until we found one.

        For $$$m$$$ being prime,
        $$$p=m-1$$$ Lets chose some $$$n$$$,$$$a$$$ and $$$b$$$ let $$$t = n^{-1}$$$ mod $$$p$$$.
        We chose $$$x=a^t$$$ , $$$y=b^t$$$ and $$$z=(a+b)^t$$$ $$$x^n = (a^t)^n = a^{(t*n)} = a^{1 mod p} = a$$$ To bypass $$$2 \lt x,y,z,n \lt m$$$ restriction we just randomly chose $$$n,a,b$$$ until we found one which satisfied those requirements.

        Initially we took $$$x=3,5,7,11$$$ it was insufficient for $$$m=2^k$$$ we just added $$$x=4$$$ so that $$$x^n$$$ is $$$0$$$ for this mod.

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

          If bruteforce worked pretty fast, means values were pretty small, why didn't you just do that ?

          For x,y,z choose first 10 and last 10 numbers. For n choose all numbers as above plus the numbers around phi(m).

          I just tried it and it passed.

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

        Here's a much simpler solution:

        1. If $$$m$$$ is small, say $$$m \le 50$$$, just use a precomputed answer.
        2. If $$$m$$$ is not square-free, consider any prime factor $$$p$$$ that appears twice in $$$m$$$. Then a possible answer is $$$(m - 1, \frac{m}{p}, m - 1, \phi(m))$$$.
        3. If $$$m$$$ is even and square-free, note that $$$(\frac{m}{2}, 3, \frac{m}{2} + 3, 4)$$$ is an answer.
        4. If $$$m$$$ is odd and square-free, note that $$$(m - 1, m - 1, \frac{m - 1}{2}, \phi(m) - 1)$$$ is an answer.
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Can anyone provide me hint for the problem "House Hunting". I thought if we have to select K nodes from the tree so we should start from the bottom like filling the leaf nodes first and then moving to the level above until we select K nodes completely?. Am I correct?

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 3   Vote: I like it +10 Vote: I do not like it

            I had an idea during the contest to iterate on the center of the subtree(of k nodes). I think this can be implemented by binary search + centroid decomposition(to check the number of nodes further than a distance x from the center), but not sure as I had not figured out all the details

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

              I tried a similar solution and used segment tree for storing number of nodes at a particular distance from centroid to apply binary search but later figured out few cases were answer will be lower than my answer, I am not sure that such solution will work or not.

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

                I think it will work. When binary searching, if length is odd, keep edge as center else keep node as a center.

                To handle edges, just make another tree of n-1 nodes from edges.

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

                  Yes, this is the intended solution.

                  Bonus: Solve it in $$$O(n \log n)$$$

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

                  Find a random permutation of the n nodes. Before applying binary search on a particular node, check if the answer found earlier satisfies this node, or else skip that node. So we shall only apply binary search on approximately log n nodes. The resultant complexity would be nlogn.

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

        Solve for $$$ m\leq 6$$$. Now for $$$m > 6$$$,

        1. If $$$m$$$ is odd, then $$$(m - 2, m - 2, m - 1, \phi(m) - 1)$$$
        2. If $$$m$$$ is even, then $$$(m - 2, m - 2, m - 4, \phi(m) + 1)$$$

        Both the results can be easily proved.

        Edit : Only 2nd is enough, that is $$$(m - 2, m - 2, m - 4, \phi(m) + 1)$$$. The first one can be used for $$$m = 5$$$.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it -8 Vote: I do not like it
        My soln (very overkill):
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Will there be an official editorial / discussion session? Also, it would be great if some experienced coders could rate the difficulty level of the problems in terms of CF rating. Thanks.

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

Are we getting T-shirts and goodies this year?

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Problem Discussion Session is on Today 23rd Aug, 6 PM IST. Join us here.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted