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

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

Hello Codeforces,

Geekhaven, technical society of IIIT Allahabad is back with its annual contest. We are glad to invite you to participate in CodeSenso which will be hosted on CodeChef and will start on Wednesday, November 3, 2021 at 20:00 PM IST. It will be rated for the users of Div-2 and Div-3 but open for all participants.

There will be 7 problems of varying difficulties in each division and 3 hours to solve them.

Contest link: CodeSenso

There will be prizes worth INR 27k. To be eligible for prizes register here before 3rd November 11:30 PM IST.

Prizes:

  • Top 3 performers globally (from the combined ranklist of Div.1 and Div.2) will get a cash prize of INR 5000, 3000, 2000 respectively.

  • Top Indian performer (apart from top 3 global) will get a cash prize of INR 2500.

  • Top performer from IIIT Allahabad (apart from the above performers) will get a cash prize of INR 2500.

  • 10 GeeksForGeeks coupons worth INR 1200 each will be distributed randomly to 10 participants from the combined ranklist

  • Only Div.1 and Div.2 participants will be eligible for cash prizes and the non-scorable problems are not considered in that.

The problems have been authored and prepared by Sumit Kumar Sahu — phantom654, Abhinav — abhinav2302, Raghav Agarwal- rag-hav, Ansh Gupta — unknown0711, Dhananjay Raghuwanshi — dhananjay_777 and myself.

I would like to thank nishant403 for his valuable suggestions and improving the problems and mtnshh for helping with the test cases.

Editorials will be posted on the same thread after the contest.

Hoping to see you on the leaderboard in huge numbers.

UPD — Editorials have been posted.

Link to editorials :

DRNKALK MAXDAMGE CALPOWER GAMEW CAPATHS DLTNODE VKMWED GUNDIS BOWSAFE

If you have any doubts regarding any editorial feel free to ask them in the comments :)

UPD — Congratulations to the winners (CodeChef ID's of the winners has been mentioned) :

Top 3 Global :

  1. xiaowuc1

  2. kal013

  3. kostia244

Top from India : mafailure

Top from IIIT Allahabad : teach_me_snpai

  • Проголосовать: нравится
  • +135
  • Проголосовать: не нравится

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

Looking forward to participate.

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

Very excited to participate :)

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

Good luck everyone!

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

Really glad that CodeSenso is here.

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

very excited for the contest

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

Looking forward to participate

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

Excited to solve interesting problems, good luck everyone.

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

good luck everyone

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

Have the seniors told all juniors to write "Excited to participate:)"?

lmao

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

Looking forward to participate in the contest.

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

How to solve Gun Distribution? I think the optimal number of guns to give a person will always be very small (<= 5), but I have no clue how to proceed further.

Also I'm shocked how low the solve count is on VKMWED, the cases are pretty easy to analyze using stars and bars. Feels way easier than CAPATHS (I might be biased here though since I spent around 1 hour debugging it due to my poor implementation skills).

Edit — My general thoughts on the round:

DRUNKALK — Decent cakewalk, might have been slightly more interesting with $$$n \leq 10^9$$$

CALPOWER — A bit too standard for my liking

MAXDMGE — Cool idea but its appeared a lot recently in various contests.

GAMEW — Nice idea, natural and dissolves to a pretty direct dp.

DLTNODE — Is the intended euler order sparse table / segtree? No comments if so.

CAPATHS — Standardish dp on trees / rerooting, but formulation feels sort of forced just to match the solution.

VKMWED — Nice combinatorics. Its a bit obvious its going to become bars and stars but cool anyway.

