think-cell Round 1
By satyam343, 9 months ago, In English

Hello, Codeforces!

Welcome to the think-cell Round 1 supported by think-cell, which will start on Feb/17/2024 17:35 (Moscow time). It will be a combined rated round for both divisions. All problems were authored and prepared by Elegia and satyam343.

We would like to thank:

You will be given $$$9$$$ problems and $$$3$$$ hours to solve them. One of the problems will be divided into two subtasks. One of the problems will be interactive. Make sure to read this blog and familiarize yourself with these types of problems before the round!

We hope you'll like the problemset!

UPD 1 : The score distribution is $$$500 - 1000 - 1500 - (1250 + 1000) - 2500 - 2750 - 3500 - 3500 - 5000$$$.

Congratulations to the winners!

  1. cnnfls_csy

  2. Geothermal

  3. Benq

  4. gyh20

  5. Ormlis

  6. jiangly

  7. tourist

  8. ksun48

  9. Petr

  10. maroonrk

Congratulations to the first solves as well!

UPD 2: Editorial is out.

And now a word from our round partner – think-cell:

text

think-cell is the leading data visualization software for business presentations. Our mission is to offer the most intuitive user interface for generating complex data-driven charts and slides, while at the same time ensuring seamless integration with Microsoft Office. We work on challenging visualization problems, reverse-engineer Microsoft’s code, and reinvent how slides are created. think-cell is the only German company funding the C++ ISO committee delegation, so there is a good chance that components we invent will find their way into the standard.

Right now, we are looking for smart, creative C++ engineers with a solid theoretical background to join our engineering team.

Highlights of the role:

  • We use the latest C++ features as soon as the compilers support them.
  • We’re not afraid of advanced template metaprogramming or macros when they avoid code duplication or lead to cleaner, more readable code.
  • We prefer algorithms and ranges (esp. ours!) over raw loops.
  • We take the time to deliver perfect code.
  • We love refactoring and modernizing old code and introducing our own libraries.
  • If we can do better than the standard library, we write our own!
  • If we have done something cool, we talk about it at C++ conferences.
  • If we are missing a C++ language feature, we write a proposal and present it to the C++ standard committee.

Here is what we offer:

  • A competitive salary from the start and a raise to EUR 130,000 annually after only one year.
  • Full support with relocation to Berlin or the option to work fully remotely.
  • An apartment for the first month if relocating to Berlin.
  • Lifestyle-friendly working hours, no deadlines, no overtime.
  • No scheduled meetings.
  • An international team of brilliant minds.
  • A flat organisation with respectful colleagues and plenty of room for your ideas.
  • A working environment that is driven by the strive for excellence.

text

Already convinced?

Learn more

P.S. don't forget to check out our developer blog to learn more about our commitment to the tech world!

Join think-cell Round 1 that will start on Feb/17/2024 17:35 (Moscow time) for a chance to challenge your skills among other developers and win the following prizes.

- First place: Apple iPad Air (10.9-inch iPad Air Wi-Fi 256GB),
- Second and Third place: Apple Watch (Apple Watch Series 9 GPS + Cellular, 41mm Aluminum Case with Solo Loop),
- 4-50 places: think-cell branded socks
- 200 additional socks will be distributed randomly among the rest of the participants who solved at least one problem and for whom this is not the first rated round!

Announcement of think-cell Round 1
  • Vote: I like it
  • +798
  • Vote: I do not like it

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

satyam343 failing to disappoint, as always

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

As a tester, there will be at most one problem about penguins.

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

Tf do I need socks for? Oh wait...

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

As a tester, there will be atmost one problem that stack is bad at.

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

As a tester, good luck earning the socks! :D

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

Damn such a long contest! Excited for this one!

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

As a tester, I enjoyed this contest a lot.

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

It may be good to have the following appended to the name of the contest: (Div 1 + Div 2)

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

As a tester, it’s my first round that I tested. Good luck to everyone!

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

satyam343 orz

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

Waiting for a good contest!

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

    why this is downvoted?

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

      nothing goes as planned in this accursed world

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

      because your comment is the same as you wrote in the other blog(obviously you just wanted contribution)

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

Damn, I never expected this crossover of authors. Nevertheless, I love 3hr rounds.

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

so now they decided to find engineers through codeforces, good

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

Hope to get some green socks

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

delectable round

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

omg EI round

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

Why is this not in homepage?

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

I hope the problem statements will be clear :)

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

This comment has been deleted.

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

Thanks for this round!

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

scoring distribution?

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

Is this rated contest?

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

Will this round be ranked?

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

On Codeforces's homepage, there was no mention of this.

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

Oh my God that socks too good.I need it!!!

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

As a tester, the next contes will be good because it's Div4

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

200 additional socks will be distributed randomly

so like 100 people will get 2 socks each, or 200 people will get 1 sock each?

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

    there is some probablity for both the above situtations, but there are different possible scenerios also.

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

OMG Elegia round

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

"It will be a combined rated round for both divisions"

Did not understand, which divisions it's gonna be?

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

    It will be ranked for every participant, including you. Assuming it will be solvable problems for every division contestant.

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

    it's like div1+div2

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

      hoping for problem statements which are actually understandable , writing in last contest 926 was too poor.

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

OMG EI Round!

Socks as prizes. Novelty. :>

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

The authors and testers will give contest from their alt accounts and win the prizes :D

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

here it is the birth of a new kind of rounds on codeforces

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

Socks❌ Sucks✔️

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

As a tester, this contest will be great!

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

Looking forward for "Good Luck and High Rating" :-)

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

Hope to get some green socks

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

Is this a global round?

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

Eh, most of rounds start at 00:35 AM for my time zone.. While at 07:00 AM I have to wake up and go to the duty :P

Would love to take part, but physically not able to. Good luck to everyone!

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

Will it be harder for me to gain rating in this round rather than in div 2 rounds?

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

Please postpone this round by 1 day, I have a wedding ceremony to attend. Thanks in advance.

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

    Ofcourse I shall petition to make this round unrated.

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

    just dont take the contest lmao. if they had to postpone a contest every time someone couldnt take it there would be a total of 0 contests so far.

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

    Please postpone the wedding ceremony by 1 day if you want to attend the round. Thanks.

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

