windva's blog

Codeforces Round 899 (Div. 2)
By windva, history, 15 months ago, In English

Hello, Codeforces!

I am pleased to invite you to participate in Codeforces Round 899 (Div. 2), which will be held on 25.09.2023 17:35 (Московское время).

All problems were written and prepared by me.

You will be given 5 problems, and one of them is divided into two subtasks. You will have 2 hours to solve them.

I would like to thank:

Score distribution: $$$500 - 1000 - 1500 - 2000 - (2000 + 2000)$$$

Good luck and enjoy the round!

UPD: Editorial is out.

UPD2: Congratulations to the winners!

Official Contestants

  1. Lycorisqwq
  2. zepto
  3. vjudge39
  4. Beelzebub_blue
  5. _t_W_

Official + Unofficial Contestants

  1. ksun48
  2. jiangly
  3. antontrygubO_o
  4. Sugar_fan
  5. KumaTachiRen
  • Vote: I like it
  • +524
  • Vote: I do not like it

Comments Comments (147)
| Write comment?
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

As a tester,problems are awesome.Hope you enjoy it :)

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

    We hope that the contestants will not spend a lot of time just reading the meaning of the questions.

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

As a tester, I did not know that the contest would be scheduled this early. Well, that was quite early, I guess.

Anyways, the problemset was enjoyable. Everyone, good luck on positive $$$\Delta$$$, and I hope you enjoy the contest as well (regardless of the $$$\Delta$$$).

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

As a tester, the last problem is the best problem I've seen recently. Good Luck and Have Fun!

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

As a tester, windva is handsome, so please participate.

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

    Will there be a problem based on cuteness of windva ? ( i'm not sure just guessing)

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

As a tester, I personally did like problem D and E. Hope you do not give up early and have a good result

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

As a participant, windva is god. :blobaww:

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

As a tester, I really enjoyed testing this contest.

The problems are creative, and solving these problems require a variety of approaches. Each problem has its unique style, and will broaden your perspective to the next level. Plus, they are fun to solve!

I saw windva putting a tremendous amount of effort and time to run this round. Moreover, windva is really cute, so please do consider participating actively.

Big thanks to windva, for creating this beautiful set, allowing me to test it, and for being cute.

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

This should be hackable, but I'm too lazy to write a testcase against it.
224983900

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

    Seems like you're in the wrong post XD

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

Wish me luck I hope this contest is another step into turning gren

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

We are ready

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

Good luck everyone! Hope you get your color-up!

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

I hope this will be an unrated contest for me :)

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

    How did you solved A,B,C,D all of them in just 1 minute in last educational round?

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

      I solved them in 38 minutes and submitted at once.

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

        Why?

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

          I'm guessing, to avoid losing rating, in case you can't solve enough tasks to get positive delta?

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

As a participant, windva is 大. very good at 三行詩. :blobaww:

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

2 out of 3!

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

Hope to solve at least one problem :)

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

Can anyone please explain why when I read input this way it is not accepted : 225037625

but when I read it this way it is accepted : 225042785

I thought both of them the same and I even runned debug with the first test case for the first submission and it just works like how I expected

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

    in first case you are breaking the for loop and not taking the complete input which gets carried on to the next tc

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

I'm kinda new here, is this round rated?

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

    All codeforces rounds are rated, unless said otherwise in the announcement.

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

Hope that I can solve problem D :)

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

I hope it will be easy to up rating

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

rated for the participants with rating lower than？

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

    The round is rated for participants of rating lower than 2100(Master).

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

how do I become a tester for some codeforces round?

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

    I invited some of my acquaintances to test the round, and the coordinator invited in more testers. I don't know exactly from what route he invited them.

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

Guys I won't be able to participate if I just didn't will that effect anything after I registered?

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

    If you don't submit anything during the contest, then your rating won't change. You can cancel your registration anytime before the contest starts tho

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

I hope everyone reaches their goal <3

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

I couldn't solve C, should I commit suicide?

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

    Lol, thought of killing yourself over a petty puzzle.

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

    Was C really that strikable. it would not have striked even if i had given a month to it

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

