yunetive29's blog

Codeforces Round #936 (Div. 2)
By yunetive29, history, 9 months ago, translation, In English

Hola, Codeforces!

We are pleased to invite you to participate in Codeforces Round 936 (Div. 2), which will start on Mar/22/2024 17:35 (Moscow time).

The round was prepared by exhausted, max0000561, azureglow and myself.

This round will be rated for participants whose rating is below 2100. Participants with higher ratings may participate out of the competition.

You will be given 6 problems and 2 hours to solve them. We hope you find them interesting.

We would like to thank:

Special thanks to KoT_OsKaR and teraqqq for their help in creating tasks.

Good luck on the round and high rankings to everyone!

Score Distribution: 500−1000−1500−1750−2250−2750.

UPD: The date of the round has been changed to avoid interference with a competition on another platform.

UPD: Editorial

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

»
9 months ago, # |
  Vote: I like it +65 Vote: I do not like it

As a tester, this is one of the coolest rounds I've ever seen

→ Reply
»
9 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Can I have a slice of pizza, please ?

→ Reply
»
9 months ago, # |
  Vote: I like it +27 Vote: I do not like it

That pizza looks delicious

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -46 Vote: I do not like it

    really ? then your standard is very low for pizzas

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

      Why alt? Scared of downvotes?

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it -29 Vote: I do not like it

        It seems like you are the one who is scared of downvotes and deletes his comment by editing if it gets a lot of dislikes.

        → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

As a tester, I think that this round is very nice

Good luck guys!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

As a tester, I recommend you to buy computers for the lowest price

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone eat pizza without sauce or mayonnaise? Anyway it looks delicious.

→ Reply
»
9 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Good job bois! I hope this contest will serve as a cornerstone for many to reach the heights of 1C. The best part is an afterparty in Marino. The great Holiday of Vyval is coming!!!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Enjoy the process!

→ Reply
»
9 months ago, # |
  Vote: I like it +10 Vote: I do not like it

pizza without toppings ??

→ Reply
»
9 months ago, # |
  Vote: I like it +187 Vote: I do not like it

Hopefully it is the start of 74TrAkToR's Redemption Arc

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The unusual round time tho :)

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

Hope reach pupil after this round

GL for everyone!!!!

→ Reply
»
9 months ago, # |
  Vote: I like it +55 Vote: I do not like it