I got no brain cell, Can I participate in thinkcell!

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

At what rank in this contest, one would get the chance of being interviewed? Is this job available for freshers?

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

DARK ARIA

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

Its time for Gennady to comeback!

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

Yeah! 3 hours!

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

Score distribution?

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

Is it rated ?

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

Cant wait to drop to specialist! Hope this will be a good round and I get some socks

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

Can I cancel my registration or if I don't enter the contest will I get rating?

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

as a tester

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

    As a not tester, I can confrim that you are a tester

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

as a tester friend don't give me contribution

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

Good Luck!

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

I was hoping I'd be able to get some positive rating delta in this contest, but that score distribution is kind of a hint that I won't.

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

Contests authors are working very hard!

(3-day continuous contests)

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

Just a quickie, how to be a world class at knowing c++.

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

Hope that I can get those """programming""" socks

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

I am participating in first time. So I have a good feelings. I believe that every participant will enjoy of round. But I have a one problem or question. Will take T-shirts every participant or only awardeds?

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

Best of luck all. Hopefully i solve 4 problems this contest ≽^•⩊•^≼

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

200 additional socks will be distributed randomly

This means 100 pairs of socks right?

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

Clashing with LC Biweekly, have to skip this one.

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

for which rating people this round is rated?

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

hope to solve a,b,c,d in the least time,, all the best guys

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

very hard to decide between Leetcode Biweekly and CF round xD:)...

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

Can I get a pair of sock, please ? :)

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

Grinding for over 10 hours daily for 3 months, not only on codeforces but also on many other sites, learning binary search, two-pointer techniques, bitmasks, number theory, backtracking, and various other topics. I solved over 30 problems on each topic alone, numerous greedy problems, and the CSES searching problem set . however with all these efforts I still find myself unable to solve problem B, which might be of 800 difficulty

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

    Me after solving A and B. I should now sleep :D

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

    Don't look at difficulties of problems with difficulty $$$\le 1200$$$. Usually, they are not adequate.

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

I constantly press F5 to see who will get an ipad :) the race is so thrilling now

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

If i get 87 likes I'll reach 1700

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

when contest finishes, can someone explain solution to C pls?

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

I solved C by using 2 hours and 3 minutes later I solved D1 ...

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

