Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)
By Amir_Parsa, 16 months ago, In English

Salam, Codeforces! $$$\color{white}{\text{ «Be attentive about your thought that becomes your behavior» «Be attentive about your behavior that becomes your speech» «Be attentive about your speech because it becomes your habit»«Be attentive about your habit because it becomes your personality»«Be attentive about your personality because it becomes your destiny» Said by: Imam Ali}}$$$

We're so excited to invite you to take part in our round Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2) which will start on Aug/26/2023 17:35 (Moscow time). The round will be rated and open for everyone.

The problems were prepared and authored by amenotiomoi, Dhruvil Psychotic_D Kakadiya, Han wuhudsm Jinlong, Amir Hossein Amir_Parsa Farhadi, Matthew chromate00 Roh, JohnVictor, ODT, ugly2333, Lavine, RiverHamster, MagicalFlower and AquaMoon.

We would like to thank :

You will be given $$$9$$$ problems and $$$3$$$ hours to solve!

Score Distribution:

$$$500-1000-1250-1500-2000-2500-3000-3500-4250$$$

UPD1 : Editorial is out.

UPD2 :

First Solve

Problem Name
A qiuzx
B noimi
C SSRS_
D Um_nik
E Geothermal
F MysticPanda
G Radewoosh
H maroonrk
I Radewoosh, One and only Orz

Top Performers

Rank Name
1 Radewoosh
2 maroonrk
3 jqdai0815
4 Benq
5 Um_nik
6 jiangly
7 SSRS_
8 noimi
9 hos.lyric
10 Brewess

GL & HF ;)

Sign up for the contest →

This round wouldn't have been possible without Harbour.Space University's support.

This contest is for all interested eligible programmers who want to start their bachelor and master studies in Barcelona, Spain or Bangkok, Thailand, and join ICPC team.

For the next academic year (2023/24), Harbour.Space University is recruiting a fascinating community of competitive programmers from the top prize-winners of international Olympiads to join one of several competitive programming teams at the university.

In the next few years, their goal is to continue winning SWERC and competing at a high level in the ICPC globally. Therefore they want to invest a serious amount of energy, resources, and talent into these activities.

That’s why you are invited on an exciting journey in the company of like-minded people, outstanding coaches, and ongoing partnership Harbour.Space University with Codeforces.

Over 100 educational rounds were already organized, so the time has come to test our joint efforts and reward the most diligent.

Here’s what you win if you place in the contest:

Codeforces and Harbour.Space

The monthly living allowance throughout the entire duration of studies may vary depending on the overall performance of the students as measured by their GPA, professional achievements and official ICPC competition results. As a guideline, it is in the range of 700-1500 EUR (it might be applied to the contestants who win 4th-10th places).

No application fee is required for any of the awards listed above.

Good luck, and may the code be with you!

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

Comments Comments (257)
| Write comment?
»
16 months ago, # |
  Vote: I like it +22 Vote: I do not like it

Finally the first official round of TheForces, I am so happy at this moment and looking forward to your wonderful feedbacks and participation, Good luck!

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

This is my first time as an author. I hope you will enjoy the problems.

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

There is an inconsistency, Round says (Div 1 + 2), 9 problems and 3 hours whereas the scoring distribution is for a 7 problem split Div 1 and Div 2

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

It was my first time testing codeforces round, I am so happy!

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

Excited for your first round as an author my friend amenotiomoi :)

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

Welcome to the first official contest of theforces, hope you enjoy our problems (including my problems)! (≧ω≦)

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

As a problemsetter, I hope everyone enjoy the experience in the contest!

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

OMG Psychotic_D round!

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

As a Tester, I am here to comment :).

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

    As a tester, I am also here to comment :))

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

As a tester, I enjoyed the round and found some very nice problems! I recommend you to participate.

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

As a tester, I recommend all of you to participate in the contest. It's a classic one.

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

First time as a tester I recommend you to take part in this round!

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

TheForces to Codeforces... orz!

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

as a first time tester, the problems are very nice to do :]

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

As a non first time tester, the problems are quite nice and I hope you have fun solving them.

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