Gun Distribution — Ran out of time but observations look interesting.

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

    Intimidation power of a person is at most 3. If $$$dp_i$$$ denotes maximum power for suffix starting from $$$i$$$, it is always in form $$$2^a3^b$$$. So, for each index, try all 3 ways and update correspoding dp value.

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

      Oops, my math went wrong somewhere then, I thought {2, 3, 4, 5} were possible and felt that would be non-trivial to compare.

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

      Can you please explain how to solve that Gun Distribution?

      I read that problem and started writing greedy approach but later realized that it was wrong.

      So how to do it with DP? Can you please explain me in detail?

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

    Thank you providing feedback for each problem. It really helps when preparing future contests.

    Here is my take on CAPATHS :

    Lets consider simple problem where we have to find a path having maximum sum. That is standard dp on trees.

    Now we can formulate the original problem as :

    Given a tree where each node has a pair {x,y} where x is 0/1. Find a path having maximum sum of y values such that xor of x values is 0. We can use standard dp on trees while maintaining maximum sum for xor 0 and 1.(+ve and -ve)

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

      I just up-solved the contest. The problems were really interesting and challenging. Looking forward to more such contests.

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

    Will it be possible for you to give cf ratings to these problems?

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

A block in the string is defined as a maximal non-empty substring consisting of the same character. For example, if S=0001110110011, there are 6 blocks: in order from left to right, 000,111,0,11,00,11.

Why didn't you cared for explaining the meaning of maximal (a bit more) in the problem GAMEW?
I got confused maximal with the "maximum length" for about 30 mins.

But, however I enjoyed the contest very much (esp. problem DLTNODE).

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

    For DLTNODE, I think the idea was nice, but the problem was made unecessarily hard for people who don't know segment trees/ sparse tables. Moreover it didn't actually contribute to the problem in any way.

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

      Edit: In this case there is a pretty cool solution and unfortunately there just happens to be a DS solution that passes — see this comment

      Such is life with most contests except for Codeforces (excl .Div3 and Edu) / Atcoder / Codechef Lunchtime and Cookoff.

      I spent 5-10 mins thinking about optimal patterns before realizing euler order spare table would work with no further observations lol.

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

      I think there are other solutions aside segment trees/sparse tables. I didn't use either of those, used something like rerooting.

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

      How to solve it using segment trees? I haven't seen any submission using segment trees.

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

      I solved the problem without segment tree or sparse tables, just precomputed gcd of all subtrees and did some rerooting for every node. It was very similar to one of the cses tree section problem. My submission: https://www.codechef.com/viewsolution/53453314

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

    maximal => If you have 000111, you cant take the substring [1, 2] or similar. Formally, you have to take an entire block $$$[l, r]$$$ such that

    • $$$s_l = s_{l + 1} = \ldots = s_{r}$$$
    • $$$l = 1$$$ or $$$s_{l - 1} \ne s_{l}$$$
    • $$$r = |S|$$$ or $$$s_{r} \ne s_{r + 1}$$$
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      Thanks for it. Actually, as the submissions increased, I realized that I'd complicated it much, and it should be a bit simpler. And, soon I noticed the pattern, $$$ 2, 5, 8, ... $$$ which follows $$$ \text{seg} \% 3 == 2 $$$ (for second person win).

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

        Oh that pattern is cool, I didn't notice it. My thought process was just that as long as we have 3 or more blocks, I can:

        • Reduce the total number of blocks by 1 if I remove a block at the end.

        • Reduce the total number of blocks by 2 if I remove a block in the interior causing the adjacent blocks to merge.

        So $$$x$$$ (where $$$x \geq 3$$$) is a winning state if and only if $$$x - 1$$$ or $$$x - 2$$$ is a losing state. This is trivial to compute using dp and is the general approach to solving quite a few game theory problems.

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

Can anyone share the idea of DLTNODE please?

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

    Prereq — Euler tours, sparse table/seg tree

    Root the tree at Node 1. Do an euler tour of the tree. Now when your destroy a node, the components that will be formed are subtrees of its children, and the part of the tree that remains after removing the subtree of the current node. With the help of euler tours, subtrees are transformed into ranges and GCD can be calculate with sparse table.

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

      what is the time complexity of ur solution?

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

        preprocessing euler tour + sorting with start time -> nlogn

        preprocessing sparse table -> nlogn

        finally checking for every node -> nlogn

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

    I used dp+ prefix and suffix arrays.

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится
    My Approach
»
3 года назад, # |
Rev. 4   Проголосовать: нравится +32 Проголосовать: не нравится