Why dfs in D is so slow. I got TL int $$$O(30 \cdot n)$$$, changed $$$30$$$ to $$$21$$$ and it's still $$$2.7$$$ seconds...

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

    Intended solution probably solves all bits at the same time

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

      Oh, it's interesting! I know only solution for each bit separately.

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

I am going to break my 1666 rating :))

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

Any hints for C ?

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

    If you fix the leftmost element which you will remove, then what would be the answer?

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

      what an elegant solution you've coded!

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

      Hmm, but can't you then proceed to remove even more elements down the line? Or would that not be beneficial since there's no use in flipping the parity twice?

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

    Work backwards. Start from $$$i=n-1, ..., 0$$$. There are 4 cases: The $$$i$$$ location is odd or negative, and for each, it can be $$$\geq 0$$$ and $$$<0$$$. For each case, you can do a greedy decision.

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

    you can do DP. Check my solution.

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

    You can get answer by checking first two element of array(obviously n>=2).

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

Why the skill difference between D and E so high everytime. btw how to approach E anyone?

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

This second question that came, well in the third test case why was the output 6 and not 7? You could include 1 too in the set.

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

    But then the set would contain everything, which isn't allowed.

    "Find the maximum number of elements in an attainable $$$S$$$ such that $$$S \ne S_1 \cup S_2 \cup \dots \cup S_n$$$."

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

What is the logic for B? Thanks.

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

    Store all element in map that represent union of all, after that for each element of map see which sets include that element and remove that set. which map element results in lowest removal is answer. here's my solution --> https://mirror.codeforces.com/contest/1882/submission/225124593

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

      Can you please explain in more detail?

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

        mp is storing union of all(you can use set too) after that i am seeing that how many element will remain if i want to remove all sets which contain that element. which element removal gives most element remain is answer , temp map(m) is storing the current union.

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

    You have to exclude at least one Element from the answer, so fix this element and add all the sets that doesn't contains it.

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

How do you solve D? (Hints)

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

    tree dp / rerooting

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

      I can solve it with tree DP easily for one root, but what is this rerooting trick you mention? Any links?

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

        If you know $$$dp[u]$$$ and there is an edge $$$(u,v)$$$, you can find $$$dp[v]$$$ in $$$O(1)$$$ https://usaco.guide/gold/all-roots?lang=cpp

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

        Think about how dp values change if you change the root to an adjacent vertex (old and new roots are connected by an edge). You'll notice that only the dp values of the old and new roots change, and this change can be calculated in $$$O(1)$$$. Now, you can just do a simple dfs traversal of the tree and always move the root when going up or down. All vertices will be the root at least once during this, and you can store those answers in a separate array.

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

        If you have the formulae to calculate dp for any parent from it's children then you can also use the same formulae to reroot the tree to the child from it's parent. Keep doing it recursively in dfs and calculate answer for every node

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

A ok

B Unimaginably bad

C Unimaginably bad

D Unimaginably bad

E1 Unimaginably bad

E2 out of my skill no comments

total: 6.9/100 (fail)

abort_dodger_3000

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 5   Vote: I like it +26 Vote: I do not like it

    For me, it's like

    A ok

    B out of my skill no comments

    C out of my skill no comments

    D out of my skill no comments

    E1 out of my skill no comments

    E2 out of my skill no comments

    total: 93.39/100

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

Quite similar problem to problem D : 1187E - Покраска дерева

It's basically the same idea

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

B's pretest were pretty weak, probably gonna fst a lot

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

Why TLE? It is $$$O(n)$$$

