Igor_Parfenov's blog

Codeforces Round 992 (Div.2)
By Igor_Parfenov, history, 11 days ago, In English

Hello!

On Dec/08/2024 17:35 (Moscow time) we will host Codeforces Round 992 (Div. 2).

The problems were written and prepared by Igor_Parfenov.

I would like to thank everyone who made this round possible:

This round will be rated for participants with rating lower than 2100.

You will have 2 hours to solve 6 problems.

Score distribution: 500 — 1000 — 1500 — 2000 — 2250 — 2750.

Good luck!

UPD: Editorial

UPD: Congratulations to the Winners!

Div.2:

  1. daniel6202

  2. younesg

  3. houseof

  4. HUST_USELESS

  5. FatihCihan

Div.1 + Div.2:

  1. jiangly

  2. maspy

  3. Rubikun

  4. BurnedChicken

  5. neal

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

»
11 days ago, # |
  Vote: I like it +60 Vote: I do not like it

Shortest description for a Codeforce Round I've ever seen. Good luck all :)

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

as a non-tester i love playing undertale

→ Reply
»
11 days ago, # |
  Vote: I like it -25 Vote: I do not like it

Hope B will not be a Game theory

→ Reply
»
11 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Hopefully, the problem statements will be short and precise just like the announcement!

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

    maybe the keyboards battery died after those lengthy problem statements so now we are left with this short description

    → Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you explain to me why does everyone care about score distribution? I don't get it. Does it correlate with the complexity of the problems? And if so, in what way?

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

    Yeah higher the jump in between the problems higher is the difficulty change

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

      So am i right that this contest is going to have a significant jump between first 3 problems? Cause it's much more often them to be like 500 750 1250.

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

        You can expect so. Usually a distribution of 500-1000-1500 means the problems are rated around 800 — (1000-1200) — 1500 respectively. There are exceptions of course (the last two div2s having 800-900-1200 and 800-900-1300 for example). In fact, a 1400-rated problem B in one of the recent div2s only granted 1000 points.

        I think that 500 1000 1500 is more common than 500 750 1250 though.

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

I hope to become Expert after this round 0 ^ 0

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

My first unrated Div.2

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

good luck

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

Best of luck to all participants—let's enjoy solving and aim for new personal bests! ᓚᘏᗢ

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

everybody best of luck give your 100% with best wishes

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I want a rating boost, so should i go with solving problemB first and then problem A?

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

xD

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Expecting increase in rating

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

As a tester, I hope you get a lot of green in this contest.

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    As a tester, the contest is a friend.

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

    which includes green stocks?
    P.S: it is only a joke. I never bought any stocks.

    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

THANK YOU! VERY MUCH :)

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

it will be the rated contest number 100 for me <3

I hope to perform well in this contest ^_^

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping I could get to expert

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope you all get greens

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Normalize writing shortest description for every codeforces rounds.

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully I wont choke on A this time :)

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

constructforces

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

i feel so stupid failing c

→ Reply
»
10 days ago, # |
  Vote: I like it -16 Vote: I do not like it

Problem C type of problems are the worst.

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

patternforces

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

C is going straight to my suicide note.

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

Is F on Burnside's lemma?

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain to me the idea behind b i feel too dumb tbh...

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

    the optimal indicies for the first operation are 1, 4, 10, 22, ....

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

      yea.. i thought it would be something like this but i don't understand why

      wont the (r-l+1)/2 > the sum of 1s ?

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

        after choosing index 10, then we have 10 ones [1, .., 10], and we choose 22, then we have 11 ones between 1 and 22, then all between will be ones also, and so on ...

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

    If the count of 1 in an array of length n is >= n / 2, then it can be made an array consisting of all ones using second operation. Now, to perform second operation, the endpoints of the subarray must be equal to 1. Hence, we can start constructing the answer from the smallest most optimal subarray, which is 1 0 0 1. Now, after applying second operation, it would become 1 1 1 1. Again, to fill next 0's, we can add another 1 after (k + 1) zeroes where k is the current subarray length which is all 1. The array will become 1 1 1 1 0 0 0 0 0 1, notice that count of 1 is still >= n / 2. This way, you can bruteforce your answer for any n.

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

      oh ty now i understand

      i forgot to count the 1 after (k+1) to the count so range was always shorter

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

      why are we putting 1 at 10th place since ceil((10-4+1)/2)==4 which would be less than the sum of a4+a5...+a10 which would be 2,

      Thus we will never be able to perform 2nd operation between 4th and 10th index as 4>2

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

        After we make 4th position 1, we can do second operation and we have something like

        1 1 1 1 0 0 0 0 0 0

        So now you see we can make the 10th index as 1

        as (10-1+1)/2 == 5

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

    a bit constructive first paint the cell 1 then check how much i can cover by painting ith cell that will satisfy l=1,r= ith cell ,then (i-1+1)/2

    a pattern like 2*(curr+1) will be formed please write it on pen paper you will surely get it

    my code : https://codeforces.net/contest/2040/submission/295579978

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