AquaMoon + TheForces contest , can't get better than this

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

    Thanks for your support, have fun and good luck! (●'◡'●)

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

As a tester, I wish you good luck and have fun solving these cool problems :)

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

First time as a tester! I hope you can enjoy these problems.

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

it's my first time being a tester ~ hope u enjoy the round

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

    How can I be as good as you, Nanani. You are already a test for a codeforces round which is a achievement I've never reach. I hope I can one day be as 1% good as you, Nanani.

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

      Just DM problem-setters lol, you can be our rounds tester next times if you wish ...

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

Orz ODT round!

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

As a first time tester, hope you all can have fun and also get positive delta.

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

As a tester i did not realize the blog has been posted xD

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

Are placements calculated from everyone who participated in the contest, or from those that applied for the university? As it says "Awards are distributed to those who are interested in pursuing..." in the picture, but the description says "if you place in the contest".

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

So many testers that none of the comments are participants

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

First time seeing score of any problem is 4250. Interesting to see who is able to solve it first

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

AkibAzmain bruh how were the problems ?

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

TheForces Orz

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

I got impressed by your creativity in indicating 'You' as legendary grandmaster colour( in last point of thanking ) .❤️

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

As a tester: the problems are cool!

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

Very good, I need to sleep well before the contest starts

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

If these turning epochs do not move with aw will today, the spheres of time are not constant do not grieve, Poem by Hafez Shirazi

Nice poem in the announcement :)

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

As a tester, I tested the round.

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

    OOOh, thank you very very very very very much.. I don't know what would have happened if you didn't tell us. Now, I started thinking of searching for another CP site.

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

      You do know that CP sites are illegal, right?

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

Hello Contest Organizers, I'm new to the platform and have never tried Div1 + Div2. Should I register ? Would this make my rating fall bad if I could only solve 1 or 2 problems?

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

As a first time Codeforces round tester, I'm pretty much sure that everyone will enjoy solving the problems.

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

is score related to rating range of a problem?

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

    It is related to the team's (setter/tester) subjective thoughts about the proportional difficulty compared to other tasks. It may or may not correlate to absolute rating, but we do aim for it to.

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

As a participant, I am writing this comment just to comment :)

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

Loved that you... That was precious... Few people know these things...

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

Thanks MikeMirzayanov for black testing

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

First time testing an official round.
The experience was awesome and I've learned a lot of things.
As a tester, I can say that the problems are really interesting. GL&HF
Congrats to TheForces for having their first official round!!!

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

220364168 what is wrong in it for 1779C - Least Prefix Sum

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

As a tester, the problem setters are not retarded.

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

I may be able to solve problem D this time.

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

"If these turning epochs do not move with aw will today, the spheres of time are not constant do not grieve, Poem by Ha"

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

All the best

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

Is it rated for codeforces rating??

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

TheForces Orz...

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

for all interested eligible programmers

Eligible for what?

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

Hope a good round! Hope I won't become expert today :(

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

Should I participate this contest to become pupil? Or even after solving question i will get negative delta?

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

    You should not think about neg delta. If not in this contest, then in future you will become pupil. But , if you miss this good contest which is even rated for LGMs then, you will miss a good experience that you could have done.

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

      Indeed its true i will participate for sure, but im really frustrated with my progress

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

        If you are frustrated by your one then have a look at mine :)

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

VivaciousAubergine, for not testing.

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

It's been 8 months since my last (Div. 1 + Div. 2) Contest. I'm eager to reclaim my BLUE rating once more.

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

any 「Chtholly」？ or at least one block-divide algorithm problem，right？XD

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