Is intended solution for problem D2:

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

    Mine used matrix instead of if-else.

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

      What do you do with matrix? I guess, dp, but I didn't come up with dp.

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

        The actual solution is much simpler.

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

        The $$$f$$$-value is to do with something like the length of last 1-segment modulo 3. I used matrix to maintain the remainder and answer.

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

        1)greedy algo for assigning 1s for substring

        "if you are 1 -> greedily push 1 to the next position if there is no already 1 at your or prev pos"

        111100100 -> 0|10000000 01|0000000 010|000000 0101|00000 01010|0000 010100|000 0101000|10 01010001|0 010100010|

        2)dp with 3 values — amount of prev substrings with 1 above us, before us, none of these

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

        Still can't understand the dp solution.

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

          In D1, I did the following to get min number of 1s for each substring:

          • whenever I see 1 in p at index i and it's too far from last 1 in q, I put 1 in q at index i+1.

          extending this to dp gives the following, once we put 1 at index i+1, we don't care about string at index i, i+1 and i+2 so we just jump to i+3.

              vector dp(n+4, 0ll);
 
    ll sum = 0;
    for (int i = n-1; i >= 0; i--) {
        if (s[i] == '0') dp[i] = dp[i+1];
        else {
            dp[i] = dp[i+3] + max(0, n-i-3) + min(n-i, 3);
        }
        sum += dp[i];
    }
          → Reply
          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            Thanks, now I understand.

            We can simplify: $$$max(0, n-i-3) + min(n-i, 3) = n - i$$$.

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

            can u pls help me with understanding the problem statement and ur approach?

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

              1 in p means that in q we will be able to find substring that includes that index and has no. 1s >= no. 0s.

              if
              p = 0011100
              then q can be
              q = 0001000

              • for the leftmost 1 in p, there is substring 01 in q,
              • for the middle 1, there is substring 1,
              • for the right 1, there is substring 10

              1 in q at position i can cover the requirement for 1s in p at positions i-1, i, i+1. And the task is to find min number of 1s in q that cover all 1s in p.

              dp[i] means sum of the answers for all substrings starting at i.

              • dp[i+3] is the sum of answers for substings starting at i+3, and max(0, n-i-3) is the number of substrings starting at i+3, so dp[i+3] + max(0, n-i-3) means adding 1 to all answers for substrings starting from i+3.
              • min(n-i, 3) is for answers for substrings [i, i], [i, i+1] and [i, i+2], i.e. those that don't reach i+3.

              (and as Igor replied, the dp formula can be simplified).

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

          (assume mentioned greedy algo works)

          go from left to right and count in parallel for all substrings

          none_of_these — amount of prev substrings without 1 in last two positions

          cnt1_prev — substrings .......1|0

          cnt1_here — .......0|1

          if val here is 1: you need to create new 1(on next pos) exactly "none of these" + 1(new substring starts here) times. Each of those substrings can end in (n — cur_pos) positions later, so

          ans += (old_none + 1) * (n — cur_pos)

          new_none = cnt1_prev

          new_cnt1_prev = cnt1_here

          cnt1_here = old_none + 1

          if 0:

          new_none = cnt1_prev + old_none + 1

          new_cnt1_prev = cnt1_here

          cnt1_here = 0

          I hope it's clear enough

          i can explain it better in russian, but your first message is in english and i can not reply with ru :(

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

          My D1 DP solution is as follows. Create a DP table $$$D$$$ of size $$$(n + 1) \cdot (n + 1)$$$, where $$$D[i][j]$$$ ($$$i \le j$$$) represents the minimum number of 1s required for the substring $$$s_i s_{i + 1} \ldots s_{j - 1}$$$ (of length $$$j - i$$$).

          Then, calculate the value of $$$D[i][j]$$$ as follows:

          • If $$$i = j$$$, the substring is empty, $$$D[i][j] = 0$$$.
          • If the first character $$$s_i$$$ is 0, $$$D[i][j] = D[i + 1][j]$$$.
          • If the last character $$$s_{j - 1}$$$ is 0, $$$D[i][j] = D[i][j - 1]$$$.
          • Otherwise, the substring has 1s in the both ends. We can cover the whole range with $$$\left\lceil (j - i)/3 \right\rceil$$$ 1s at most. Also all the possible splits need to be considered, thus $$$\displaystyle D[i][j] = \min \left\{ \left\lceil \frac{j-i}{3} \right\rceil , \min_{i < k < j} \left( D[i][k] + D[k][j] \right) \right\}$$$.
          → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    [deleted]

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

C was a pain.

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

How to solve D?

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

    This code finds f(s)

    for (int i = 0; i < s.size()) {
    if (s[i] == '1') ans++, i += 3;
    else i++;
}
    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping to become a specialist <<<<<<< hoping to get the socks

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

Is there any solution to C using segment tree?

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

    The intended solution uses sorting.

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

    I think no that approach will probably fail , I tried during contest but it failed then I came up with greedy solution and it worked.

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

    I used tree compression

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

    I think we can maintain a set consists of non existing element. We can greedily take the element from left to right

    • if the element doesn't exist in the answer set then we add it and keep decrementing it until we reach a value that still doesn't exist in the array then we can add it to the non-existing number set

    • if the elemen exists in the answer set, then we can find the biggest element in non-existing numbers set and add it to the answer while we maintain the set

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

      My solution is basically the same idea you're talking about.

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

my bad,I couldnt help Stack construct the array b.

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

100 is Lexicographically Larger then 99..?

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

    no, it isn't

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

      chill guys, I thought he talking about strings

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

    $$$[100]$$$ is lexicographically larger than $$$[99]$$$, because we're comparing the lexicographical order of arrays, and array values are treated as integers, not strings (similar to comparing instances of std::vector<int> in c++ with >)

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

Who can explain the problem F? If it's not difficult, the steps to solve.

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

I kept reading statement of problem D1 , but couldn't understand the question even after reading for like 1hr

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

By when can we expect results and ratings?

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

is this round rated , any chance for rank increase?

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

    Yes, the round is rated

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

      It's not showing me in my rated contests and neither in unrated contest. Any idea why?

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

        when ratings will be released , only then it will show in contests history

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

how to solve c anyone???

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

I think those who made more than one correct submissions for a question received penalties for the extra submissions

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

Why 512MB memory in G? I suppose you didn't intend to kill memory-inefficient solutions, and you just didn't know such solutions. Please consider using 1024MB (or larger) as a default when you don't care about memory.

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

    chill bro

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

    I am sorry about it. Initially, the memory limit was 256 MB. During testing, the maximum usage was 300 MB, with an average usage of around 180 MB. So, I thought 512 MB should be fine.

    I hope you liked the contest despite this issue.

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

      I got it. I now have a way simpler (and most probably intended) solution for G and it looks nice. Thank you for preparing the contest!

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

How to solve C? what's the optimal strategy

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

Well,emmm,I can not understand what problem D mean.QAQ

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

Your description of the problem is as good as the person who wrote the last round. XD

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

998244353forces

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

Hate D. Wasted my contest.

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

Nice contest, i liked $$$E$$$, and it's only problem i solved($$$\geq$$$ C) lmao:)

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

What's the intended time complexity of F?

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

Feedback:

A: Fine easy problem. If anything a bit easy for its position, but I don't mind the existence of submit bait.

B: Fine problem; this felt like the sort of task where if you try a couple of things one of them will quickly work, and that turned out to be the case.

C: Decent problem, though not especially interesting. I didn't read the detail about how a set can only contain unique elements and implemented the trivial multiset version immediately, but adjusting for the set version didn't feel particularly challenging/interesting. I'm extremely surprised this had so few solves relative to A/B/D.

D: Good problem; characterizing the best strategy and then figuring out how to compute the answer for all substrings in parallel were both pretty interesting (the former task took me longer than it maybe should have...). This felt much harder than C to me, but to be fair I was warned by the scoring distribution. (I also found it harder than E and F, maybe my skill issue.)

E: Very good problem; after a nice little observation it turns out not to be too difficult. I found this easier than D. My one criticism is that the observation is perhaps a bit easy to guess without proving, but it's not too difficult to at least have strong intuition for why the observation is true.

F: Good problem; after recharacterizing the condition as maximizing b_i & ~b_j over all i, j, it works out nicely with a BFS-like strategy.

G: Excellent problem, one of my favorite problems/possibly my favorite problem of the year so far. After figuring out how to arrange the subtrees so that we can do DP processing them in a specific order, the recursive strategy ends up working quite nicely. Very satisfying to think about, the idea is not hard to prove once you have it, and the implementation is short and easy. 10/10 problem, no notes.

H: Good problem. The statement took a few minutes to parse, but I think that's just because the idea involves a lot of notation. My initial reaction is that this seems like it shouldn't be possible, but it ends up working quite nicely. In some sense the general idea is very nicely motivated: if the solution isn't to output preorder and postorder traversals, what else are we going to do? Somehow I convinced myself those wouldn't work and tried other things for a while, but once I came back to that idea it turns out to work out quite nicely. The implementation took me a little longer than for most other problems in this round but still was not too bad. I think this is maybe conceptually easier than G, since G required more insight while for this problem the first thing you'd think to try works if you finish figuring out all the details. However, the implementation is harder, so giving them the same score/placing them in this order seemed reasonable.

I: Seems like a nice problem, but I had an hour to work on it and still had absolutely no idea what to do at the end. I quickly reduced to counting the number of ways to satisfy all the 1 constraints (and then separately counting the number of ways to satisfy all the 0 constraints), and when you formulate this in terms of PIE it seems like it should work out nicely. Unfortunately, this solution ended up relying on a sequence that, according to OEIS, seems not to have a nice closed form, and with that idea aside I didn't come up with anything that seemed productive. This definitely deserved the 5000-point score.

If there were any preparation errors, they didn't meaningfully affect my experience. The one negative about my experience in the contest is that I spent the last hour working on a problem I felt like I had no realistic chance of solving, but such is life and the three-hour duration was probably good for contestants who might be expected to solve one more task in a 9-problem round than they would if the round was shorter. I could perhaps imagine a 2.5-hour duration, but overall I can't fault the choice of duration.

Thanks to the authors!

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

    Can you explain how you implemented F? What algorithms did you use?

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

      After making the observation I discuss in my comment, the general strategy is to maintain two sets A and B (actually, I implement them as arrays, but let's think about them as sets for now). When b_i enters the array, we add all submasks of b_i to A and all submasks of ~b_i to B. As soon as some value enters both sets, mark it as a possible answer.

      The surprising part is that the "add all submasks" step can actually be done efficiently. We just BFS down from b_i, iterating over all bits in b_i and adding b_i ^ (1<<j) to the set if it isn't there already. This way we only enter each bitmask in each set once, giving $$$O(n \log n)$$$ amortized complexity.

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

        I got it. Could this be implemented with a tree of segments?

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

          Maybe? I suppose you could think of this as a variant of lazy propagation in some sense. But I think BFS is strictly easier to implement and will probably have a faster constant factor.

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

    Hey bro can u explain ur logic behind E please?

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

      The key idea is that if we perform $$$i$$$ operations, any set of $$$n - 2ki$$$ elements can be the final set provided that at least one element remaining could have been the central element for the last operation (i.e., one element has $$$k$$$ deleted elements on either side). We can then iterate over $$$k$$$ and $$$i$$$ and do complementary counting (note that there are $$$O(n \log n)$$$ options for $$$k$$$ and $$$i$$$ due to the harmonic series). There are $$$\dbinom{n}{n-2ki}$$$ ways to choose any set of $$$n-2ki$$$ elements to be left over. If we want to ensure that no remaining elements could be the central element for an operation, then all elements remaining must come either before all but $$$k$$$ deleted elements or after all but $$$k$$$ deleted elements. This gives $$$2k$$$ positions where they can enter into the ordering, and we can count the number of ways using stars and bars.

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

        ahh get it now, couldn't get to it in the contests

        appreciate the time and effort

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

        oh it was subsequence not substring T-T

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

        I didn't understand the end of your explanation : what does mean " then all elements remaining must come either before all but k deleted elements or after all but k deleted elements" ?

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

        I couldn't get the end of your explanation like how can we calculate the orderings in which no remaining elements could be the central element for an operation. How did you reach to the formula in your code? can someone please explain it with some examples ?

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

    I think I can solve I if I can compute the first n terms of https://oeis.org/A167510. Is it the same sequence you ran into?

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

      Yep, that's the one. I skimmed a couple of the papers linked from OEIS but none of them got me anywhere especially useful (though for my idea to work I would need to either do some convolution magic I don't see how to do/which might be impossible, or I would need a closed form that works out nicely for my computation).

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

        I think convolution magic works. We need to compute stuff like dp[i]+=dp[j]*seq[i-j], and if we use divide and conquer, then the influence of the first half of the terms on the last half can be done using convolution?

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

          Ahh, I see--thanks for the explanation! I think that trick is probably well-known by now (in the sense that I've seen a decent number of problems possibly made easier by something like that), but I haven't seen it before :)

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

      If you check the GF terms in detail, or in some paper linked in the OEIS, you will find this form:(where $$$U=\frac{1-\sqrt{1-4t^2}}{2t}$$$)

      $$$\frac{1-U^2}{1+U^2}\sum\limits_{k\ge 1}\frac{U^k}{1-U^{2k}}$$$

      Computing the first $$$n$$$ terms of the generating function in $$$U$$$ in $$$O(n\log n)$$$ time by brute force and plugging the expression of $$$t$$$ into it suffices.

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

        When you say "plugging the expression", isn't it computing formal power series composition for which there is no fast algorithm according to https://mirror.codeforces.com/blog/entry/56422?#comment-401173 ?

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

          Hm, did some searching and apparently this paper claims that specifically for this polynomial for U composition can be fast.

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

          This can be done in $$$O(n \log^2 n)$$$ time using the fact that $$$xU^2-U+x=0$$$.

          With that, $$$U^{n+2}=\frac 1x U^{n+1}-U^n$$$, so writing it in the matrix form gives a divide and conquer solution.

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

    Could you please explain C? Read others' explanation but still cant understand the solution.

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

      If $$$S$$$ was a multiset, we can easily see that the optimal strategy would be to let $$$S$$$ contain $$$a_i + i$$$ for all $$$i$$$. The trick is to deal with the fact that $$$S$$$ is not, in fact, a multiset. The idea is that by waiting to take $$$a_i$$$ from our set until some element with a lower index has been removed, we can add $$$a_i + i - 1$$$ to $$$S$$$ instead. So while our multiset has multiple copies of some element $$$x$$$, replace all but one of them with $$$x-1$$$, and do this until all elements are unique.

      There are some details left to prove, e.g. showing that we can't achieve a larger set $$$S$$$ in the end and showing that we can decrease the index of all elements of $$$a$$$ in the desired way without ever trying to reduce the index of $$$a_0$$$. However, these aren't especially hard to work out, and the general idea is as given above. (To implement, I built the original multiset directly as a map from values to the number of times that value appears. Then, I repeatedly took the largest element $$$x$$$, output its value, and if there were $$$y$$$ copies of that element, added $$$y-1$$$ copies of $$$x-1$$$.)

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

        Please can anyone share the proof for how it is always possible achieve values $$$(\alpha-1, \alpha)$$$ whenever we have two colliding occurrences of $$$\alpha$$$.
        It makes intuitive sense, but I'm interested to see the proof for learning how to prove such combinatorial stuff.

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

        Solved it. Thanks.

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

Reading questions wastes loooooooooots of time, maybe I should improve my reading comprehension skills

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

5 problems in 1:15 let's gooooooooooooooooooooooooooooooooooooooooooo I'm getting back to blueeeeee

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

C became a lot easier when I noticed the output doesn't require the number of elements in the array $$$b$$$ — because this means it's always optimal to greedily assign the largest value possible while avoiding all duplicates. If there were cases when duplicates could be optimal, then the checker would have to know the number of elements in $$$b$$$ in advance before reading the actual elements.

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

    Or, you know, the checker could use readLine

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

      Yes, but in most cases the checker ignores whitespaces, so even when the statement says to print $$$x$$$ lines people can just print them in one line. If the checker was to exhaustively check each lines then the statement should clarify it imo.

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

      Or, because the answer is unique, the checker could just check if output files are identical (disregarding whitespaces)

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

        That's also true. Though it would be more clearer for the checker to identify which number corresponds to which test set. I think the current checker is kind of assuming that the participant will always output exactly $$$n$$$ numbers for each case.

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

My solution for problem C.

Look at an element $$$a_i$$$. We can get from it any value on segment $$$[a_i + 1, a_i + i]$$$.

But can we for any chosen values on segments for all elements achieve those values? Yes. There are $$$n!$$$ ways to choose values on segments for all elements. And there are $$$n!$$$ ways to choose a permutation of "take" operations. And there is a bijection between them: if we change permutation, some values on segments will also change.

Now we have $$$n$$$ segments. We want to choose one number from every segment and maximize minimal not appearing number. Can we sort segments by right borders in decreasing order and take them greedily? Well, no. It can happen, that a segment with big right border has small left border, which we can use later.

We can achieve here $$$9, 8, 7, 6, 5, 4, 3, 2$$$

[1, 2]
[2, 5]
[4, 6]
[2, 7]
[3, 7]
[1, 8]
[2, 8]
[1, 9]

Instead, we can use this greedy. We will take the biggest left border of the segment. But we will choose only from those segments, whose right border is not less, that number, we are going to take now. I achieved it by having two sets. I "iterate" on numbers in decreasing order. The first set contains segments, whose right border is too small yet, and sorts them by that right border. The second set contains segments, whose right border is enough, and sorts them by left border. I take elements from second set, every time decresing number by $$$1$$$ and moving segments, which became "available", from first set to second.

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

How to solve D2? I did DP on D1, no idea of how to solve for such a large n.

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

Cool problemset! Really enjoyed the contest!

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

so fast SYSTEM TESTING :)

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