Submission: 225143030

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

    It seems like O(20n). We allowed fast O(20n) solution, but the intended solution is actually O(n) and not guarantee slow O(20n) solution to get AC

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

      Are $$$3$$$ seconds not enough when $$$n = 2 \cdot 10^5$$$? It is C++!

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

      I don't think it really makes sense to allow a slower solution only if it's implemented efficiently. I think you should've either allowed the slower $$$O(20n)$$$ to pass easily or changed to like $$$a_i < 2^{60}$$$ and a 2 second TL to only allow the fast $$$O(n)$$$.

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

        I guess it was quite hard because diverse languages (ex. Kotlin, python) have to be considered. We had to guarantee O(n) solution implemented by Kotlin to get AC

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

        I agree with your point.

        However, we had to consider slow languages, so had to set TL at least 3s. And due to this, we intended to pass O(20n) instead, because we thought it would be impossible to block O(nloga) in TL 3s even if we increase the constraints. In fact, there were O(20n) codes which worked in nearly 1 sec so I thought it wouldn't depend on the subtle difference in code's efficiency.

        Thanks for your feedback :)

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

          Usually, a constant of $$$20$$$ is too small to distinguish between two solutions. So it was the right decision not to block $$$20n$$$. But maybe it would be better to increase the TL? I don't think it's easy to squeeze $$$O(n^2)$$$ into this problem in any reasonable time, even on C++.

          By the way, thanks for problem C, I really enjoyed it!

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

    You can check my O(20n) solution. which works at 1.3-1.4 seconds. 225156423

    → Reply
»
15 months ago, # |
← Rev. 12   Vote: I like it +51 Vote: I do not like it

A: We can solve by greedy: Let b[i] be the minimum it can be, which means, if a[i]==b[i-1]+1 then b[i]=b[i-1]+2, otherwise b[i]=b[i-1]+1.

B: For each $$$t \in \bigcup_{i=1}^{n} S_i$$$, assume $$$t \notin S$$$, we can let $$$S = \bigcup_{t \notin S_i}^{} S_i$$$, and take it as a candidate of answer.

C: Observe that if we removed the i-th card, then for j>i we can get max(0, a[j]) score by appropriate order of operations. Assume the most top card we removed is i0-th card, then the answer will be a[i0]*[i0%2==1] + sum(j>i0)(max(0, a[j])).

details

D: When u is the root, it's useless to do operation on u, and for each other node v, we need to cost (a[parent[v]]^a[v])*size[v] to make a[parent[v]]==a[v]. Therefore, if we let 1 be the initial root of the tree, and u is the parent of v when root is 1, then node v will contribute (a[u]^a[v])*(n-size[v]) to the answer of nodes in subtree of v, and contribute (a[u]^a[v])*size[v] to the answer of other nodes.

E1: We can use 3 operations to swap two numbers in the permutation: [I]*s*[II]t[III] --> [II]*t*[III]s[I] --> [III]*s*[I]t[II] --> [I]t[II]s[III], and do 2 opartions on 1, n will cause no change. Therefore, we can build operation sequences for p[i] and q[i] separately, and if the parity of lengths of them is the same, we can fill (1, n) to operation sequence of p[i] if it's shorter, or fill (1, m) to operation sequence of q[i]. Otherwise, if n is odd, we can add n operations on 1 for p[i], similar for m is odd. If both n and m are even, the answer doesn't exist.

Why answer doesn't exist
→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How did you arrive at the answer for D?

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

      since doing xor on a whole subtree is kind of like doing suffix xor on an array, you can consider do something like difference array, that is, make every edge $$$(u, v)$$$ have a weight of $$$w[u] \text{^} w[v]$$$, then the weight of $$$v$$$ is indeed the xor of path from root to $$$v$$$(except the root, but it is not important), and the problem become "Make all edge have weight $$$0$$$, in one operation you can make an edge's weight xor with $$$c$$$", then it is obvious that xor edge with it's weight is optimal.

      → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    When u is the root,it's useless to do operation on u

    Can you explain why?

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

      My understanding was as follows: If you XOR the root and a certain set of bits get flipped in root's value, then those bits will get flipped for the entire subtree (since operation is on the entire subtree, not just root). So, essentially the problem remains identical just with the flipped bits i.e. you want to match those bits in the root's value with values in its subtree using the XOR operation on the subtree.

      Consider an example with only 1-bit numbers: If root's value is 1. And its subtree has node1=0, node2=1, node3=0, node4=0, node5=1. Then, if you apply operation on the subtree rooted at the root itself, these numbers will become root=0 and subtree will have node1=1, node2=0, node3=1, node4=1, node5=0. Clearly, the nodes in subtree which had different value compared to root still remained the same before and after the operation.

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

    For D[problem:1882D], the conclusion that it is useless to do operation on the root (to minimise cost) seems obvious.

    However, in your statement/solution, are you assuming that for a node v to become same value as root, the value of node (v) has to (at some point) become equal to the original value of its immediate parent after a sequence of operations? If so, how can we prove it for optimal cost?

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