https://codeforces.net/contest/513/problem/B2

lol

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

    This explains so many submissions on C, despite its difficulty being near 1800.

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

    How did you find this problem?

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

    Oh no, its the exact same task !! Authors please be careful from next time bcz many people might have known this so its a bit unfair for us.

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

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

    Authors: solve the same problem for multiple testcases. lol

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

D is serious?

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to D?

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

    Keep track of a value you will assign to the nodes, starting at 1. DFS and use precalculated sieve to determine when a parent-child value difference is prime, in which case increment the value by 1 until it is no longer prime. The number of increases is upper bounded by about n/2, which ensures the value never exceeds 2n.

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

      Guessed it would be solved like this. Thanks!

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

    Just fill everything in dfs with odd numbers starting from 1. When you fill children of some node u, skip odd number x + 2, where x is the parent's odd number. In the end you'll have at most one unfilled node, so just fill it with even number x + 1, where x is the parent's number. It works because the difference of two non-adjacent odd numbers is an even number greater than 2.

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

    Another solution: solve in dfs order for subtrees first, then when combining add 1 to the whole first subtree and starting from the second subtree add double the size of all previously considered subtrees plus 2 to the whole now considered subtree. After the first dfs, the final answer will be obtained by going to the leaves from the root and adding all calculated values plus 1.

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

C I gave up on observations and just generated $$$n=8$$$ permutations and found patterns

→ Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    that's the first thing to do for permutation problems

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

    Can you explain further? Did you do this on pen and paper (seems like a daunting task), and if you did this via code — did you calculate S(P) for all of them manually?

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

      Yes, I did this in code and calculated S(P). Python has many nice features that make this pretty straightforward and fast. You can use itertools to generate all the permutations easily and S(P) isn't too hard to code.

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

    what was the pattern I sill didn't get it?

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

      Get binary representation of $$$k - 1$$$ with the number of lead zeroes that makes the binary string's length $$$n-1$$$. Then iterate over the bits. If $$$i$$$th bit (1-indexed) is $$$1$$$, then add $$$i$$$ to the tail of the permutation. Otherwise add $$$i$$$ to the head of permutation. Then there is only one number left, $$$n$$$, which should fill the only index not yet considered.

      → Reply
  • »
    »
    10 days ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    I started by thinking of maximising sum of intervals of each length. Realised you can't really get better than, say, for n = 5, for intervals of length 2 you can get at best 1 + 2 + 3 + 4. Then for length 3 you can get at best 1 + 2 + 3. And so on. And eventually realised that every piece besides the biggest one has to have as neighbors both a bigger and a smaller than it (considering the edges of the permutation to be 0). So essentially this is like going through the numbers in order and putting either smallest position still possible either biggest. So, like this, for example: n = 4

    0  0
0 1    0
0 1   2 0
0 1   3 2 0
0 1 4 3 2 0 (this last one will always be the same, whether you try putting it on the left or right)

    This can also be written then as either putting left or right. So for the given example it's L R R (you put 1 to the left, 2 and 3 to the right, 4 in what remains). And then finally when I started listing how all combinations of L and R would look I realised that this if you put the combinations in order, their results will literally be in the same order lexicographically, too (if you consider R bigger than L).

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

    Same. I lost track with pen and paper at $$$n = 5$$$ so I just coded up a brute force construction method and then it's pattern seeking from there.

    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the editorial be published?

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

mathforces

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