This is how I came up with Problem C Solution :

At any moment, for index i in array A, we only need to consider how many elements before i that were deleted as the elements deleted after i do not update it's index in A.

Now, consider the following cases for an index j < i in array A.

$$$ Case 1 : A[j] + j < A[i] + i $$$

We can delete element at ith index before deleting element at jth index.

$$$ Case 2 : A[j] + j > A[i] + i $$$

If we delete jth element before deleting ith element then the value of ith element in array B will be lesser than A[i] + i since jth element deletion decreases it's updated index. I can always get an array B' in which I'll have two elements with values (A[j]+j, A[i]+i) which will be lexicographically larger than array B.

$$$ Case 3 : A[j] + j = A[i] + i $$$

It is better to delete jth element first, immediately followed by ith element since in other cases, we may end with one element lesser in our array B.

So, considering all these cases, we only need to consider for any index i, whether the last element in array B is equal to the value of element i i.e., (A[i]+i).

Here is my accepted code.

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

G is such an amazing problem! The solution felt like magic, shame I didn't have time left for it during the contest

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

How are the rating changes decided for div1+2?

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

guessforces

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

    The description of D is terrible

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

      that was the point. It would be B if described clearly

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

      Ok, I'll take the bait. What do you think is a better way to write the statement of D?

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