Tried DFS and Rerooting for each bit in D, got TLE, shouldn't 20 * n pass?

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

    No need to do it for each bit. If you want to make a whole subtree equal then you need to make all children of the root equal to root otherwise its not possible. There is no way we can change the root value to be equal to the value of the child without changing the child.

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

    Please take a look at this comment

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

The contest is maybe very good But it DID NOT FIT ME. :( problem D is DP. I am not good at DP at all:( especially on tree :(:( E1 WA#10, mistake, didn't pass pretest until contest over. :(

problem C is fun. feel good over A B C.

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

    How did you reach purple without a stronghold on dp?

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

      Dp on trees is more annoying than normal dp. I struggled with the code a bit too

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

For Problem C, DP was way straight forward than the greedy method for me. DP Solution

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

    Thanks for this, I really need to get better at dp lol-

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

    This is the method I used as well in testing. In fact I did not know there is a greedy solution until today.

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

    I tried the same approach but didn't bass the example.

    It's much easier to think about Dp solution for problems like this than to think about a greedy solution -$$$ at $$$ $$$least$$$ $$$for$$$ $$$me$$$-.

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

    In your solution, can you explain the calc(v,i+2,1)+v[i] case when the parity is odd?. I was thinking on the exact same grounds but cannot understand why this is needed.

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

      Let's say we are on an odd position i now. If we take this value right now and if there exists another value at position i+2 it will become even after the operation.

      Example: [1,-5,2,-3,5]

      After taking the element at position 1: [1,-5,2,-3,5] > [-5,2,-3,5]

      Here you can see that the value 2's position has changed from being ODD to Even.

      But if we take the element at position 3 first: [1,-5,2,-3,5] > [1,-5,-3,5]

      As you can see the position of the element 1 has not changed from being ODD to Even. So we can take this element even after taking the 3rd element.

      So, for that it is optimal to take the value of (i+2)th element before taking ith element. So by calc(v,i+2,1), I am saying that "I will take the ith value after taking the (i+2)th value."

      I hope it clears up the idea behind it.

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

        Hi bro, still did not understand this line - ->So by calc(v,i+2,1), I am saying that "I will take the ith value after taking the (i+2)th value

        why we need to check this for only i and i+2th element. like example 1 -2 -2 -2 4 -2 -2. Here we can take 4 and then 1 as well which is not at position i and i+2, How is this case handled?

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

          It is a recursive function. And it has 3 branches for odd positions.

          • (1) Take the current value and make the next value ODD and calculate from there.

          • (2) Do not take the current value and calculate from the next position.

          • (3) First calculate from the i+2 th value, then take the current value. So, making no changes to the positions of the next elements.

          And it has 2 branches for the even positions:

          • (4) Remove the current value from the array and make the next position even. And calculate from there.

          • (5) Do nothing to the current value and calculate from the next position which is an ODD position.

          So for the case you have mentioned we follow these sequences:

          3->2->5->1

          The numbers represent the type of operation at each time stamp.

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

it was a very good contest and I do learn a new thing from D problem thank you Windva for writing these Masterpiece

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

Why multitest in D???

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

The system tests for E1 are weak. A test with two decreasing permutations of length 2500 causes my solution to TLE. I'm not sure why some tests were included for E2 but excluded for E1, since I'm pretty sure test 87 from E2 would have caused the same TLE on E1 (the code that causes the TLE is unchanged between my submissions). This also seems like the most intuitively "hard" case, so I'm surprised it wasn't included early on among the pretests for both versions of the problem.

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

D is too similar with Leetcode 834. It is possible to "transform" 834's solution to D's solution by just adding weight of the egdes by a[u]^a[v]

Leetcode 834 solution (in Chinese version) :https://leetcode.cn/problems/sum-of-distances-in-tree/solutions/

My solution: https://mirror.codeforces.com/contest/1882/submission/225158821

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

    To have that transformation you need the main idea anyway, so I don't think this is a major issue.

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

C was too much ad hoc for me, fuc*** my whole contest :(, D was straight kinda straight forward, submitted just after the contest was over :(

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

Problem B Is too much for div2B

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

Video Editorial For Problem A,B,C,D

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

My DP solution for C is not working. Can anyone plzz check?

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

Super Fast Delta Delivery!

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

In problem C i got AC but i don't know if my idea is good or just lucky

practically i maintain a multiset where i keep the values that i took

a priority queue where i keep the value i didnt take but are on odd positions

a cnt where i mantain the values i didnt take on even positions

i have a value tura that means if i have to look on even or odd positions , because i deleted a even number or odd number of numbers before

so practically when i am on a odd position i see if its > 0

if it is i take it and tura becomes 1 -tura

if i am on a even position i see if i took a position before if i did and this one is bigger than 0 i take this position as odd also

if i didnt i will see if i have cnt > 0 if yes it means i can take it if its bigger than 0

then if i cant do that either i see if v [ poz ] > min ( multiset.begin() , priority_queue.top())

if yes i take it and i give up a element to the left

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

Can someone pls explain this solution by Jiangly for problem B? https://mirror.codeforces.com/contest/1882/submission/225097723

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

    I hope this commented code helps:

    225190010

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

    The variable Or is used to store the union of all the sets. We enumerate the number $$$x$$$ to erase for the answer. Then it's clear that all sets containing $$$x$$$ should not be selected, and we can select all other sets . So we can know the largest union set to get which doesn't contains $$$x$$$.

    For code implement, uses bitmask to record each set, and some bit operators to check the conditions above.

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

Since October 2022, I have participated in 3 CF Rounds, all in May, this year. After that time this one was the first. This year I participated in the IMO and IOI. Hence, during the last few months, I was training for both IMO and IOI. I started training for the IOI after the IMO. During that period I have not participated in any CF Round. I was virtually participating in different 5-hour IOI-style contests, mostly IOI. To understand the problem statements clearly, I read them slowly. And now I think I am not in my best form of CF-style contests. Fortunately, I managed to solve A, B, C, D and to write the code of E. After I finished coding, then finding and fixing bugs, around a minute was remaining for the contest to end, so I quickly tested my code on the test cases available in the statement and sent the code. But… I got WA on TEST 1. What?… and after a few seconds of checking my code, I found the following:

BUG

I wrote this to locally debug my code to find bugs, and forgot to change it into a comment… I quickly fixed that, but it was already late for a minute… The contest was over… During the system testing I hoped that my idea of the problem was wrong, or that there was another bug in the code (so that the lateness of 1 minute wouldn't change anything), but, fortunately or unfortunately, after the end of the system testing, I sent the fixed code and got AC… WOW… I thought I would be more relaxed should I get WA.

P. S. By the way, the Honourable Mention from the IMO and Bronze medal from the IOI, which I earned, made me feel happy that a story like this happened during the regular round but not the official contest.

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

Editorial please!

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

In problem D, how to prove that in the optimal cost solution, all values in the subtree of a node v should become equal to the original value of the node v itself after certain operations?

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

    Assume you would make an operation on the node $$$v$$$. Then all the nodes in the whole tree will be $$$xor$$$-ed. If you only look at one bit position, that means either we $$$xor$$$-ed with $$$0$$$, then nothing changes. Or we $$$xor$$$-ed with $$$1$$$, then all bits $$$1$$$ changed to $$$0$$$-s and vice versa, so the differences are still the same. We did not get closer to our goal. So using an operation on the root is futile. This means all numbers will be equal to the number in the root.

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

I'm getting WA on test 5 E1, it says:

Checker Log

wrong answer incorrect A

what does that mean?

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

Thank you to the author and helpers for the contest! I liked all the problems except D, which I felt was standard and boring, and E2, which I can't solve. C and E1 in particular I like a lot. Thanks again :)

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

Thnx

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

DP Solution for C, considering

dp[i][0][0] => not removing the ith index as an even index from the start,

dp[i][0][1] => not removing the ith index as an odd index from the start,

dp[i][1][0] => removing the ith index as an even index from the start,

dp[i][1][1] => removing the ith index as an odd index from the start,

dp[0][0][1] = max(0ll,a[0]);dp[0][1][1] = a[0];

for(i=1;i<n;i++){
        ll x,y ;
        x = dp[i-1][0][0]+max(0ll,a[i]);
        y = dp[i-1][1][1]+max(0ll,a[i]);
        dp[i][0][1] = max(x,y);
        x = dp[i-1][0][1];
        y = dp[i-1][1][0];
        dp[i][0][0] = max(x,y);
        x = dp[i-1][1][1]+a[i];
        y = dp[i-1][0][0]+a[i];
        dp[i][1][1] = max(x,y);
        x = dp[i-1][1][0];
        y = dp[i-1][0][1];
        dp[i][1][0] = max(x,y);
}

submission — 225203776

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

    hi...why are you adding max(0,a[i]) for computing dp[i][0][1]

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

      Because initially left positive integer at odd position can be collected afterwards performing necessary operations on right

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

can anyone explain B to me??

I understood that we need to opt out the set with least no of unique elements wrt other sets,but how to implement this.

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

    For me I just used the fact that all elements <= 50 so I tried union of every set not containing X for every X in [1, 50], if that union if not the same as union of every set then it works.

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

Hi, can someone tell me why the following code gives me a runtime error (I ran it in an IDE outside of Codeforces and no RTE was picked up). Thanks.


int main(){
	ll t;
	cin >> t;
	while(t--) {
	    ll n;
	    cin >> n;
	    vector<vector<ll>> s(n);
	    vector<ll> freq(50),k(n);
	    ll maxi=0,m=0;
	    for (ll i=1;i<=50;i++) {
	        freq[i]=0;
	    }
	    for (ll i=0;i<n;i++) {
	        cin >> k[i];
	        vector<ll> a(50);
	        for (ll i=1;i<=50;i++) {
	            a[i]=0;
	        }
	        for (ll j=0;j<k[i];j++) {
	            ll b;
	            cin >> b;
	            a[b]=1,freq[b]+=1;
	            if (freq[b]==1) {
	                m+=1;            }
	        }
	        s[i]=a;
	    }
	    for (ll i=1;i<=50;i++) {
	        vector<ll> freqnew=freq;
	        for (ll j=0;j<n;j++) {
	            vector<ll> c=s[j];
	            if (c[i]==1) {
	                for (ll l=1;l<=50;l++) {
	                    freqnew[l]-=c[l];
	                }
	            }
	        }
	        ll num=0;
	        for (ll i=1;i<=50;i++) {
	            if (freqnew[i]>0) {
	                num+=1;
	            }
	        }
	        if (num<m) {
	            maxi=max(num,maxi);
	        }
	    }
	    cout << maxi << endl;
	}
	return 0;
}
→ Reply
»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Really fun round ngl

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

I and wxy_is_a_dog/2255153050 had studyed the Replacing DP，and we studyed https://www.cnblogs.com/wlzhouzhuan/p/12643056.html this blog.So our solutions have something in same by accident.

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

I got a message stating that my solution to the problem 1882C - Карточная игра coincides with qilby's submission (both submissions: 225107761, 225130187). The submissions are very similar (and what's even funnier, our nicks are also pretty similar), but the coincidence happened only due to how short the solution to that problem was (all variable names used there are pretty standard like $$$s$$$ for sum and $$$ans$$$ for answer or $$$ll$$$ for long long type). Moreover, I've submitted the solution $$$\approx$$$ 30 mins after De_Coder so it would make no sense to take that long if I had been cheating. The solution didn't use any data structures/advanced algorithms hence I didn't use any code written before the contest.

MikeMirzayanov

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

For Question B, Set and Union. Test Case 3.

s2 U s3 U s5 = {1,3,5,6,8,9,10} but the test case missed 1. i.e s2 U s3 U s5 = {3,5,6,8,9,10}. Why is 1 missing for test case 3?

The answer for test case 3 should be 7 right?

→ Reply