SleepyShashwat's blog

By SleepyShashwat, history, 5 years ago, In English

Greetings Codeforces Community!

I would like to invite you all to participate in the Exun 2019 Programming Prelims. The contest will be 2.5 hours long and will contain 6 problems. All the problems will be from IOI Syllabus.

The contest is rated for everyone.

The problems are prepared by Tarrus, AwakeAnay and me. I would also like to thank taran_1407, arjunarul and the rest of the CodeChef team for helping with testing and reviewing the problems.

Contest Details:-

  • Start Date and Time : 11th October 2019 (19:30 hrs) to 11th October 2019 (22:00 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
  • Registration: You just need to have a CodeChef handle to participate. All those who are interested and do not have a CodeChef handle are requested to register in order to participate.
  • Registration for Onsite Finals : All Indian School Students are eligible for the onsite finals at Delhi Public School R.K. Puram, you can register here and then fill this form.
  • Prizes: Top 10 performers in the Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies.Other than that, five random participants and the first user to solve each problem will also get CodeChef laddus.
  • The ranklist will be IOI style.

Good Luck!

Hope you enjoy solving the problems!

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

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

Looking forward to the contest! Thank you for taking this initiative at such a young age, a true living legend!

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

Auto comment: topic has been updated by SleepyShashwat (previous revision, new revision, compare).

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

How to solve the second last problem Anay and Polynomial?

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

    Find the value of $$$P$$$ for all tuples $$$(x_1, ... , x_n)$$$ such that $$$x_i = 1, -1$$$. If you add all of them then the only term that will remain are the coefficients with even power for all $$$x_i$$$'s and each is counted $$$2^n$$$ times.

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

    Here's my solution with proof:

    Solution

    Btw, this was my first time setting a problem, so I hope you enjoyed it.

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

      Can you explain why $$$A = B$$$?

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

        "This has various proofs."

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

        $$$A, B$$$ are number of even and odd elements subsets of $$$[1, 2, 3, .. n]$$$.

        Let $$$S$$$ be number of subsets of $$$[1, 2, .. n - 1]$$$ respectively.

        Consider $$$A$$$ : if the subset contains $$$n$$$ then we map the subset to an odd element subset of $$$[1, 2,.. n - 1]$$$ containing all its elements but $$$n$$$, otherwise we map it to itself. Thus, $$$A = S$$$.

        Similarly, consider B : if the subset contains $$$n$$$ then we map the subset to an even element subset of $$$[1, 2,.. n - 1]$$$ containing all its elements but $$$n$$$, otherwise we map it to itself. Thus, $$$B = S$$$.

        Therefore, $$$A = S = B$$$

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

      I just understood your solution and I really enjoyed and loved your solution. I initially thought that it would be too advanced but after going through it, I managed to understand the entire solution !

      The main idea is to get the $$$P(1)$$$ and $$$P(-1)$$$ and generalise it to a tuple.

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

Unfortunately, I couldn't solve some of the problems during the contest but came up with the solution afterwards. How do I submit the solutions now and upsolve them ? I can't find the problems in the Problem Section.

UPDATE — The problems have now been added to the Practice Section and I can make submissions to the problems now :)

Also, I liked the questions and am open to discussing them. Here are my solutions to the contest

  • $$$A$$$ — Observation and Mathematics. How to solve $$$A$$$ if the uniqueness constraint was removed ?

  • $$$B$$$ — Observation and Construction — While this was easy, it was not obvious on sight. Had a good time coming up with this.

  • $$$C$$$ — Segment Trees and Binary Search on Prefix Sum — I kept an auxiliary array where $$$A_i = 1$$$, if the $$$i$$$ th element is not a multiple of the $$$(i — 1)$$$th element. I found this easier than $$$D$$$ , even though I see $$$D$$$ had far more successful submissions.

  • $$$D$$$ — DFS

I look forward to discussing $$$E$$$ and $$$F$$$!

  • $$$E$$$ — Thanks to AwakeAnay for explaining the solution
  • $$$F$$$ — SleepyShashwat, would you like to explain the solution to F — Dipole Moment ?
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    During contest, I wrote an overkill solution for C using lazy propagation but after the contest, I realized by looking at other people submission's that there is an easier solution wherein you can simply maintain the starting point of every range of elements using a set. Code

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

      Ah so just insert the beginning of all segments into a set and do binary search on every query ? Interesting idea ! Fantastic !

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

        Yes. For an update at the ith index, there are a few cases, firstly check to see if there is a change between the ith and the (i+1)st index.

        1. If a[i] used to divide a[i+1] earlier, but now it does not, a new segment starts at index (i+1). So, insert (i+1) into the set.

        2. If a[i] did not divide a[i+1] earlier, but now it does, the segment for (i+1) must be merged with the previous segment by just simply erasing (i+1) from the set.

        Similar cases must be handled for a[i] and a[i-1].

        And for a query simply output the largest index in the set <= i.

        BTW, your comment above is showing "Unable to parse markup [type=CF_MATHJAX]"

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

    Regarding your solution for Problem C: The complexity of your solution is $$$O((lg N)^2)$$$ per query since you perform a binary search and also a prefix query at every step using the segment tree. There exists a very neat trick to optimize the complexity of this thing to $$$O(lg N)$$$ per query.

    The idea is to perform a dfs on the segment tree. You start at the root node of the segment tree. If (left == right), you have found the index that we needed as the answer. Otherwise, consider the value at the left child (the sum of the elements in the left half). If this is <= sum (the required value), move towards the left child. Otherwise, move towards the right child and reduce sum by the value by the value at the left child node. Modified Code

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

      Oh wow !

      Thanks for taking the time to read my code and provide a new idea to optimise it by going through the Segment Tree intelligently.

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

When will the rating be updated for this contest? After long challenge ends or before it?

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

    "The ratings for this contest will be calculated once October Long Challenge gets over."

    -From the announcement section.

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

Don't forget to update scoreboard before rating recalculation. Currently, it doesn't count few AC submissions sent in last seconds and processed after contest ends.

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

    Seriously!!
    Some proof of your claim that scoreboard is not updated please? Some usernames of affected people?

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

      Me, obviously. Username: gultai4uk_r
      Last AC solution has been submitted 10 seconds before contest ends.
      Scoreboard correctly shows my points for each problem but the sum is wrong (it doesn't count my last submission).

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

      It also affected spellstaker with last AC submitted 12 seconds before contest ends and singhanuj123 with last AC submitted 7 seconds before contest ends.

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

        Create a blog on cc discuss tagging @admin and @vijju123 asking for updatation of the rank list along with these screenshots. Nobody will take cognizance from a comment here. In case you don't create blog nobody will update rank list and ratings will be calculated without these corrections.

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

The best contest that I have taken part in lately!

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

Any idea as to why are the problems showing up as partially accepted in the practice section, while my submissions showed up as 100 points.

Screenshot:

Screenshot-2019-10-14-Code-Chef-User-Code-Chef

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

When will the ratings be updated?