As a participant hope to finally reach pupil :3

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

How does this solution (quadratic time) pass for D2? Seems like weak tests.

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

    Compiler optimizes the inner loop to take constant time instead of linear.

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

    compiler is probably smart enough to optimize

    for(int j=i;j>0;j--){
    dp[i]+=1;
}

    with

    dp[i]+=i

    other than that: this solution is not quadratic

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

      Oh, I didn't know it was a thing! What if it was something like:

      for(int j=i;j>0;j--){
    dp[i]+=13;
}

      Would the compiler optimize it to dp[i] += 13 * i?

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

        honestly I'm not really aware how exactly it works, I just know that sometimes compiler can do magic optimzations :)

        I guess you can experiment with it on your own

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

Nice Contest.

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

great round as expected. good job!

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

For problem F, a straight-forward brute force on Trie is as follows.

Build a Trie tree on all values, and greedily iterate on i from 22 to 0 to see whether 2^i can be added to the answer. Maintain two candidate Trie node lists L and R, which means that, for the current stage, any leaf node in the subtree of any node in R, when pairing with any leaf node in the subtree of any node L, there exists a valid mask, that can achieve the current maximum possible answer. And for each layer, if there exists a node in R that has a right child, and a node in L that has a left child, then we can greedily add 2^i to the answer just by letting the i-th bit of the mask be 0, and update L, R with all left children of nodes in L and all right children of nodes in R. Otherwise, 2^i can't be added to the answer, and any children of nodes in L and R remains the candidate.

In this brute force, although the addition of value is O(logN), the candidate list can grow as large as the size of N, which certainly won't fit the time limit. However, if we modify the simple brute force a bit by limiting that we have at most 100 candidate nodes for each layer (and simply throwing away other possible candidates), the solution magically passes all the tests.

Link to my submission: https://mirror.codeforces.com/contest/1930/submission/246909255

It's the first solution I can come up with when taking a first glance at the problem, but unfortunately I don't have enough time to write down the solution during the contest due to too much time wasted on debugging D2 which I used a far more complicated method than desired. I think more data should be added to hack such a simple "brute force + greedy" solution.

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

    I hacked your solution. Here is the code for the hack https://pastebin.com/Kq4juNnM

    I do agree that a stronger tests should be added for these kinds of solution. But to come up with my hack test, I need to analyze your pruning part: which side you prioritize keeping. In your code, you keep all your right descendants of the left candidates. So my test won't work if you just slightly change this priority. Imo it is not straight forward to come up with some general tests to rule out these kinds of solution, and might need several tests to do so.

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

      Thank you for coming up with the hack! I totally agree that it's not easy to hack such solutions, and it's actually a general challenge for setting up tests for the category of "finding-the-best" cp problems, where desired observations can be substituted by some simple randomness or clever heuristics to work within the time limit as well.

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