Hope everyone will get positive abs(Good bye 2023's) delta.

→ Reply
»
9 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Hopefully mathforces❤️

→ Reply
»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

sigmaforces

→ Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

It is 2:00 a.m. and now I'm hungry 🥺

You didn't have to do this to me.

→ Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I think the timing is showing in UTC+3 for everyone

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think you posted the wrong time

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Pizzas and kudos to the authors for continuing the trend of attaching pictures!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's great to see CF round's authors posting images of their daily life again <3

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

wow!That pizza looks so delicious!

→ Reply
»
9 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Hoping for a pizza with positive Delta toppings...

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Users on this site have pretty weird satisfaction downvoting any thing they see,even their own picture. [:

→ Reply
»
9 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Yay 74TrAkToR First Round Coordination in 2024 !

→ Reply
»
9 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Participation from India will be lower due to IPL match.

→ Reply
»
9 months ago, # |
  Vote: I like it +23 Vote: I do not like it

The upd says "The date of the round has been changed to avoid interference with a competition." What competition is that?

→ Reply
»
9 months ago, # |
  Vote: I like it +70 Vote: I do not like it

UPD: The date of the round has been changed to avoid interference with a competition on another platform.

Average 74TrAkToR moment

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Now I want Pizza... :)

→ Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hope for a exciting contest <3

→ Reply
»
9 months ago, # |
  Vote: I like it +30 Vote: I do not like it

traktor bros going to cook us

→ Reply
»
9 months ago, # |
  Vote: I like it +19 Vote: I do not like it

UPD: The date of the round has been changed to avoid interference with a competition on another platform.

Which platform?

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The traktor bros are about to serve up something fierce

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck guys!

→ Reply
»
9 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Ramadan Kareem

→ Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I hope that round's problems would be like Pizza !!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

If I could get 1600 by the contest,I would be excited all day long.Try my best！

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Bro，you smell so good.

→ Reply
»
9 months ago, # |
  Vote: I like it -9 Vote: I do not like it

74TrAkToR :(

→ Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Why do I remember it was March 21st? Did I make a mistake？

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wonderful!! one small problem... I AM INSIDE UR HOUSE :3

→ Reply
»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

good luck everyone :>

→ Reply
»
9 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Seriously? Goodbye 2024 in March?

→ Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

pls everyone give me dislikes! I want to have lowest contribution!

→ Reply
»
9 months ago, # |
  Vote: I like it +27 Vote: I do not like it

EVERYONE DISLIKE MY COMMENT! I HATE THE JUDGES, I HATE EVERYONE!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

As a tester, our problems are well prepared, and as a tradition give me negative contribution. Please everyone give me dislikes!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +66 Vote: I do not like it

sorry, someone took my laptop

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -67 Vote: I do not like it

OH OH OH OH OH OH OH OH OH OH OH OH OH OH OH OH !

74TrAkToR Round !!!!!!!!!

74TrAkToR Round !!!!!!!!!

74TrAkToR Round !!!!!!!!!

74TrAkToR is the person in the photo you ? It looks very ......

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

    it is not surprising that such comments are left by gray authors

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think there is a problem about pizza ^-^, Good luck everyone

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

As one of their lecturers I strongly recommend you to participate in round! Hope you like it!

→ Reply
»
9 months ago, # |
  Vote: I like it -31 Vote: I do not like it

Hopefully it is the start of 74TrAkToR's Redemption Arc

→ Reply
»
9 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Yes,brother,as you see,I am back!

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

In one of recent contests, I submitted wrong algorithm but it passed the pretest so that I got FST on it. I hope the data in this contest is difficult enough that it will minimize the likelihood of FST. By the way, I hope I can become Expert.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm currently unrated. Will I get rating?

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

As a tester who forgot to test a round for three months, this round is very cool

→ Reply
»
9 months ago, # |
  Vote: I like it -14 Vote: I do not like it

IPL is clashing with this contest

→ Reply
»
9 months ago, # |
  Vote: I like it -7 Vote: I do not like it

hope to reach gm in this round!

→ Reply
»
9 months ago, # |
  Vote: I like it +17 Vote: I do not like it

As a participant, this is one of the coolest rounds I've ever seen

→ Reply
»
9 months ago, # |
  Vote: I like it +51 Vote: I do not like it

First solves:

mfw I get first solve
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem C?

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

    Binary search on the answer and greedily cut every sufficiently large subtree.

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

      I implemented that but somehow got WA. Can you please have a quick look at my solution to see where my mistake lies? Thanks

      252801186

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

        You are updating subtree sizes incorrectly. Say a is a parent of b and b is a parent of c. You cut c and subtracted its size from b. Now you cut b and subtract its updated size from a. But a was calculated using old subtree size of b, so you didn't subtract enough. You should calculate subtree sizes during the same dfs.

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

          You're absolutely correct! Thanks.

          I had the subtreeSize method in my lib and was lazy to implement it and then missed this :)

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

      I'm doing exactly this but getting WA2. Where is my mistake? 252806411

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

      But wouldn't there be too many options for cutting and each option affecting the answer ?

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

        Suppose we are looking for some x.

        A few important notes:

        Hint 1
        Hint 2
        Hint 3

        And the solution:

        Solution

        My solution: 252786253 (I'm sorry for somewhat dirty code, I was trying to implement is as fast as I could after I found out the solution).

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

      hi, I also do exactly like this but I dont know why I got WA :( I will be very happy if you can spend some time look through my code :) 252794634

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

        I'm sorry but I don't understand what you are doing. For starters, you have two dfs instead of one. Also, no offense but I find your coding style difficult to read. The best I can do is direct you to my submission 252744762

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

          Thanks for looking at my code! I found out the error alr, it is because I only cut the node when its weight >= ans and max weight of children node < ans, where ans is the answer we are looking in binary search. I shouldnt include the condition about the max weight of children nodes in my dfs1 function.

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

      In your solution, could you please tell that in can() func, what's the purpose of checking sz >= x again (at the end)? In all provided test cases, that condition never got satisfied. Thanks for sharing your solution, btw.

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

        Root has no parent so there is no $$$(v, p_v)$$$ edge to cut and hence I thought I had to handle it separately. However, upon further consideration, it appears that the logic inside DFS handled it just fine too since it's basically the same.

        → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is E based on inclusion-exclusion principle???

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

    My solution has nothing to do with PIE. First observe that $$$p_{m_1} = s_1$$$ and $$$a_{s_1} = n$$$. Now solve the problem for $$$p$$$ and reverse of $$$s$$$ independently. Iterate over $$$p$$$ in reverse, it's easy to find the number of candidates for each position.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a really interesting round for me! Problem B was annoying simply because C++ % operator apparently does not work for negative numbers.

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

    How did you solve that problem? Was stuck on it throughout the contest

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

      My approach was to find the maximum subarray sum over a using Kadane's algorithm. Then, simply add this sum into the contiguous subarray that holds the maximum subarray sum. Do this k times, each time updating the new maximum subarray sum and you will get the answer.

      Hope that made sense.

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

        Thanks for the explanation but I was asking about how you tackled the mod operator for negative numbers.

        (Got my answer, so no need to reply)

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

    Hey, at least now you won't make the same mistake again! Many players use a library for modular arithmetic. I use atcoder::modint, check it out.

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

    An easy workaround would be to use (x % mod + mod) % mod. (You can write it as a function to make the code shorter)

    → Reply
»
9 months ago, # |
  Vote: I like it -39 Vote: I do not like it

C >>>>> D (D is a garbage problem imo, literally solved in 10 minutes, just failed to implement 3 times)

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

    I solved C in 5 minutes but skipped D because it wasn't obvious to me. I think both problems are a bit boring but not bad for their positions in Div 2.

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

      I didn't solve C for an hour straight (how do you prove that greedy works?).

      D just felt like an implementation problem to me, not much thinking involved.

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

        Let S be a subtree that has >= x-1 children, and all its children have < x-1 children

        So cutting any of its children will invalidate the tree instantly

        If you have remaining cuts to make, we have two choices

        1- to cut now

        2- to leave this and cut later

        We need to prove that cutting now is the best option every time

        Suppose that cutting now will make the tree invalid and cutting a parent edge later will make the tree valid

        Remember that we have >= x-1 children right now, so the tree can be invalid only if the remaining tree without the current subtree has < x nodes, which will make any parent cut also invalid

        Which contradicts our assumption, so if there is a solution for x, we should always cut once we have >= x-1 children

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

        For each partition $$$P$$$, consider a deepest vertex $$$v$$$ where it differs from the greedy one $$$GP$$$. It means that greedy cuts edge $$$(v, p_v)$$$, where $$$p_v$$$ is parent of $$$v$$$ but $$$P$$$ doesn't. Note that it's impossible for $$$P$$$ to cut $$$(v, p_v)$$$ if $$$GP$$$ doesn't cut it.

        Let $$$u$$$ be the lowest ancestor of $$$v$$$ such that $$$P$$$ cuts $$$(u, p_u)$$$. Let's exchange these edges: consider $$$P' = (P \cup (u, p_u)) \setminus (v, p_v) $$$. We gained one new good component rooted at $$$v$$$ and lost one good component rooted at $$$u$$$ (and also increased the size of some component above $$$u$$$ but that's besides the point).

        Hence $$$P'$$$ is an equally good partition with a smaller "deepest different vertex". Choose $$$P^*$$$ to be the minimal partition by this criterion to infer $$$P^* = GP$$$.

        → Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

C humiliated me

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Surprisingly difficult C : Tree Cutting, but interesting nonetheless. I've added my hints and thought process on CF Step

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

    3000 people solved it.

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

      That doesn't change my viewpoint though, since I'm extrapolating from my past experiences of seeing problem C. Of course, there's bias involved.

      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E << C and D. I wasted too much time on C and D so ran out of time to debug E but I feel I'm close :(

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

    Problem difficulties are always subjective. I solved C in 5 minutes but spent an hour on E because I went in the wrong direction. I had dp[gap] = number of permutations with max - len = gap. It has interesting but complicated updates. I thought it could be solved this way, but eventually, I gave up and found a simpler solution.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this correct approach for D — We need to iterate over all the bits from 30 to 0 and try to merge numbers in pairs of two using DSU, depending upon whether that bit is set in x or not ?

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem C is the reason for my headache today.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Would anyone be able to tell my WHAT is wrong with my code for problem B?

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

    Do not mod best_sum and sum in the loop, maximum subarray sum can exceed mod (but cannot exceed int64_t). Mod it best_sum after the loop.

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

      Okay, that does make sense. Thank you a lot man, I was so frustrated I couldn't think reasonably.

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

      Yooo you just helped me on some interview problem in discord yesterday. Wasn't expecting to see u here, and thanks btw

      → Reply
»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it

how to not be blank on problems like E?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody tell why some test cases are not giving the correct answer : link

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I cracked the approach for problem D, just 1 minute after, ending of contest,

would have increased my delta by a lot :(

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

whats idea of D?

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

    Say we are looking for a partition into subarrays with OR = x (instead of $$$\le$$$). Then you can only partition at positions where the prefix xor is a submask of $$$x$$$. Such partitions are monotone by inclusion, so it is sufficient to consider a small subset of maximal masks $$$\le x$$$. Namely, $$$x$$$, and ((x >> bit) << bit) - 1 for each bit that is set in x (think of it as trading the current bit for all smaller ones).

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

I hope the pretests are strong, cuz I passed D mostly by guessing

→ Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

In today's contest I solved D but couldn't solve C.
In last div3 I solved E but couldn't solve B.
I don't know whats happening to me 😞

→ Reply
»
9 months ago, # |
  Vote: I like it -40 Vote: I do not like it

downvoted

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

got Accept D in the last 5 minutes. I regret not to use the initial idea (binary search) to solve this problem. My rank got down like 800 positions.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this solution fail on $th test case problem D

code
→ Reply
»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

3000+ solve on c and I am not one of those geniuses.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Am I the only one whose confused about the problem B's statement?

What most people have done is take the maximum Subarray Sum using Kadane's Algo in the beginning and then just keep on taking that subarray along with the present added element using operation.

My question is: Won't the subarray become bigger as we keep on adding elements and then the entire array would be taken at once? This, in my opinion, would WA every solution.

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

    i think taking whole array will reduce the max sum.

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

    because if you take full array sum would be lower than the smaller size one

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

      Leave it at this point. I don't even know what the hell I'm doing these days. Thanks for helping me out!

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

    Suppose at some moments, you choose to get a bigger array. Then the sum of elements which you extend will be larger than 0. However, if that happens, which means the initial subarray you choose by using Kadane algorithm is not the optimal one (since it will be better to extend that subarray with those elements).

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

    ...select any contiguous subarray of the array a (possibly empty) and insert the sum of this subarray anywhere in the array.. So, you will put that subarray sum in the main array and continue to do the same.

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

    no, I thought it was problem of maximize (sum mod 1e9+7), i.e maximize answer itself, not find the max sum then take mod 1e9+7.

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A -> Simple sorting and sum

B -> Kadanes algorithms and then fast exponentiation

C -> Binary search on answer

D -> could not do during the contest :(

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

    In B, O(k) is enough to pass, doesn't need fast exponentiation tho

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      but k = 2e5 , test_cases = 1e4

      total -> k*t = 2e9 , may pass may not pass, better to extra safe when exponentiation

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

        The sum of k over all test cases does not exceed 2e5

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

        It is guaranteed that the sum of the values of $$$n$$$ and $$$k$$$ for all test cases does not exceed $$$2⋅10^5$$$.

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

          I did not see that, I assumed they will try to fail on fast exponentiation.

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

          please help me understand this, k can be equal to 2.10^5 right, isnt that 2e9 complexity, isnt it guaranteed to TLE?

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

            Sum of all $$$k$$$ in all test cases together is limited to $$$2⋅10^5$$$

            If you will have in some test case $$$k = 2⋅10^5 - x$$$, in all other testcases $$$k$$$ can't be greater than $$$x$$$

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

              Sum of all k in all test cases together is limited to 2 * 10^5

              If thats the case what the complexity? I thought it should be strictly <= 10 power 8

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

                We are talking about calculating $$$2^k$$$ with a cycle instead of a binpow

                for (int i = 0; i < k; i++) {
    ans = ans * 2 % MOD;
}

                requires $$$sum(k)$$$ for all testcases

                ans = binpow(2, k, MOD);

                requires $$$sum(log2(k))$$$ for all testcases

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

        "It is guaranteed that the sum of the values of n and k for all test cases does not exceed 2*10^5."

        → Reply
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          please help me understand this, k can be equal to 2.10^5 right, isnt that 2e9 complexity, isnt it guaranteed to TLE?

          → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got in too late and couldn't even solve the first problem :(

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please look into my submission: submission thank you

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

    Your code does not sort the array anywhere hence median in cases with 3+ elements is wrong

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

      No no it does

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

        In the case for n=2, output should depend on wether array[0]==array[1]

        Hence, it gives wrong answer for testcase 1 1

        → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help why my code is not correct?? 


void solve(int testcase)
{
    int n,k;
    cin>>n>>k;
    v a(n);
    cin>>a;
    v pre(n+1, 0);
    for(int i=1;i<=n;i++){
        pre[i] = (pre[i-1]^a[i-1]);
    }
    int ans = 0;
    int curr = 0, ind = 0;
    for(int i=1;i<=n;i++){
        int xorr = (pre[n] ^ pre[i-1]);
        int temp = (pre[i-1] ^ pre[ind]);
        int left = (temp | curr);
        if((left|xorr) <= k){
            ans++;
            ind = i-1;
            curr = left;
        }
    }
    if(ans==0) cout<<-1<<endl;
    else cout<<ans<<endl;
}

I am checking at every index if the bitwise or of bitwise or of previously made sections and xor of right section is <=x, if yes I am incrementing the answer.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just blame it on Problem B and C, they're the brain-busting culprits of the day.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can question B be done without kadane's algo? something even simpler maybe?

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

    Since freedom of place of insertion is given, I guess the greedy approach (kadane) is very intuitive.

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

    I believe that Kadane's algorithm is the simplest way to solve this problem. All other approaches I can think of have higher complexity (from the O(n) Kadane algorithm to O(nlogn) D&C, Segment Tree, etc. and O(n^2) brute force) and, in fact, harder to understand and implement (even brute force)

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

      Ahhh i see, i was thinking maybe i am over complicating things by using kadanes for this question, turns out it was fine. thanks for the reply!

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

    you can do it using segment tree actually there is a part on edu section explaining it (its on segment tree part 1 — step2) but its not simple at all

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

    i solved it with o(n) dp u can check it outsolution

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

fuck me.

forgot to mod the maximum of the sum of contiguous subarrays and i had no clue about how it would cause wa on test 3.

not trying to complain here. it's just that next time you see me i be gray.

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved D in 15-20 minutes, spent a hour on C and still have no idea.I suck at Binary search.

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it -11 Vote: I do not like it

Problem ABC : Simple greedy.

Problem D : Bitmask, and it's a bit harder than my expectation.

Problem E : Ridiculous problem which can be placed at div.2 C in former contests.

Problem F : Just a trival DS problem.

So what's the cool point of this contest ??? The unreasonable difficulty distribution?

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

in E I boiled down the problem to the following expression

SUM(product(ai)) for all expressions such that we can reduce 1 from aj and add 1 to ai any number of times subject to constraints i<j. example

expression -> 4!2!2!3! we can have the following expressions 4!3!2!1! or 7!0!1!3! but cannot have 3!3!2!3!

how to solve it further.

PS: SUM(ai) is bounded by n (2*10^5)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do we have any graph solution for E?

→ Reply
»
9 months ago, # |
  Vote: I like it -112 Vote: I do not like it

That's probably the worst round I have participated in for a long time.

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

    why

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

    Because the answer is too obvious for you?

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

    please shut up, Huym_nik

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it -52 Vote: I do not like it

      The pain in your comment. Stop being envious of gifted people, it's not his fault that you're not gifted enough to be a red coder, please cry harder.

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

        He was saying that because Um_nik didn't give constructive feedback, or tell them how they can improve, he just said "trash round u suck", which is not a good thing.

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

        Gifted gray writes smart comment, omg!!!

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

    That's probably the worst comment I have read in for a long time.

    → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 2   Vote: I like it -13 Vote: I do not like it

    Sir, In this community everybody wants a Constructive feedback from a elite level/Rank holder like you. Then why are you promoting a Amazing level of Worst Feedback!

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Hope u are safe.

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

    Bro, I think you should practice a little bit. It's not you who are stupid, it's just that the tasks are difficult

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

-100 delta lets goo

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

    lezgoOOooO

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

    man i literally did the same error as you, just taking mod one more time would've been enough . That too so much time was left after B , failing system test is rough.

    → Reply
»
9 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Did not like it.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool contest! This is one of my worst performances recently :(, is F intended complexity n log n? I wrote a n log^2 n solution and TLE'd by a constant factor...

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

    My $$$n \log^2 n$$$ solution passed, although I think it is good constant factor because all I'm doing is adding and multiplying things (mostly adding though). I also included pragmas.

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

for problem F, i passed pretests, i can't pass pretest on system test, please rejudge, thank.

→ Reply
»
9 months ago, # |
  Vote: I like it +2 Vote: I do not like it

can anyone explain what's wrong with my code Solution

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

    As you can see on the checker's verdict: wrong answer 30th numbers differ — expected: '1000000004', found: '-3', you aren't handling negative numbers under modulo correctly.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D shares the approach with a problem on HDUOJ 2 weeks ago: (Chinese)

D. Legal Pairs

(I personally do not recommend this OJ from my experience in this contest: the statements were unclear and there had been serious queueing issues)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it's just for me? I just intuitively unclear on how applying Kadane's algorithm once is sufficient to get AC (problem B)

isn't max subarray sum varies every time we insert max subarray sum? because since max subarray sum become larger so that it may include elements on left and right side that were originally unable to include?

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

    Yes, it's not trivial to see, but also not difficult. I asked aryanc403 to elaborate on this in his stream. Timestamp

    The crucial idea is this. If the maximum sum subarray looks like

    _____S_____

    Then, all the extensions to the left or to the right have a net negative value. (Otherwise, you could use that extension to increase the sum).

    Now, suppose you place the incoming $$$S$$$ at a different position, like so

    _____S___S__

    Then, the max sum now is $$$S$$$ + middle + $$$S$$$. But we know that the middle extension will be negative, so it's better to keep it like so

    _____SS_____

    Even in this case, the maximum sum subarray would not contain any extensions to the left or right. Why?

    Hence, the maximum sum subarray is $$$2 \cdot S$$$.

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

    Hi, for problem B

    5 1 4 -2 8 -12 9

    In this test case, we add -12 in the first operation like this 4 -2 8 -12 -12 9 then sum will become -5 if we take the modulo of the -ve number then and would be 10^9+2 why the correct answer 17 here? please explain.

    → Reply
»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

how to solve E?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain why this solution does not TLE? I tried to hack it during the contest, but I couldn't. It uses a memset to reset memory in every test case, which is O(T*MAXSIZE). Does the compiler make some optimizations somehow?

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

Liked the round overall, D is an extremely nice problem, and i liked F too.

Nevertheless, pointing out some issues : BC are both boring and imo not correct for their spots. Tree dp + binary search, and kadane's algorithm really dont fit for the 2nd and 3rd easiest problems, and also are quite standard.

F TL??? the fastest solution for F is merely 2s..... and i had to do quite a bit of constant opt to fit the TL (tho i wasnt using pragmas, my fault ig). Please make TLs more lenient. I dont see why n needed to be so large. Is there some bad solution?

I liked E too, but i think the ideas behind it (and maybe even the problem) have occured before, because it looks standard, but if not, then nothing against it.

I would request round authors to kindly not put standard tasks in BC positions. Again, thanks for the round.

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

    It's not relevant but I love your previous round. Expecting your rounds in the future

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Why do people love calling every problem which is not ad-hoc — "standard"? ....

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

      Because the problems are standard....what should i call them instead?

      There are ofcourse non ad hoc problems which are not standard, but ad hoc problems by definition cannot be standard.

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

    in F we have $$$O(n \log^3 n)$$$ solution that works in about 6.5 seconds with proper optimization, so in order to cut it we made TL 6s and big $$$n$$$ and $$$q$$$ limit (to mention our $$$O(n \log^2 n)$$$ solution works in 1.6s without extra input optimizations and stuff like pragmas)

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

    I think a particular bad solution I think they wanted to weed out was solutions like this one: 252793752, which has complexity $$$\mathcal{O}(n \log^3 n)$$$, I think? Optimizing it was one of the harder and more beautiful parts for me.

    EDIT: bruh sniped

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I opened problem C, turned off my laptop and went to play basketball( Thanks for the contest! A and B were cool.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest with ultra cool tester...

→ Reply
»
9 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

nooo

→ Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The ratings are updated (lightning fast rating changes).

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

My F code took about 1s in the AtCoder code test, but it took 4s in the CF code test (almost maximum case).

Again, I think it's best not to hold a contest until C++ is completely fixed. I think it will surely be ruined due to constant factor in the near future.

→ Reply
»
9 months ago, # |
  Vote: I like it -39 Vote: I do not like it

Bad round. Don't ever cook again.

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

I tried solving D with a different approach, getting wrong on pretest 2 but cannot find the error.

My approach was to split the given array again and again till it satisfy the three conditions, while iterating through the array:

  1. XOR of all elements within a subarray should be less than x;
  2. XOR of all elements after the current index should be less than x;
  3. OR of all subarray and the subarray formed by other (remaining elements) should be less than x;

as soon as any subarray satisfy these condition i increase the counter and reset ans variable to 0.

my approach might be wrong, I will be glad if anyone points out my mistake

here is my code

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

    Bro you can send the code as a spoiler or as a link

    Upd:Thanks for listening me<3

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Spoiler
      → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Because it fills so many places

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is hacking phase open or it was withu=in contest??

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone help me? (I got in the contest very late dont judge pls)

A. Median of an Array:

Spoiler

Out first test: 1 2 1 3 1 1 1 3

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to solve slight variation of B, where instead of max(sum) modulo 1e9+7 for an answer, max(sum modulo 1e9+7) (way harder, i think)

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

    that would be orange problem or purple at least

    → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem F my $$$O(n \log^3 n)$$$ passes but $$$O(n \log^2 n)$$$ with unordered_map gets TL 7 🤡

252809693 and 252810082

can anyone explain why? is u_map constant that bad? I'm confused

(as a side note: choice of constraints in this problem is dumb, at least ML could've been 1024mb easily, but I would also decrease limit on $$$n$$$ and $$$q$$$ for $$$3 \cdot 10^5$$$ or something)

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why you didn't write what is permutation of length n in F's problem statement?

→ Reply
»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

problem C mega sexy

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I disabled by admin?

Yesterday I signed up for my codeforces account FromOceans, Then I participated in a contest (it was "Codeforces Round #936 (Div. 2)"), and the next day I logged in with my account only to see "disabled by admin"?? I didn't cheat in the game (I can publish vscode's timeline if I need to), nor did I do any DDos attacks on the website?

I don't know where I'm supposed to post, and the account I signed up to explain doesn't seem to be able to post, only comment under existing posts.

If there are any errors in English grammar, please point them out.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

C was great

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is this 252777884 Pq_oqtg_96VtCmVqT_tqwpfu

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I get WA on test 2 (problem C) but the test is too far for me to debug. Can anyone tell me the wrong case with this submission: https://codeforces.net/contest/1946/submission/253016060. Thank you

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

74TrAkToR About my problem of being rechecked in code https://codeforces.net/contest/1946/submission/252762903, most of which I have written in https://codeforces.net/contest/1914/submission/238131112, all the changes in which only add binary algorithm,In this problem, everyone is going to use this algorithm， this is just a coincidence, can you cancel my punishment

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am innocent but codeforces blame and they took the cheek of my rating and even did not count the contest. I just want to codeforces that : "Please! Give my rating back".

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

253431622 I met a very strange problem in B,I almost wrote the same code in the turoial,but I received many times wrong answers with the prompt the the solution is executed with error 'signed integer overflow',I used long long and it doesn't work,why?

→ Reply
»
8 months ago, # |
  Vote: I like it +5 Vote: I do not like it

It was an amazing round!!!

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

266117318 anyone plz tell where I am doin wrong

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this round changed my life!

big thanks to developers for this hamster combat

→ Reply