In my mind E is always a DP problem. Will it...?

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

    Nope! Well, maybe it might be, but my approach (please don't FST) was limited to MSD-RadixSort, bit manipulations, and basic combinatorics.

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

      Me too. I'm surprised that there are no DP problems from A to E...

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

        I thought D is a DP problem. What's your approach?

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

        isn't D dp?

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

          I think it's a greedy & brute force problem. :)

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

            i solved it with dp idk how to solve it greedly

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

            I saw your solution by adding you into my friend list(and see your code in "Friend standing"). I think what you were doing can be classified as DP.

            EDIT : I misunderstood your solution. I am too stupid,.

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

              220542661

              How? Do you mean down/sumto/diffto arrays? I think it should be from the lazytags in Segment Trees..

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

9 problems & 3 hours! Amazing! Good luck!

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

Looking forward to solve 2 out of 9 problems.

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

I liked problem C.

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

Nice problemset. how to solve D i am thinking like a range for each one then crossing out the zeroes in that range ?

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

    greedy

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

    Iterate over rows from top to bottom. Notice for each 1 that remains in the current row, you are forced to use an operation.

    Thus, the idea is to loop over rows from top to bottom and count the number of ones. Then, you have to find a way to efficiently store the effects of the operations on future rows.

    This can be done by keeping track of the number of operations performed on each diagonal and using prefix sums for each row.

    My submission: 220552191

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

How can I get abdnp from this input? in Problem B

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it 
    // * * means swapping elements above the stars
// **** means reversing elements above the stars

abndp
* *
nbadp
 ****
npdab
* *
dpnab
 ****
dbanp
* *
abdnp
    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks!

      I thought for 2 hours that the right solution was wrong because I did not found a way to do it.

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

        In a case like that you should implement brute force (takes less than 5 minutes) and run it locally. It's instantaneous to BFS all possible operations for small strings.

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

      .

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

    abndp -(2)-> apdnb -(1)-> dpanb -(2)-> dbnap -(2)-> anbdp -(1)-> adbnp

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

      So all downvoters, can you please explain, what made you downvote my comment? It answers the question.

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

        The original question was:

        How can I get abdnp from this input?

        But you showed how to get adbnp, not abdnp.

        So no, your comment actually didn't answer the question.

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

          Ah, didn't notice it. Yes, you are correct.

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

10 more minutes and I'd have E, :(

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

for B how to prove that even window = sort the whole string?

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

    If the window length is even then reversing the string will change parity of all values,thus each value can be positioned at any index(both odd and even) using two types of operations.

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

    Because of the first kind of operation you can sort all the odd indices and even indices separately. Now if the other kind of operation allows to swap characters at the end of an even window then you can use it to send any odd index element to even index. This allows us to sort the whole array.

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

      you can swap the parity of the indices with even k, but then you have to change the parity of k/2 odd,even pair at the same time. How do you get from this to sorting the whole string

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

        Suppose if you sort the whole string you know which characters are at odd and even indices in the final sorted string. Then you can use the second operation to change the parity of any character that is not in it's correct parity list and finally sort it using first operation.

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

    Assuming you got the part when window is odd. position 0, 2, 4 .. will be sorted position 1, 3, 5 .. will be sorted

    Now, you have arrived at this, then you can change the parity of any element with even window which again can be sorted with i, i+2 swapping,

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

      what i don't get is you have to sort the entire window of k.

      Like k = 6 and s = 231564 in this case all the odd and even indices got swapped at the same time, so 1 and 2 would always have the same parity, but what you want is 12...

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

        In the constraints it is given k<n every time all odds and even wont get swapped

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

    Think of it in this way, let's say you have $$$2$$$ components (graph) of even indexes and odd indexes. Reaching from one node to another means you can swap these $$$2$$$ indexes in the original string. Now if, $$$K$$$ is even that means you have an edge between the $$$2$$$ components of graph making it a single big component, while if $$$K$$$ is odd, parity of swapped indexes will not change, and they will still lie in the same component as their original one.

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

    .

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

    Let 1 represent a character than belongs at an odd position ($$$1, 3, 5,\dots$$$) in the sorted string and let 0 represent a character that belongs at an even position ($$$2, 4, 6,\dots$$$) in the sorted string.

    Lemma: If we can make the string 011010...10101 equal to 101010...10101, we can always sort the original string.

    Proof:

    Construction:

    Start by moving the incorrectly placed 0 (first character) as far back as possible. Now our string is 111010...10100.

    Now, reverse the first $$$k$$$ characters. Now our string is [0101...010111]10...10100 ([] contains the reversed part).

    How many incorrectly placed ones 0's our string currently have? Before the operaiton, we had one such 0. Every 0 included in the reversed segment was good, so now they're all bad. The reversed segment included $$$k/2$$$ elements at an even position, one of which was a 1 and the remaining $$$k/2-1$$$ were 0's. These now became bad, so we have a total of $$$k/2$$$ bad 0's.

    Note about above statement:

    Now, we have $$$k/2$$$ incorrectly placed 0's. Thus, we also must have $$$k/2$$$ incorrectly placed 1's. We can move all of these to the first $$$k$$$ positions of the string and reverse that segment, making all of these good. This concludes the proof that it is always possible to do the operation required for the lemma, which proves that the string can always be sorted. $$$\square$$$

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

    Let A be the minimal set of odd index values we would like to be even, and B be the minimal set of even index values we would like to be odd.

    Clearly |A| = |B|

    By induction, we only need to decrease the size of these sets.

    Place some value of A at index k-1, and some value of B at index k

    Preforming the window operations [0, k-1] and [1, k] will only change the parity of the values at index k-1, and index k.

    So the order of |A| and |B| decrease.

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

Loved Problem D AquaMoon, E was also good but i couldn't implement in time.

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

    Thank you so much, i am so happy that you love my problem! (〃'▽'〃)o

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

As a small point of feedback, I wouldn't use $$$(x, y)$$$ to refer to row $$$x$$$ and column $$$y$$$, the $$$x$$$-axis is usually horizontal / $$$y$$$-axis is usually vertical. Maybe use $$$(r, c)$$$ instead. Otherwise thank you for the contest!

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

What is the pretest #3 of problem G?

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

    Dunno if this is helpful, but I initially failed this because I multiplied by $$$k$$$ instead of $$$k!$$$ when rotating some subset of $$$k$$$ rows. Fixing that got me AC.

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

    Dunno but my solution ended up being very simple — rotate all you currently can in one direction (horizontal/vertical), switch direction, repeat.

    Since I'm doing this for both initial directions, I had to handle $$$A=B$$$ as a special case.

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

      OMG genius implement, helps a lot

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

I like the contest for today D is so good i liked it so much C i got it too late , i was thinking of number theory soultion but it was bitmask

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

Nice contest, thx!!!

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

thanks to authors for the great round, simple problem statements and interesting problems

Plus a,b,c,d were very balanced. Slight sudden difficulty jump at e-but obviously nobody can optimise all the problems to be perfectly balanced.

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

I figured out how to do D when it was about more than 1 hour left, but couldn't implement it...

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

Expecting the solutions~

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

submitted E 9 seconds before the end but it showed contest is over. i will have a huge negative delta, if E is correct then i don't know what i will do.. i'm crying right now

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

    If your solution for E is correct then it means you are able to solve it. The contest is over only means that it doesn't receive more submissions to judge for the standings and the rating which you can still earn whenever there is contest, it's not over for your journey on solving them.

    For me I need about more 5 seconds to submit solution for C.

    Cheer up bro! Let's get ready to revenge in the upcoming contests!

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

      Thank you actually, after all if i deserve a certain rating I will get there no matter what happens, wish the same to you, and yes, i will certainly get ready for a revenge!!

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

Any hints to solve D? I tried 2D Fenwick Tree, but it gave TLE.

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

Good contest overall. Thanks for this round! :)

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