It was a great experience thank you very much

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

Can somebody give a proof for problem C ?

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

    it comes down to 2 basic cases we can pick the maximum of the current array of (a[i]+i) if its unique or we can take the first occurence of the maximum (a[i]+i) now if we take any other occurence then the smallest i for which a[i]+i(say,k) was maximum remains unchanged then for the next time that value gets picked and we already have the same value in the set so it won't count and hence the element will be wasted now if we choose the first occurence then for all other occurence , k become k-1 so for the next iteration same process will be repeated and the the duplicate updated value will be used when they occur as first occurence

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

      I got this but I don't understand why putting
      cnt[k-1] += cnt[k] — 1
      Doesn't mess it up
      Shouldn't it also change for all other elements? Why just changing the max elements satisfies while that max element can affect everyone

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

        Every copy of max element then becomes a copy of max-1 as we always choose the first occurence of max, again if there was already a max-1 in the array then all the copies of max-1 become copies of max-2 and so on until each copy becomes an unique max of the current array Try dry running for 3 2 1 7 8 9 6 5 4

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

    Yeah:

    We rewrite the array as v[i]+i for all i.

    It is easy to see that we can do no better than the array with the duplicates "subtracted by 1" until they're unique.

    Now we need to prove that we can achieve that.

    First of all, let's show that we can achieve an array with all N elements. To do so, we go to the max element, and select the first occurrence of it. Every element after is decremented, so all following occurrences become max-1. We repeat the process.

    Now, why is this suboptimal for the problem? Because while length is kept at N, sometimes we unnecessarily start removing too early in the array harming the elements after. for example initial array of [5,1] (in the modified format) will become [5,0] when it should be [5,1] if we start taking from 1.

    Taking the 1 won't hurt the 5, and they are not identical they are "independent" so surely it must be taken first. We formalize this notion in the following algorithm:

    Assign priority 0 to all elements initially. Priority P means that we need exactly P elements selected from before it in the array prior to it.

    Find the first occurrence of max element, keep it "priority 0". (This is natural, if we select something before it prior to selecting it we will lose the max, so it must be priority zero).

    Similarly, all the other occurrences of the max have their priority incremented to "1". Meaning there must be 1 element selected before they can be selected. They are also decremented, as we know they will be decremented before being selected. This is unchanged from before.

    Now we look at the earliest occurrence of max-1 (which can be either from the initial array or a decremented max). All other occurrences have their priority set to its priority (first max -1) +1. that means, that if it originated from a max, then these have P=2 because they must be selected after.

    Once we are done, all the numbers have priorities. FROM RIGHT TO LEFT, we select an element with priority 0, take it out, and decrement the priority of everything afterwards.

    What this does, is when elements have the same "priority" we take the rightmost one in order to prevent the earlier ones from being decremented. This makes sure we don't needlessly decrement later elements by unnecessarily selecting earlier ones. Just satisfying the priorities means we will be taking all the elements as we specified earlier. (because it will appear in our set as v[i]-initial P)

    Furthermore it is guaranteed that there will always be a priority 0 element (or array is empty and we are done), because a 0 must be followed by a 1 which will in turn become a 0 (and everything else decrements as well), so this algorithm completes.

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

int main() { int t; cin >> t;

while (t--)
{
    int n,k,x,a,m,c,l,r,v;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin>>arr[i];
        arr[i]+=1+i;
    }
    sort(arr.rbegin(), arr.rend());
    int prev = arr[0];
    cout<<arr[0]<<" ";
    for(int i=1;i<n;i++){
        if(arr[i]>=prev){
            prev = prev-1;
        }
        else{
            prev = arr[i];
        }
        cout<<prev<<" ";
    }
    cout<<endl;
}

return 0;

}

How did above solution pass?like when we are sorting and then doing prev-1(first if condition inside loop),this case will be when there will be multiple duplicates but in the else statement we have to know the number of integers we have deleted from left side of new arr[i] encounterd?

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

When will the prize winners be announced?

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

Any proofs of correctness for D greedy solution?

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

    Didn't know about any Greedy, what's that .... It can be done using DP --> 246868553 in O(n) though

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

    check for smaller cases like 10101 or 11100 or 11111

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

    choosing segments of length 2 is the most optimal approach as choosing len>2 will require 2 or more 1's to make it the mode

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

Tutorial plz.

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

Thank you, Elegia so much for problem I! I've never felt as extatic about solving any problem in my life!

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

I got the answer for E but didn't implement it because I think it will TLE, what a pity XD

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

Become an expert successfully!

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

Tutorial plz.

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

Can someone prove my solution for C 246855499
I was messing around with ideas and the Idea that u can always choose in a pattern that the cnt will be max is possible so I just sent it and it was AC

Can someone prove it? Thx

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

Tutorial plz.

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

Update first solve for problem I as Kapt

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

Good level questions...

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

Tutorial plz.

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

Is it easy to cheat on codeforces contests these days ? Because from our country Sputnik123 wrote 5 problems. I don't say problems are too hard at this think-cell round but: In the real life contest (our NOI semifinal, yesterday), he scored much lower than me. And you can also check him submissions.I don't know really did the solutions leaked ? But I am sure this guy is so suspicious and cheated.

Here him first submission for problem C, This code gave Compilation error .

If you check this submission, you will realize that, he forget to change the map name. Lol he can't even cheat. (Check the submission link if you want to see.)

And after few more compilation errors he got accepted. The errors caused by stupid things. And also for accepted submission, there are functions in the template that are never used. And they were not at the first submissions. This is suspicious too. Who can say me that which of these function can be used in the problem C?

Non Accepted Submission Template
Accepted Submission Template

And lastly, I hope MikeMirzayanov will start a big plag test. Sorry for english grammatical errors. Have a nice day!

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