Intended solution for DLTNODE :

Lets consider a simple problem where we remove an element from array. Here we usually maintain prefix and suffix gcds.

We can do the same by flattening tree using euler tour and compute prefix,suffix gcds. Now we can find gcd of subtree using dfs and all nodes except subtree using these arrays. Works in O(N) (log of computing suffix gcd will be amortized)

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

    Ok wow that is pretty cool. Its unfortunate that the sparse table / segtree approach exists, the intended approach is pretty nice.

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

Can someone tell me the reason why the memory used by my code is abnormal for DLTNODE? Submission

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

Can anyone explain/give a proof of the formula for the number of ways to distribute <=n identical numbers into r groups in the editorial of Magic Weed. During contest, I was not able to figure this formula and was only able to solve it in O(n^2)(tle's). Formula:-C(n+r,r).

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

    It can be proved using multinomial theorem, Let's say you have r numbers whose sum is less than n $$$y1+y2+y3+\dots+yr<=n$$$

    Now we can add one more number which will always have the difference between sum of first r numbers and n. $$$y1+y2+y3+\dots+y(r+1)=n$$$.

    Let's say $$$k = r+1$$$

    Now we're going to express all the options available for first group as powers of x.

    So for first group -> $$$x^{0}+x^{1}+x^{2}+x^{3}+x^{4}+\dots+x^{n}$$$.

    You can read this as either it can have value 0 or 1 or 2 or 3 or 4 or $$$\dots$$$ or n Now similarily you can write this for all k groups and multiply them. $$$((x^{0}+\dots+x^{n})\times(x^{0}+\dots+x^{n})\times \dots \times(x^{0}+\dots+x^{n}))$$$.

    When multiplying these expressions what we do manually is we select some power of x from first group some power of x from second and so on and find out the resulting power of x and add that term in the final answer, right?

    That's what you will be doing in this questions as well right choosing some power of x for first group, some power of 2nd, some power for 3rd and so on and take the sum of all powers to find out the resulting power and add it to the final answer. Each multiplication will add 1 to the $$$x^{sum of all powers}$$$ i.e. 1 number of way to make sum equal to this power.

    So the above expression can be written as $$$(x^{0}+\dots+x^{n})^{k}$$$.

    We have to find the coefficient of $$$x^{n}$$$ in this expression and that will be the resulting answer.

    $$$x^{0}+x^{1}+\dots+x^{n}$$$ forms a G.P. So it will be equal to $$$\dfrac{1-x^{n+1}}{1-x}$$$. We have to find $$$x^{n}$$$ in $$$(\dfrac{1-x^{n+1}}{1-x})^{k}$$$. Now from numerator we will only need $$$x^{0}$$$ as all other powers will not be useful to us because all of them will be greater than n.

    Coefficient of $$$x^{0}$$$ is 1 in numerator.

    Expanding $$$(1-x)^{-k}$$$,

    $$$(1-x)^{-k}=1+\dfrac{k}{1!}\times x^{1}+\dfrac{k*(k+1)}{2!} \times x^{2}+\dfrac{k*(k+1)*(k+2)}{3!} \times x^{3} +\dots$$$

    Now you can easily observe that power of $$$x^{p}$$$ is $$$\binom{p+k-1}{k-1}$$$ and therefore the resulting coefficient of x^{n} will be

    $$$\binom{n+k-1}{k-1}$$$

    After putting $$$k = r+1$$$ we get $$$\binom{n+r}{r}$$$

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

      Thanks bro!.

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

        There is one other easier proof also using n+k-1 places and selecting k-1 barriers among them. And then these barriers will divide it into k different blocks. everything before first barrier will be x1. Everything in between first and second barrier will be x2 and so on. There are $$$\binom{n+k-1}{k-1}$$$ to do that.

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

    For contest you just have to remember the formula for number of ways to choose r numbers to have sum equal to n. That is $$$\binom{n+r-1}{r-1}$$$. Now you just have to think about taking difference in the sum as well to make sum equal to n and not less than n.Then you will have r+1 numbers whose sum will be equal to n.