C is sooo brilliant!! And how everyone is genius can be seen from the number of acceptances of C and E!

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

    wuhudsm has always been orz in problemsetting

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

    Can you explain c ?

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it
      Hint(almost solution)
      → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the intended solution for F? My approach was for a query [L,R] first check if L==R if yes then only one operation is needed otherwise we need to bring all element in range [L+1,R] to L and then use one operation to reduce all to 0 but it gave WA on pretest 5. Submission: 220592550

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

    I think it's the same as my solution — for every pair $$$A_i = A_j = v \in [L,R]$$$, check if the maximum value $$$\lt v$$$ that lies between $$$i$$$ and $$$j$$$ is $$$L$$$, if yes then it adds one operation since we can't make both $$$A_i$$$ and $$$A_j$$$ zero "together", there have to be operations changing that maximum $$$\lt v$$$ between them to zero, then some separate sets of operations changing $$$A_i$$$ and $$$A_j$$$ to zeros.

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

      Yes my approach was also similar. For every a[i] I found the ranges it covers consisting of elements greater than or equal it then used a prefix sum array to calculate the total cost. Could you tell what was wrong in my approach?

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

        Maybe you oversimplified things. That sounds like way less than I had to implement.

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

GapForces

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

    I didn't expect G to have so few ACs during contest.

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

      I could've tried to guess stuff. Instead I tried to figure out a rule, which was quite tough and wrong logic sent me in wrong ways a few times. In comparison, A-F was straightforward thinking (only difference being the amount of thinking), but more of writing down code and optimising it. When you have enough experience, that's a lot easier.

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

      I think G implementation was quite painful (finding the shifts, then finding the ordering constraints, then doing a topsort), and there's special cases like all row/col shifts only (which I failed to recognise in contest)

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

        Because $$$O(n^3)$$$ is allowed, the implementation isn't actually that bad.

        You can just scan for all rows/columns to see whether you want to shift this row/column or not every time.

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