in problem c, after reverse sorting , i have used , if(a[i]==a[i-1])a[i]--; while correct answer is a[i]=min(a[i],a[i-1]-1); what is the difference?

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

    If your goal is to make sure that a[i] is less than or equal to a[i-1]-1 in all cases, the second snippet is likely the correct one it provides more control over the update and ensures that a[i] doesn't become greater than a[i-1]-1.

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

all of this was in a response to a comment i made in this post asking how 2ball did A to C in eight minutes he reached out to me in the dm's and here is what transgressed. I am not accusing him of anything other than being vulgar and disrespectful, a 20 something year old should not retaliate by calling someone the N word i am attaching the pictures of the chat MikeMirzayanov please take the necessary action edit- the image link i don't think i am able to embed it properly https://imgur.com/a/o00YXuU

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

Thank You So Very Much

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

What is the probability of me getting a pair of Think Cell socks, modulo 998244353?

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

246822702, 246822598 they are indeed same, but...

why would you give a cheating to problem A lol, the problem literally saying to write this code. I can't write it in other way

satyam343, MikeMirzayanov

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

    For what it's worth, my code is also literally the same: 246820744

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

      Exactly, I mentioned this previously here too. This 'A' problem shouldn't be considered for plagiarism, it's too obvious and really high chance for false positive.

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

Sorry, that's a coincidence.This code was completed independently by myself.Please return my rating

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

    246852013 and 246856579,it's normal to have the same approach.

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

Hey, I got a mail today for Plagiarism in 1930B. It's saying that anish.naruto/246839764, Rafantasies/246883667 have a match but it's completely normal in this question. Like the logic was pretty straight forward and i think, really lot of people would have done with the same logic. Also, the way of implementation is different in my code using long long and other things. I don't even know the guy with whom my code is matching, please remove the plagiarism as it was my own original code.

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

When will the owners of the socks be announced?

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

Why the contest is skipped? I don't make any cheat. Actually I use a template of my friend. Most of the time I need to change around 10-15 lines in this snipped. Use any friends template or any code snipped Is rule of violation?

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

Why selecting 200 people randomly is so time-consuming? It is about almost 2 weeks.

Please write some note to the blog, if they have been already determined and (maybe) private message or email sent to them.

Kind regards.

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

Congratulations to winners of the prizes! In a few weeks, you will be contacted via private messages with instructions to receive your prize.

As usual, we used the following two scripts for generating random winners, seed is the score of the winner.

get_prizes.py
randgen.cpp

Top 3

Rank Name Prize
1 cnnfls_csy Apple iPad Air
2 Geothermal Apple Watch
3 Benq Apple Watch

Socks winners