Today I learned that 2 is a prime number :(

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C was too tough for pupil and specalist Guys.We cant even fight to solve C. Totally Disappointed

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

    As a pupil, I did solve C

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

      you've done a great job.

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

      But an average pupil/specialist might not.

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

        If average pupils solved C, I don't think they would be pupil

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

          That C was way too hard for an average C. An average C is solvable for an average pupil.

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

            I agree on it being harder, but I think people solving ABC are specialist, not pupil.

            → Reply
  • »
    »
    10 days ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Nah, it's just a find-a-pattern problem, not much knowledge is required to solve it.

    → Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

C is painful for me

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

No idea how to solve C :(

→ Reply
  • »
    »
    10 days ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    Do a brute force to find the optimal value sum first and then see all the permutations that give the result for some small $$$n$$$ like $$$7$$$. Try to see the pattern.

    Spoiler
    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I honestly dont get the point of questions like C.

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

    I liked C but it might have been harder or just as hard as D, which is not very cool. Also someone said they found it somewhere on codeforces, so, it shouldn't have been in the contest.

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

nvm

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I brute forced and saw the pattern for C, but I couldn't figure out how to implement it for 90 mins, got really frustrated by the end of the round

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

    same, couldnt figure out how to do it without computing 2^n

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

      2^n gets really big really quickly, so you only need to do it for small n (Like <= 50). Then the large case is trivial, because it will be bigger than k.

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

    same bro despite of finding the pattern it is difficult to implement it Does anyone knows how to solve such type of problems please explain , it is much needed ?? Please

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

      you can literally solve this particular problem by making observations and "wishful thinking". See my comment above. But yeah, running bruteforce and figuring out why it looks like that might be faster than what I did. Regardless, realising when to call it quits and run a bruteforce and pattern match is still a skill, isn't it?

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

    same :(

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

help in d please

My thought process : choose 4 as diff and then choosing adjacent node

one will act as root and all nodes in it subtree will be 1 given 1 and increment of 4 , other with 2 and it increments

counter case : for star graphs case i can take other additions also like 1 and 7 for additional nodes,

can't implement it so need help

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

    That would be quite weird to try to implement, so instead of using 4 as the smallest non-prime, use 1 and see where that gets you. That's how I did it.

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

    tried implementing the same

    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

These ppl didnt mention the function in B was ceil, and not floor, and spend half an hour on that lmao, next time hopefully they write its ceil function

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

    The one that is closed on top ($$$\lceil x \rceil$$$) is ceil, the one with the closing under it ($$$\lfloor x \rfloor$$$) is floor.

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

    $$$ceil(x) = \lceil{x}\rceil$$$

    $$$floor(x) = \lfloor{x}\rfloor$$$

    $$$round(x) = \lfloor{x}\rceil$$$

    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C was way too tough ig

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I wasted so much time rabbit-holing in B... so I did D and then came back to B, spent another 20 minutes, and then finally saw the easy way to do it smh.

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

is there anyone found $$$D$$$ was easier than $$$C$$$ ?

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

    really thought so

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

    i found it easier to solve, but much much harder to prove

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

    can u tell why am i getting tle?

    d

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

      I think your problem is with this line

      while (it != st.end() && check.find(*it + base) != check.end()) it++;

      try to optimize your approach to find this value in $$$O(log(n))$$$ instead of $$$O(n * log(n))$$$

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

    i found E < C < D

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

why is d getting tle d

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

This was not competitive programming, this was competitive math

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

Yeah, it seems to be a very fair thing to not tell explicitly that you are using ceil function instead of floor and then don't even add testcases to make sure it doesn't happen. There's barely a difference between ceil and floor brackets and anyone can genuinely miss it.

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

guessforces + how on earth none of testers noticed about C

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

dear problem setter, please never make problem like C again, never.

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

make this unrated wtf

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

Am I the only person who really liked C? Only reason I found out it was hated was by looking in the comments

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

    It is cool but it appeared before.

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

    pretty sure your code is copy pasted. A lot of newbies and pupils have the exact same code as you. Its an already existing question.

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

      1) If I copy and pasted the code, why would I have gotten a WA for my first submission

      2) I do that in my submissions in-contest, eg https://codeforces.net/contest/2037/submission/291988558

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

        And since you decided to change your comment's meaning, point 1 still stands. I've never seen the problem before, and I swear on that (for a bit of extra proof, here's the bruteforce solution I wrote in contest, Ik it's not perfect proof, since I could have written it after the contest, but here)

        import itertools
def test(arr):
    total = 0
    for i in range(len(arr)):
        mini = arr[i]
        for j in range(i, len(arr)):
            mini = min(mini, arr[j])
            total += mini
    return total

n = 9
k = 33
print(test([4, 3, 5, 2, 1]))
total_combos = itertools.permutations(range(1, n+1), n)
maxi = test(list(range(1, n+1)))
print(n, k)
print([str(x) for x in total_combos if test(list(x)) == maxi][k-1])
        → Reply
    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Well there are some coders who name variables very explicitly, like neal, for example. (I am replying to the first version of your comment)

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

d is too hard for me :(

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

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

    F is combinatorics, not constructive

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

      The "F" in the pic doesn't seem to reference a problem.

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

    Actually one of your homies loves constructive problems

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

I'm sure for many, the D task was an attempt to just stuff something stupid without even trying to prove it. It's a pity that I only managed to do it after the end of the round. Specifically, C was too heavy for me.

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C binary search solution: 295643209

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

I cheezed D with a randomised solution. Basically, I guessed that the ratio of number of "unblocked" values to total values is never much lower than 1/2

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

People fighting over problem C, and my stupid brain thinking it's a floor operation in problem B.

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Never let this author cook again.

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

Who and for what reason decided to add -1 in Problem D?

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

    That's quite common as to not spoil the solution. Alternatively you have to guarantee that solution always exists, but that is not always obvious.

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

      If they wanted to make the problem better, they could have added that maximum node should be as small as possible.

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

        I think the problem is good as it is. How would you solve the modification you proposed?

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

          Not sure, But I would Try to change my initial code which got TLE on 24 test, were I find the diameter of the tree fill with numbers which have difference of one and after that go to subtrees by increasing the number with smalles composite difference and do the same in there, but not sure how to implement it yet to pass in time.

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

[For problem C] I am trying to generate the permutation according to the bitwise representation of k. Could anyone please see what's the error?

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--) {
        int n, flag = 0;
        long long int k;
        cin>>n>>k;
        vector<int> a(n, 0);
        if((n<=60) && k>pow(2,n-1)) {
            cout<<"-1\n";
        }
        else {
            int L=0, R=n-1, shift=n-2, value =1;
            while(L<=R) {
                if(((k-1)>>shift)&1) {
                    a[R] = value;
                    ++value;
                    --shift;
                    --R;
                }
                else {
                    a[L] = value;
                    ++value;
                    --shift;
                    ++L;
                }
            }
            flag = 1;
        }
        if(flag) {
            for(int i=0;i<n;++i) {
                cout<<a[i]<<" ";
            }
            cout<<"\n";
        }

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

    You did the same mistake to me at my first submission,notice that shift=n-2 and R-L+1=n,this mean your shift you decrease n-1 times when L==R,in other word when L==R,your shift will decrease n-1 times,initially shift=n-2 and n-2-(n-1)=n-2-n+1=-1,you right shift (k-1) by -1 ((k-1)>>-1) will happen unexpected operation

    → Reply
»
10 days ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Problem C was exact copy of problem : https://codeforces.net/contest/513/problem/B2

This is extremely unfair to the people who tried this problem for the first time. This also explains why so many people were able to do this problem despite it being good enough that most of my expert friends couldnt do it.

My submission for contest problem : 295640125

Exact same code submission for older version : 295644907

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

    I totally agree with you. What are the testers doing? If it's a problem from another country's website then I can understand why they accidentally made the same problem. But another exact same problem from codeforces????? Insane. It is really unfair for ppl who didnt try this problem like me.

    → Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah higher the jump in between the problems higher is the difficulty change

→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +44 Vote: I do not like it

I found something interesting while reviewing the official common standing: three participants younesg (rank 2), Constantor (rank 7), and CLAY (rank 15)—all failed to solve problem D. Upon examining their code, I noticed a significant similarity in problems C, E, and F. Although they paraphrased the code quite skillfully, it’s evident from problem E that there’s clear code plagiarism among them (295598220, 295609438 and 295632243). I hope MikeMirzayanov and Igor_Parfenov can address this case.

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

How did u all solve 2nd problem , i couldn't understand the editorial someone help me, i thought of a diff approach which i got wrong answer but it was no-where near to this editorial approach please explain. Does this problem looks similar to some previous problem?? How to solve these types of problems I need some advice. This is my second contest and i wanna reach pupil but i guess problems like these are a problem for me

PLease help me how to solve problems like these with ease

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

    You can think like this,initially we have no 1 in our array,if n=1,then we just need to add 1 to the array,and if n=2,also do the same thing add more 1 to the array then answer=2,but think about does n=3 we need to add 1 more? the answer is no,why?For example,you can add 1 in your second times like this ,[1,0,1,0,...0],the sum of interval [1,3] is 2 and the length of interval is (3-1)+1=3,ceil(3/2)=2,so for n=3,answer=2,and similary for n=4,answer=2,So according to this observation we need to make sure the 1 already been added into the array is completely use by us so for example if our array already become [1,1,1,1,1,0,0,0,.....0] assume that there is k times 1 in our array,then how much 1 i will get if i place my next 1 optimally?The answer is (k+1)*2,because you already have k times 1 and you add 1 more then you have k+1 times 1,and let s=(k+1)*2,obviously s/2=(k+1) which is satisfy the statement,so you can directly run a simulation to approach this and the time complextiy will be O(logn) and overall for all test case will be O(tlogn) which is under limit,below is my submission hope useful to you 295580740

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

In E, how to derive the expression "2 * sizeof(vertex) — 1"? Though, i guessed, after this move, move parity will be odd, so, we can go back to the same vertex, using 2 moves and one substraction for parent.

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

    at any vertex you have two choices(if the step is even)- either go down to one of the child vertex or go to the parent vertex... the probability of going to a parent vertex is 1/degree while going to a child node is (degree-1)/degree. let E denote the expected number of steps to reach parent vertex then E= 1/degree + ((degree-1)/degree)*(1/degree)+(((degree-1)/degree)^2)*(1/degree)+........ . Solving this you get the required value of 2*degree-1.

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

did thet tutrioal of D's second idea is wrong,the"write the values n*2,n*2-1,…"should be "write the values n*2,n*2-2,…"

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Question C: What do you want to investigate?

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Curious Patterns in Contest Submissions

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Israel?.... get out.

→ Reply