why still not start pending

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

I would like to know which problem is made by ODT

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

seeing the submission count of c question i think brains have evolved

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

I solved C and submit it and it got passed but I thought it could be give Integer overflow therefore I again submit the solution later and my score got decreased why? :(

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

I loved problem E, thank authors for the good contest!

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

someone could give me a code with B?

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

C>>D

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

    Can you please explain how to solve D?

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

      The optimal way is to invert any element whenever you find 1 in the matrix starting from the 1st row.

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

    C: In 20 minutes created, proved and coded solution

    D: In 2.5h couldn't get with anything faster O(n^3) :D

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

    true

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

As someone who is not good at math, I found Problem C much more difficult than Problem D. I spent too much time on Problem C and didn't pay attention to Problem D. That was a lesson learned.

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

    It's interesting to think about math from a binary perspective :)

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

Nice round, thank you!

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

Beautiful problems. It's been a while i've seen problems like these. Though i think C and D could be swaped.

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

Was the 1000 used as the upper bound in Problem C deceptive or is there any solution intended?

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

Can anyone explain how to solve E ?

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

    Let's understand how to count the number of turns for A and B. Alice looks for the first 1 in A|B (suppose its position is i). If A[i] == 0, she understands, that B[i] == 1, so A < B. Otherwise she can't say anything exact, because B[i] can be either 0 or 1, so she skips. Now it's Bob's turn. If B[i] == 0, he understands, that A[i] == 1 and A > B. Otherwise he looks for the next 1 in A|B and the situation repeats. In general, let's define C as the number of 1's in LCP of A and B. If C is even, the answer is C + 1, otherwise C + 2 (corner case A == B, the answer is always C + 1)

    How to count the answer for the problem? We can iterate k = [1, n] and choose A = a[k]. We can use trie to count for each prefix of A the number of B's, such that current prefix is LCP for A and B (suppose this number is P). Then we should add (P × number of turns) / (n × n) to the answer.

    My submission: 220583318

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

    Consider the positions of the 1s in the OR value. When I refer to position, I am talking about these specific positions with 1 in the OR, skipping all the positions with 0 in the OR.

    If Alice has a 0 in the first position, she knows the 1 came from Bob, so her value must be smaller, allowing her to end the game. Otherwise, if she has a 1, she doesn't know whether Bob has a 0 or 1 here (or about later positions, if any), so she answers "I don't know".

    When Alice answers "I don't know" on her first turn, then Bob knows Alice has a 1 in the first position. Now, if Bob has a 0 in either the first or second position, then he knows his number is smaller, and ends the game. But if he has a 1 in his second position, then he answers "I don't know".

    More generally, if both players have 1s in the first $$$k - 1$$$ positions, then the first $$$k - 1$$$ turns are all "I don't know".

    Side Note: If Alice and Bob first differ at the $$$k$$$-th position, then the $$$k$$$-th answer depends on whether the person who is answering has a 1 ("I don't know") or 0 (smaller) in this position. So there are either $$$k$$$ turns or $$$k + 1$$$ turns, depending on who got the smaller value. This might sound annoying, but it's actually easy to handle when we deal with it later.

    So how do we count the expected number of turns? We can first count the total number of turns for every possible pair. But there are $$$n^2$$$ pairs, so we cannot afford to consider each pair one by one. We need a more efficient way to count them.

    My approach for calculating these turncounts involves MSD-RadixSort. We separate numbers based on whether their first bit is 0 or 1, then for each group, we separate them further based on the second bit and so on. At the $$$d$$$-th level, given a group, their first $$$(d - 1)$$$ bits all match and we can keep track of how many 1s are there to get the value of $$$k$$$. Then, if an unordered pair is formed by any number who has a 0 in the considered digit position and any number who has a 1 in the considered digit position, this will result in a turncount of $$$k$$$ or $$$k + 1$$$. Since we actually need to count ordered pairs, we add both $$$k$$$ and $$$k + 1$$$ to our total turncount (one corresponds to whether Alice gets the 0 and the other to whether Bob gets the 0, but we don't care which is which, and this keeps changing when $$$k$$$ updates anyway), i.e., multiply the number of unordered pairs with $$$2k + 1$$$.

    Finally, we need to consider the base-case, when we have a group where all values are equal. The MSD-RadixSort stops here, but it is possible for Alice and Bob to get the same value, which would also be equal to the OR value. If this OR value has a total of $$$k$$$ 1s, then there will be exactly $$$k$$$ turns of "I don't know" and then on the $$$(k + 1)$$$-th turn, the player will realize there are no positions left, and that they both must have the same value. The number of ordered pairs is equal to the size of the group squared (recall that both players might get the same index), and the turncount is exactly $$$k + 1$$$. The case where one or both players get the number 0 is correctly handled here (no need for an exceptional edge case check).

    Finally, don't forget to keep spamming the mod operation and to perform modulo division of the calculated total over $$$n^2$$$ (total number of ordered pairs) to get the final expected value.

    My submission: 220592883 (may have to wait until System Testing is done to see it)

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

I think problem D is boring and easier then D from other contests.

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

    yes but i the implment for D is hard

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

    Just to mention, task D did not exist in the initial problemset. E was originally right after C, which made the gap very large between the two tasks. So, task D was added to alleviate the gap.

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

I think E >> F.

Both Alice and Bob are smart enough.

It's quite hard to be as smart as Alice and Bob LOL.

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

Very unfortunate to have spent an hour writing a brute force solution to E and then 40 minutes looking at a computer screen. But the contest was good.

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

    lol 暴力 is not 'violent' but 'brute force'

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

      Sorry for that, thanks :(

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

Can anyone Explain How in E if a = 2 and b = 3 number of turns are 3.Like first alice think a|b = 3 so b can be 1 or 3 ,then turn will shift to Other person ,he thinks a might be 3 or 2 or 1 ,what ahead?

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

    Third turn: Alice knows that b = 1 or 3.

    If b = 1, then Bob would know that a = 2 or 3, leading to b < a, which stops at second turn.

    So Alice knows that b = 3, then she knows a < b, which stops at third turn.

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

For problem D, I implemented a O(n^3) solution by greedily selecting '1' in row major order and updating subsequent rows using prefix sum array structure. How to solve in O(n^2)?

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

    I did some sort of lazy propagation: updating only the next row, but keeping the information (that this update needs to be propagated further).

    My solution (in Golang): 220584229

    This changes the time complexity to (n^2).

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

    Instead of updating prefix sum array in each row, memorize where should the increment + decrement in the array should happen if you were to construct the prefix sum array at current row. To be specific you can maintain two counter for each column index, specifying how many increment and decrement should happen in each square. Then, whenever going down a row, the increment counter would shift left by one square, and the decrement position would shift right. You can then use this information to construct that prefix sum array in O(n) for each row, and update the counter in O(n) whenever going down a row

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

    Same as above, but using C++: 220587779

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

Can someone give a solution for C?

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

.

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

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

Why I change my code a little and submit again,then get skipped?

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

    We fixed the testcase with $$$n=1$$$, and rejudged all affected solutions. Your first submission on D was affected as well, and the rejudge made your second submission give a penalty due to resubmission. Therefore, we skipped the second submission to fix the issue. Our sincere apologies.

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

Am I the only person who got mad at problem A because the input order was $$$x, y, n$$$ rather than $$$n, x, y$$$?

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

How does subtraction of divisor relate to turning off lowest significant bits? How does it even ensure that we never repeat any divisor of subtraction twice ?

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

    I couldn't solve it, but this is pretty interesting. It is not that hard, just think about it.

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

      I went about it like this:

      If n = 2^k then we can at every step subtract it by n/2 to finally reach 1 using every number exactly once. Eg: 8->4->2->1

      Now suppose the highest set bit in the binary representation of n is k. Then we know that we can reach 1 from 2^k. Now how to reach 2^k from n? At each step we turn off the LSB of n from it till it reaches 2^k since the number formed by the LSB always divides the number and using this operation we use each number only once.

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

    Our construction will consist of two phases; we will show that each divisor is used at most once per stage.

    Let $$$x$$$ be our current value, and let $$$k$$$ be the largest integer such that $$$2^k \mid x$$$ ($$$a \mid b$$$ means $$$a$$$ divides $$$b$$$, i.e. $$$a$$$ is a factor of $$$b$$$). If $$$x = 2^k$$$, we move onto the second phase. If $$$2^k \neq x$$$, then $$$x = 2^k \cdot q$$$ for some integer $$$q > 1$$$. $$$q$$$ must be odd; otherwise $$$2^{k+1}$$$ would divide $$$x$$$ and $$$k$$$ wouldn't be the largest such integer. If we choose $$$d = 2^k$$$ and replace $$$x$$$ with $$$x - d$$$, we get

    $$$x_\text{new} = x - d = 2^k \cdot q - 2^k$$$

    $$$x_\text{new} = 2^k(q - 1)$$$

    Because $$$q$$$ was odd, $$$q-1$$$ must be even. Thus, the largest $$$k_\text{new}$$$ such that $$$2^{k_\text{new}} \mid x_\text{new}$$$ is at least $$$k + 1$$$, so we won't repeat the divisors during the first phase.

    In the second phase, we have $$$x = 2^k$$$ for some integer $$$k$$$. While $$$x > 1$$$, we can keep choosing $$$d = 2^{k-1}$$$ and replacing $$$x$$$ with $$$x - 2^{k-1} = 2^k - 2^{k-1} = 2^{k-1}$$$. Thus, we won't repeat any divisors in the second phase and we will use each divisor at most twice, which is enough to solve the problem. $$$\square$$$

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

    I used the concept of meet in the middle. Suppose x is 39, I define the 'middle' as the biggest power of 2 less than or equal to x. In this case, the 'middle' is 2^5 = 32.

    From 1 to 32: 1 -> 2 -> 4 -> 8 -> 16 -> 32 (Each jump is using a different number)

    From 39 to 32: 39 -> 38 -> 36 -> 32 (This has to do with the lowest significant bit.) (Each jump is using a different number)

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

I have a completely different solution for problem C.

For a given value of $$$n$$$, I assume that there is a solution only considering divisors of the form $$$\frac{n}{p}$$$, where $$$p$$$ is any prime that divides $$$n$$$.

Given that it’s not obvious which $$$p$$$ we should use in each step, I literally try every possible value with backtracking, keeping track of the amount of times I used each divisor with a map (to avoid using them more than two times). As soon as I found a solution, I stop.

Note that in each step of the recursion, I factorize $$$n$$$ in $$$\mathcal{O}(\sqrt{n})$$$ to get all possible values of $$$p$$$.

I have no idea why this solution works, and also why it’s fast enough.

Here is my submission: Link :)

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

    Ruled it out, thinking it would/should TLE.

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

    Yep, this similar solution appeared in the testing. It seems that considering the smallest $$$p$$$ possible is enough for the selection of $$$p$$$ in your solution.

    If you don't understand why the solution works, do not worry. Neither did I

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

How to do B?

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

    Sort the string directly when k is even, otherwise sort the odd and even positions separately.

    My solution: 220536553

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

      You mean when K is even? Can you explain why does it work?

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

        First for operation one, he can change the odd and even parts of the string to any sequence respectively;

        Then for operation two, it doesn't make sense if k is odd, otherwise he can swap characters in odd and even parts.

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

      hi i did this idea but gave me wa can u tell me whats wrong? submission

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

        Why did you use reverse at the end?

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

          i thought i need to reverse the substring of length k when i find out that last char is less than the first char ( didn't think i don't need this operation back then) but doesn't that mean it shouldn't affect the code? because i already sorted the chars which in the same component ( so the condition won't never be true)

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

            But reverse is left-closed and right-open, and the second operation in the problem is in the range $$$[i,i+k-1]$$$, note that $$$-1$$$.

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

Why am I still in queue...

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

Problem E teaches us all that when someone says "Mine is bigger than yours", this person is likely not intelligent and cannot be trusted to speak honestly.

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

Video Editorial For problem A,B,C,D.

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

Really liked the problem C. Unfortunately couldn't solve it during contest...

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

Great contest; felt like authors actually cared about the + Div.2 part of Div.1 + Div.2. Thanks guys!

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

Hey, why was my first solution for A skipped?

I submitted it after 11 minutes and it should be correct. My second submission was after 2h52m and got accepted but it gets 200 points less.

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

    You submitted it twice, your second submission will be counted as the main solution

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

      Yes, i know. But why??

      It is almost the same code. If I had not submitted the second time, I would have gotten 200 points more. (i.e. resubmitting scores me lower, why?).

      UPD:
      https://codeforces.net/contest/1864/submission/220611176 This shows that my first solution was correct on system tests.

      UPD2:
      with ~260 points more i would place ca 5200 instead of ~5950.

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

        You should not submit duplicate solutions, cuz it leads to penalty for you, please read codefores contests rules.

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

          ok, i found it.

          I want to apologize for my discontent. sry.

          (its just the purpose of this rule... but thats how it is...)

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

Does anyone know why this submission TLEs for F on test 49 with C++20, but the same one passes comfortably with C++17?

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

    Same with C++20 vs. C++17

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

    It is related to this blog. I modified the input part of your solution (in particular, inputting all the values before pushing them into vectors) and it gets AC with C++20(64): 220609849

    I tested a hanful of TLE49 solutions, including mine (unironically all are submitted with C++20(64)), and they all passed with C++17 or doing the modification above. I have no idea why that works...

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

Could anyone that knows python give me explanation why the time differ so much in problem E? I use Trie to solve problem E.

During my contest, In the submission 220592727

class Trienode(object):
    def __init__(self):
        self.count = 0
        self.child = [None,None]

It gives me TLE many and many times, and cause me lose big rating. Then after the contest, when I read other's solution, make the submission:220607127), only change the node structure to:

class Trienode(object):
    def __init__(self):
        self.count = 0
        self.left = None
        self.right = None

It passed within 2 seconds. Why they are making so big difference?

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

Radewoosh congrats with winning scholarship in Harbour.Space!

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

All the problems I did were great, this is honestly one of the best rounds I've competed in. I solved A-D and almost solved E in the last 5 minutes but forgot to mod n^2 before calculating the mod inverse :(

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

    Same error as me! Doesn't matter, still a good contest

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

The memory limit of E may be a little small because...

A poor guy is hacked!

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

In problem b, how this test : cdba will be abcd with k=4

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

One of best contests ever thx guys

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

Happy that I solved first 3 problems in this contest , but could have solve little faster to get good rank.

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

I really like problem C. Thanks.

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

Nice Contest

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

Plag check going on ? After these many weeks Ratings are rolled back deyumn.

I got -1 when I was at 1599 Rating, now I hope I get +1 to 1600 and become Expert :)

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

Incorrect plagiarism in Question D: The approach to the question used by many people is quite similar due to the structure of the question: just 3 DP matrices, and because of this, the structure of the code of a lot of the submissions is similar. Please look into this.

→ Reply