List place Contest Rank Name
4 1930 4 gyh20
5 1930 5 Ormlis
6 1930 6 jiangly
7 1930 7 tourist
8 1930 8 ksun48
9 1930 9 Petr
10 1930 10 maroonrk
11 1930 11 ugly2333
12 1930 12 AmazingTalker_Frank
13 1930 13 thenymphsofdelphi
14 1930 14 244mhq
15 1930 15 arvindf232
16 1930 16 Adam_GS
17 1930 17 potato167
18 1930 18 natofp
19 1930 19 maspy
20 1930 20 bachbeo2007
21 1930 21 stkwill
22 1930 22 Szoboszlai10
23 1930 23 tute7627
24 1930 24 jeroenodb
25 1930 25 JoesSR_
26 1930 26 gisp_zjz
27 1930 27 ttklwxx
28 1930 28 Mangooste
29 1930 29 CJ_xde_lt
30 1930 30 hitonanode
31 1930 31 Rubikun
32 1930 32 Pyqe
33 1930 33 AlternatingCurrent
34 1930 34 A_G
35 1930 35 DoIodu123
36 1930 36 E_fireworks
37 1930 37 TKT_YI
38 1930 38 le0n
39 1930 39 siganai
40 1930 40 Kevin114514
41 1930 41 SongC
42 1930 42 shiomusubi496
43 1930 43 StarSilk
44 1930 44 kotatsugame
45 1930 45 frodakcin
46 1930 46 hank55663
47 1930 47 emthrm
48 1930 48 BalintR
49 1930 49 xuanxuan001
50 1930 50 Thienu
111 1930 111 QwertyPi
199 1930 199 uwu
204 1930 204 superguymj
319 1930 319 Hanazaki
470 1930 470 lvkaiyi0811
491 1930 492 ns7407346
624 1930 625 Hard_Hard
715 1930 717 ifail
749 1930 751 Fly_37
817 1930 819 lmaozzz
853 1930 855 djm03178
864 1930 868 JeffreyLC
873 1930 877 _SMART_FAMILY_
1028 1930 1032 eggag32
1043 1930 1047 kevaljain
1133 1930 1135 Aniket_Kumar1
1251 1930 1256 Tony1234
1267 1930 1272 Dorothy__
1324 1930 1330 molhaam1
1332 1930 1338 thesuaveguy
1398 1930 1404 ABDAZE
1574 1930 1582 tiom4eg
1647 1930 1654 wei138
1662 1930 1670 ventilator13
1727 1930 1737 trassis
1729 1930 1739 -Ibrahim-
1736 1930 1745 LLGM
1745 1930 1756 SanguineChameleon
1847 1930 1859 ParsaF
1932 1930 1946 Striker009
1939 1930 1953 AHMADUL
1944 1930 1957 Prayag_Kalriya_
2069 1930 2081 viv123
2087 1930 2102 urirob
2153 1930 2169 kaks_30
2159 1930 2173 m_ithunvoe
2260 1930 2277 notHuman9504
2298 1930 2316 FIorian
2420 1930 2442 Rage10
2472 1930 2490 PiyooBislerii
2580 1930 2603 chiragvarshney_9528
2646 1930 2669 AbdoGad
2789 1930 2811 Taurus388
2927 1930 2954 BabyPopcorn
2978 1930 3006 hritik25
3006 1930 3035 KoKai
3097 1930 3126 chaitanyan
3142 1930 3174 Stark0509
3187 1930 3221 abhisheek_gupta
3379 1930 3410 _Poltergeist_
3501 1930 3537 MoLotfi
3507 1930 3537 asy_01
3543 1930 3537 Cy_2010
3604 1930 3620 AlfaGenius
3613 1930 3620 randombernie
3870 1930 3880 SG2Alok
3902 1930 3933 pranavsingh0111
3903 1930 3933 teckedboy
3961 1930 4000 Hasher_08
4118 1930 4126 RaviSkumar
4133 1930 4164 Avi0308
4216 1930 4247 Warlock_007
4223 1930 4262 goldrevboy
4245 1930 4262 Byf23333
4328 1930 4353 kunal10200
4358 1930 4398 mitocondia
4379 1930 4416 Luca_with_LL
4449 1930 4484 Zeel_Boghara
4490 1930 4532 NoticeMeSenpai
4532 1930 4572 Pisces233
4544 1930 4593 lecxe
4581 1930 4621 haters
4671 1930 4702 IUA_Hasin
4684 1930 4724 achyut88
4697 1930 4741 greentree888
4781 1930 4833 eternal1422
4843 1930 4880 kanwarmamta
4884 1930 4921 Aldibek
4915 1930 4964 limif
4934 1930 4985 Axeley
5134 1930 5196 abhinav_mishra
5141 1930 5196 Tasbeh
5148 1930 5210 HERMES017
5220 1930 5273 vrangr
5227 1930 5273 santGom05
5247 1930 5294 Struggler8
5292 1930 5353 samandarhacker
5322 1930 5375 yadav_rahul2122
5388 1930 5441 im_gh
5510 1930 5561 FATHER5
5536 1930 5602 ash0904
5608 1930 5676 Faissel
5619 1930 5676 phngnh
5631 1930 5694 Alorithm
5670 1930 5725 rishyy09
5746 1930 5813 kishansinh
5754 1930 5813 leVi_
5815 1930 5873 codeforces_ravi_7
5891 1930 5964 Rahmandretop
5921 1930 5992 was_sitting_under_a_tree
5923 1930 5992 breakthe_rule
5968 1930 6024 Aiden121pearce
6022 1930 6097 Nahull
6085 1930 6165 Vagray
6158 1930 6226 sounak.purkayastha
6268 1930 6346 namra2004
6296 1930 6370 hasan_15_07_03
6306 1930 6385 MaciejDaciej
6366 1930 6441 mada-mada
6427 1930 6512 SALmncA.S
6455 1930 6539 aditya_0670
6464 1930 6539 Mehedy_Hasan_Alvee
6561 1930 6632 wlllz
6681 1930 6763 Yzmddsw
6766 1930 6855 eucalyptus
6858 1930 6945 Kunal12345
6937 1930 7025 RockyKGFV
7003 1930 7100 MASTERScp
7033 1930 7136 Calyrex
7072 1930 7165 soumyatus12345
7074 1930 7176 fastybanno
7332 1930 7448 Zer012
7344 1930 7460 czkkkkk
7426 1930 7544 TranHungTien
7439 1930 7556 ur_mum
7521 1930 7637 mj_riffu
7543 1930 7665 Gong..
7582 1930 7704 shyam_mourya7
7655 1930 7778 Godussop01
7696 1930 7821 rigel_136
7713 1930 7839 Nahdi_Salim
7755 1930 7884 Pranto_Chandra
7759 1930 7884 _ANTOR_
7767 1930 7891 DPikachu
7776 1930 7904 _anup
7821 1930 7951 lazyBrain
7856 1930 7986 heizequan
7889 1930 8019 devika_123
7900 1930 8035 shenzong
7903 1930 8038 abhijain565aj
7910 1930 8042 Hello....Universe
7933 1930 8070 0001.0
7954 1930 8091 Robin_22
7979 1930 8118 Sandeep_Yadavji
8001 1930 8136 040328
8006 1930 8142 Jayverma
8021 1930 8158 White_Knight_
8127 1930 8268 Madhu125
8186 1930 8332 Amit9
8214 1930 8360 nub_or_what
8218 1930 8360 ntikeswar83
8220 1930 8366 chestnutZ
8531 1930 8697 weakestOsuPlayer_244
8533 1930 8699 chauhan_meet
8622 1930 8787 AmineMezghani
8717 1930 8882 Annikla
8887 1930 8980 hemant030406
9022 1930 9147 KRISH_V_0610
9107 1930 9257 BinarySage004
9171 1930 9319 yashk6767
9190 1930 9381 Sunij225
9261 1930 9445 assasinator
9268 1930 9445 aayush.03k
9269 1930 9445 sjsgmm
9274 1930 9445 rahmaheni
9286 1930 9445 YetAnotherError
9478 1930 9684 TarunSaha
9567 1930 9780 zzy__
9690 1930 9930 VampWeeknd
9717 1930 9949 poban_chandra_sarker
9741 1930 9992 asabiwasabi
9778 1930 10042 nzx0917
9904 1930 10178 AbdoMO
9967 1930 10236 Javahir
10123 1930 10404 Slein1x
10156 1930 10440 phantomthecoder
10199 1930 10498 vedprox.exe
10203 1930 10498 neerajkumar4
10214 1930 10507 harshb777
10218 1930 10507 Its_pro_deep
10252 1930 10554 _Md_shakib_khan13
10332 1930 10655 Priyanshu-Batham
10349 1930 10667 MrJahrakal
10353 1930 10667 beyes
10365 1930 10691 hashcliffe
10379 1930 10707 mind9121
10409 1930 10740 Arif_NCS13
10419 1930 10753 invictus_conductor
10482 1930 10816 omarnasser_0
10497 1930 10834 iamgolamrabbanii
10518 1930 10852 Abdulaziz.A
10602 1930 10948 hemant_kumar023
10610 1930 10958 h_ardik
10615 1930 10964 jubaer_421_bubt
10624 1930 10976 antu21
10699 1930 11062 sayed_syl
10826 1930 11203 Hidden_Dark
10879 1930 11264 Tanha_Tanven34
10903 1930 11289 Running_
10958 1930 11345 MBZ
→ Reply