Harbour.Space Scholarship Contest 2021-2022 (Div. 1 + Div. 2)
By Harbour.Space, 3 years ago, translation, In English

Codeforces and Harbour.Space

Hey, Codeforces!

We have great news for you.

Harbour.Space University is excited to announce a new contest for all interested programmers who want to start their studies in Barcelona, Spain or Bangkok, Thailand, and join our ICPC team.

The contest will be hosted on the Codeforces platform Jul/22/2021 17:35 (Moscow time). We have prepared 9 problems of the joined (Div1 + Div2) level. The round will be rated and open for everyone.

UPD: Scoring distribution: 250-500-750-1250-1750-2500-3000-3750-5250

UPD2: The editorial is out!

Sign up for the contest →

For the next academic year (2021/22), we are recruiting a fascinating community of competitive programmers from the top prize-winners of international Olympiads to join one of our competitive programming teams at the university.

In the next few years, our goal is to win SWERC and compete at a high level in the ICPC globally. Therefore we want to invest a serious amount of our energy, resources, and talent into these activities.

That’s why we are inviting you on an exciting journey in the company of like-minded people, outstanding coaches, and our ongoing partnership with Codeforces.

We have already organized over 100 educational rounds, so we think 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 depends on the overall performance of the candidate. As a guidance, it is in the range of 500-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.

We would like to say a word of appreciation to:

UPD3: Congratulations to the award winners!

Note1: All the winners get an application fee waiver.
Note2: All of you eligible for Competitive Programming Scholarships (cf rating > 2000) may apply directly through our website and go through the general admissions process.

Guaranteed full scholarship + monthly living allowance + free 3-week course:
- 1 (49). Ali.Kh
- 2 (58). Yousef_Salama
- 3 (175). early-morning-dreams

A full scholarship with interview process + free 3-week course:
- 4 (184). sunyx
- 5 (200). amanbol
- 6 (203). IMRED
- 7 (219). Meijer
- 8 (226). loan
- 9 (265). kpw29
- 10 (267). Huah2

Free 3-week course:
- 11 (292). dhruvsomani
- 12 (299). adamant
- 13 (326). Kaitokid
- 14 (355). RetiredPlayer
- 15 (264). c8kbf

Good luck, and may the code be with you!

Harbour.Space University

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

Comments Comments (299)
| Write comment?
»
3 years ago, # |
← Rev. 5   Vote: I like it -113 Vote: I do not like it

Sir Errichto is an Author, seems Good!

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

    Can i ask why so many downvotes?

    please don't downvote this message :((

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

      because people think that downvotes are better than upvotes :(

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -21 Vote: I do not like it

        My rating is 1351. If i wanna become a specialist after this round, (to gain 50 rating points) 4000th place will be enough, right? (giving the fact that all div1 participants (about 1200 users) will be above me)

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

          I think yes, good luck :)

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

          i also fear of that , to be honest u will not achive today but some day sure

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

            why not today?

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

              because he is not consistent yet thats why

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

      people downvote everything, just like stack overflow ahah, anyway dont take it personal

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

      Get a higher rating and you'll get upvote — CF hidden laws No.1 -

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

        Yes, get higher rating and stop writing stupid comments and you will get upvoted.

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it

Only 3 testers? Kinda weird O_o

UPD: LostCoder was right, more testers were added

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

    only if they were grey

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

    Probably new testers would be added in few more hours i think.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    tourist prepared the last contest all himself. So, i think 3 testers isn't too bad

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

    Now there are 1015 testers.

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

Niceeeeee prizes, but absolutely they're not mine :(

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

Erricto means we r getting Geometry Problems. change my mind!

→ Reply
»
3 years ago, # |
  Vote: I like it -21 Vote: I do not like it

Errichto is one of the authors = good round

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

Weird terms of agreement when registering for the contest:

Section#38:RegistrationTerms

Maybe it makes sense to fix this? So that the cheaters don't have a formal "I didn't break any rules" excuse.

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

Albeit really appreciative for the CF partnership, I highly doubt this recruitment strategy will be particularly effective. Limiting the choices to only top 10 in div 1 just seems absurd and suicidal. Unless it was never intended for the prizes to be collected?

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

    I understand that it's top-10 among those showing interest.

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

      Yes, that would make way more sense. I misinterpreted it.

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

rules are broken again

→ Reply
»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it
benefits summary:
→ Reply
»
3 years ago, # |
  Vote: I like it +68 Vote: I do not like it

Screenshot-2021-07-20-212653

My only achievement at codeforces

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

As a tester, I want to wish you all good luck & high rating!

P.S. Yes, it is rated.

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

Praying for specialist! Also orz to the authors, the testers, and MikeMirzayanov for the Platform!

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

As a tester, I ...

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to decline the scholarship(not that i'll win it, just curious)

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

Hope to reach pupil. Should i solve previous contests of these authors? Would that be helpful?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hoping to be an expert for the first time in this round. Got stuck around 1500-1600 for too long.

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

Looking forward to it! interested in your university. i ma still a bit young but i have plenty of time to practise for your future contests!

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

When, will the scoring distribution be announced ?

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

curious to know how did authors from different nations came together to write a round? As far as I know, CF coordinators don't accept individual problems

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

Hope I can become an International Master after this round.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -75 Vote: I do not like it

i just wanna congratulate tourist, benq and radewoosh for getting the first three places and winning the scholarship

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it a 3 hour round?

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

Score distribution??

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

It's been a while since I entered a contest after a time skip, I'm looking forward to it <3

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

The purpose of the scholarship is to attract the top-ranked coders to join the university and to win ICPC, right? So, if they don't fulfill the requirement for ICPC (e.g. age limitation), does it mean they are not eligible for the scholarship?

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

    Good day, foolishgoat We carefully take a look at each case separately. Winning the ICPC is one of the priorities of our university, but also, we are investing in a community of like-minded competitive programmers. We have had the cases of several top-rated programmers who have been already awarded scholarships for one of our technical master's programmes

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

update: 9 problems in 2h 30m :)

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

I think this round will have best problem ever I have seen.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Score distribution?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

UPD: Scoring distribution: 250-500-750-1250-1750-2500-3000-3750-5250

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have never seen 250 pts for problem A. It will be interesting!

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

tourist ans Benq both are participating today and the fight for rank 1 continues!

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

Speedforces coming up

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

So glad to see mnaeraxr as a problemsetter!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing!!Contest

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

stringforces

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

Does someone ever had this feeling, that you didn't register for the contest and thought you will after you solve till C (pupil goal), and then realize you can't register anymore (for the first time)? (sad emoji). Anyways will upload in practice.

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

    why did you have to use so much tactics??That you didn't register then waited until solving C.Just fucking register before the contest and give the contest like a winner.Don't be so timid!!

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

      For The First Time. Also, Regarding the tactics everyone should have there own Freedom of choice.

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

      saying a person who stopped giving contest after becoming specialist once.Show the same courage yourself if you think you can sustain specialist by giving contest.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        It's a dumb comment from you.How do you know that I am not giving contests because of fear of loosing specialist position??I am very confident that the next contest I will give I will be expert.Besides,I don't consider being specialist as an achievement.For me it's just a node on the path.

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

          A kid who took 71 contest to be specialist once is confident to be expert in his next contest.Just stop lying to yourself bro.

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

            and people like you can only comment like these...I don't care whatever you say.3 years later when I will become red after giving 200 more contests..Please on that day comment some stupid stuffs too..I am inviting you.Till then take care and stop barking

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

At least i will be able to participate in div 3 round.....

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

HackForces

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

Saw a tough Fight between Tourist and BenQ...Congrats BenQ for winning.

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

I trolled on F because of a one char error for like 40 minutes -_- but the problems were good overall.

The observation on E was pretty nice (albeit maybe a bit convoluted?).

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

What is the intended solution for F? I am doing like some $$$O(n \log MAX ( \log MAX + \sqrt{MAX} ))$$$ shit and runtime is ~3950ms. Likely not going to pass sys test.

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

    I had a solution with the same complexity, but couldn't debug in time :/

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

    If you use sqrt decomposition with prefix/suffix sums in each block then the $$$log$$$ factor disappears because the intervals are disjoint.

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

    I was able to do $$$O(n\sqrt{n})$$$

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

    I used Fenwick trees to compute the sum and count of numbers $$$\ge \sqrt{K}$$$, with $$$K=500$$$ it passed systests in 888 ms.

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

How to solve E?

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

    Why my E does not work?

    Foreach p[i] we calculate the k if that p[i] was an unswapped one. Then we collect the frequency of all those k.

    Each k with a freq>=n-2*m is a possible k.

    But that fails on pretest 2, why?

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

      Nope, you still need to do further check. Try this input:

      1
6 2
2 3 4 1 5 6

      Your code outputs 2 0 5, but this is incorrect. Can you change 2 3 4 1 5 6 to 1 2 3 4 5 6 with only two swap operations? You can't; you need at least three.

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

    At most 3 different shift values are possible. Check each of them (we run dfs and check if the number of bad-ordered vertices — number of cycles <= m).

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

    There are at most 3 possible k's (you only consider k's where we have >= n-2*m fixed points, you couldn't move more), and m <= n/3.

    For each k, just check how many swaps you need to sort it.

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

      I will always remember to read special constraints...

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

      I feel like I'm missing something obvious, but how does having atleast n/3 fixed points imply that only 3 k's can satisfy that constraint ?

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

        Using swaps you can change at most $$$2m$$$ positions. That means that each valid k has to have at least $$$n-2m$$$ fixed points. This is smallest when $$$m$$$ is maximal, which is $$$n/3$$$. That means you have to have more than at least $$$n-2\cdot n/3 = n/3$$$ fixed points, which is possible for at most 3 different k's.

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

          Thanks. I got to the "we need n/3 fixed points" criteria but could not come to the conclusion that it means we can have atmost 3 K's.

          The rather simple piece I was overlooking was that each position can only be fixed by a unique 'k'. So the set of fixed points for any two K's do not intersect and therefore having 3 of them have sets of size >= n/3 means there's nothing left for the rest of the Ks.

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

Is problem E related to counting inversions? I think I was close to the idea but couldn't implement it on time xd.

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

Too bad problem B had such weak pretests. :(

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

Thank you for the contest!
Also, I'm glad to see a contest with hacks, for a change.

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

E was such a troll problem.

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

    Why so ? . I just want to know why do you think it is . I wasn't able to solve it,Can you explain your solution ?

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

      The basic idea is that for each k, you perform the shift, and then you count the number of swaps needed to go from one permutation to the other. If it is at most m, we found a good k.

      But this solution takes quadratic time. The key insight is the constraint on m <= n/3. This means that we only need to consider options where at least n/3 numbers are already fixed. And there can be at most 3 of these.

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

Please check why it is giving runtime error for Problem-D :- 123349910

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

Find my D is wrong and resubmit in the last minute!!!!!

Case

And hope my F will pass although it takes 3.96s in pretests

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

what is the hack testcase for B?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

Scoring distribution: 250-**1900(500+14×100)**-750-1250-1750-2500-3000-3750-5250.

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

    What testcase did you use for hack?

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

    You still missed 4 hacks in your room lol

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

    I did my best in hacks too :)

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

    I thought there was a B test case that I was missing after only hacking 1 B solution in my room and seeing others hack 5+ B solutions, but after system testing I see that others were simply way more lucky with the rooms they were in.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help why my solution of B giving wrong answer, got stuck for 1.5 hours:(

link

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

I solved A,C. Solved C first time in codeforces. Thanks for the contest.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it -48 Vote: I do not like it

Hello! Why does this solution for C is failing on the second pretest? I was debbuging it for like two hours, but my debug method has a fatal flaw -- i'm brainlet. Pls help. https://pastebin.com/xqysHjZu

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

    Test with 1010101010. Your code outputs 7, but the correct answer is 6.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it
Observation for E
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for sharing your observation...!

    I thought about it for hours, but couldn't get it :(

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is Test3 in problem F

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

Pretests for D are very weak.

Test case for successful hacking

And my pretest passed solution also fails on this test case and I realized that after hacking someone else solution and locking my own T_T.

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

Problem B & D weak pretest :(

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

i think standings is gonna change very much :/

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

I've got a really nice new achievement in this contest. Which is I'm the first participant to get WA on test 23 on Problem E, and almost the only, actually there are just two participants who managed to do that. Thanks codeforces for this new achievement.

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

How to solve F? I think I figured out how to calculate all pairs apart from ones with structure (i < j a[j] % a[i]).

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

    Add numbers from left to right. When we insert a number $$$a$$$:

    1. $$$b \mod a = b$$$ for all numbers $$$b < a$$$, so add sum of all smaller numbers to answer.
    2. $$$a \mod c = a$$$ for all numbers $$$c > a$$$, so add $$$a$$$ to the answer multiplied by the amount of larger numbers.

    The other 2 cases are a little more difficult

    1. In order to count $$$c \mod a$$$ for numbers $$$c > a$$$, lets notice that $$$c \mod a = c - i \cdot a$$$ for numbers $$$c$$$ in range $$$[a \cdot i, a \cdot (i + 1) - 1]$$$. Just loop over $$$i$$$ and count using the formula. Total iterations over $$$i$$$ for all values will not exceed $$$A \cdot log(A)$$$ (similarly to Sieve of Eratosthenes), because all of the elements are distinct.

    2. In order to count $$$a \mod b$$$ for numbers $$$b < a$$$, we do similarly to above, but instead we precalculate for $$$b$$$. So we do something like add $$$b$$$ to position $$$b$$$, add $$$b$$$ to position $$$b \cdot 2$$$ and so on... Then for $$$a$$$ we will add to the answer the number of smaller elements $$$\times$$$ $$$a$$$ — sum on range $$$[1, a]$$$.

    We can perform all the operations fast using some fenwick trees.

    → Reply
»
3 years ago, # |
  Vote: I like it -38 Vote: I do not like it

unbalanced contest + weak pretests, lmfao.

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

tourist was happily securing second place ... And then the hackers came :)

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

123348935 Problem D Why this gives WA on pretest 17?

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

Hacks on problem D should be a lesson to future problemsetters that you should either have more than 1 brain cell or use $$$t \leq 10^4$$$.

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

    What do you mean?

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

      You can either make all possible test cases with small $$$n$$$ and a small alphabet size(2, 3 or 4) or do the brainless approach of using $$$t=10^4$$$ and making completely random test cases by partitioning $$$1.25 \cdot 10^5$$$ into $$$10^4$$$ parts and making the size of each part the size of the first string for that test case, making the alphabet size a random number between $$$1$$$ and $$$min(n,26)$$$ and making the size of the second string a random number between $$$1$$$ and $$$n$$$. Both of those will definitely make a test case like ab a, which is the only D hack that I know of.

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

        Well, setting $$$t \leq 10^4$$$ is something different than setting higher $$$t$$$ and just making a few random tests, but I guess the "more than 1 brain cell" part is kind of about it.

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

    Bruh, all pretests on D except 2 (and sample test) have $$$t=1$$$. These 2 pretests have $$$t=10$$$ and $$$t=500$$$ respectively.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

Suppose someone hacked any solution. My question is will that test case be included in system test?? Or it remains the same?

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

f**k the sh*t weak pretest

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

FST Forces!!! T_T

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

Is this real? Red coders getting FST on B?????

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

It seems hacker also get hacked :3

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

Good job on making an Educational Hackforces Round!

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

    yeah i can feel the same pain..

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

    Cool.. Educational Round is rated for Div. 1 now, meanwhile AtCoder Regular Contest isn’t for some reason.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

In B, except for the edge cases, not getting covered in system tests. There is also another hack case.

The system tests don't include even a single case of "YES" with sz(s) == 500 and sz(t) == 999, because there are solutions (which got AC'ed), with dp array parameters as 505, 505. (dp[505][505]).

:(

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

Why not $$$10$$$ tasks of "write a cycle"-style?

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

    I was wondering for a while. Did you mean "loop"?

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

      I was wondering for loop a while loop. Did you mean "loop"?

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

Man, what is going on, my submissions are not being checked

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

Your text to link here... I want to know that why problem B is always routime error

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

    I think the line "int i=s.length()-2" is the reason for getting runtime error. s.length() always returns an unsigned integer. If the value of s.length() is 1 then s.length()-2 will not be -1. It will be a big unsigned integer and your string doesn't have that big size. That's why you got runtime error.

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

Hi Everyone, what is the correct approach for problem D, I was trying to greedily find the next matching characters but it's not the correct approach. Do we need to think around dp for this question?

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

    Do greedy on the reversed strings and you will succeed. To prove it: let's say that in the correct solution we do not match a pair of symbols and do backspace instead. Then after some even number of symbols, we will face the same symbol. We could have just deleted all the skipped symbols + this one and just pick the very first one we faced. Thus, our greedy works.

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

      Sir, thank you for hacking my B, only if you could've done it a little earlier :(

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

some people were hacked in the middle of the contest and they were able to resubmit? i dont see this fair but ok..

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

    Yeah, It seems unfair because getting hacked is just telling somebody that your solution will fail system tests .Obviously he/she will resubmit and escape FST .

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

      yeah but that allows you to find the mistake and submit a good solution which will pass. and what is FST?

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

Is B the problem with the most FST in cf history ?

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

The pretest are f*ck*ng weak.

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

With the help of Problem D，I can't get Grand Master！

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

I would worry about losing rating, but fortunately div.3 rounds are unrated for me.

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

A meme:

meme
→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +174 Vote: I do not like it

B & D

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -60 Vote: I do not like it

Currently I am new here started few months ago and did few problems of Div 1.

should I solve 100 problems of Div 1 or I should solve 30-40 and then proceed to Div2

I did the below problem B

But I got late to submit

Can anybody suggest if this is a good approach or a lengthy one

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

    Did anybody explain you not to insert code directly in the comment?

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

    Why do I get So much downvote though I already wrote that I am newbie, you code masters treat a newbie this way to encourage them

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

      1. This blog is about the certain contest, so people only discuss about that contest. Avoid discussing about other stuff.

      2. There are many other people who have asked the same questions. Do some searching online.

      3. People's experiences are different. No one can tell you the single best way to learn.

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

I have a question but I might get downvoted,

What is the importance of pretests if they don't tell me if my solution is correct or not?

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

So I spent more than 1.5 hours on F and after reading some accepted solutions, I realized that I overlooked the "distinct" part. Please press F guys.

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

    But I think there is only a slight difference if written cleanly(which I wasn't able to do so).

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

    WTF I literally just found that I had overlooked it because of your comment.

    F

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

    :O I didn't read that too and just hoped my $$$\mathcal{O}(N*(N/B)*log(N/B))$$$ works lol

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

    Me too! I had a lot of trouble with fitting my $$$O(N * \sqrt {N * \log (N)})$$$ solution in the TL, but eventually I did try deleting the #define int long long line, which helped a lot. Will reconsider using it in the future.

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

Woops I didn't realize we had to end an even number of positions away from the end in problem D so I tried both parity sequences, muh bad.

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

why my submissions are not getting judged?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +14 Vote: I do not like it

Don't forget to check my submissions. My all submissions are still in the queue. :(

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

Does the $$$==$$$ operator on strings return "false" immediately if the lengths are different? I assumed that it doesn't and tried to hack a guy which would have $$$O(n^4)$$$, but it was unsuccessful.

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

Damn! Hackforces :/

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

![ ](image)

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

    same...I was going to gain 93 rating (and reach expert!), but then after system tests, I'm going to lose 7 rating.

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

My F passed with 3.993s. Wow.

(Probably the redemption of last round's F)

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone point out the edge-case of B, though I passed FST, would like to know what it was?

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

hackforces going great :3

why soooo weak pretest!! :'(

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

I think that it's the most fstforces round on cf

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What does FST mean?

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

TLE on 87th test case :( .

Habour poor test case.

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

This contest told me never locked the problem if you don't want to hack others. I knew why i was wrong when I was hacked by others, but I cannot make any submission anymore.

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

score prediction after contest +69

score prediction after system test -69

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

(on test 18)

such a big difference between system-testing on B vs E

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

lesson learnt, never participating in any harbor space contest again.

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

sanghai2000 mind explaining all those xxxxx=1 in:

https://mirror.codeforces.com/contest/1553/submission/123313319

https://mirror.codeforces.com/contest/1553/submission/123326933

https://mirror.codeforces.com/contest/1553/submission/123334705

?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how is cabad cabac correct in problem B: Reverse String?

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

    the steps are 1 2 3 2 1

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

    c

    ca (Going right)

    cab (Going right)

    caba (Going left)

    cabac(Going right)

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

You have been warned.

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

    Looks like a strong testcase for problem D.

    1
<<the blog text>>
weakpretests
    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Does anybody know what was the problem in test 19 problem D?

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

    That's a large test case, I don't know. But looking at your solution, what you're missing probably is that the position at which $$$t$$$ ends must be at even parity relative to the end of $$$s$$$.

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

Thanks for the contest! It was nice. Really enjoyed solving it!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is wrong in this approach with problem D : every two adjacent letters in t should have even distance between them in s. so the path is even odd even odd ...... or odd even odd even odd even.

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

    there is no or. There is a single possibility. D was solvable by a single for. It was honestly ridiculous for a D.

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

      It's a combined round, not ridiculous. In most Div1 + Div2 A-E is solvable by pretty much anyone >= 1700 rating, it's mostly based on observations.

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

    take the index of the last character that you choose, call it p

    the number of characters from p + 1 to the rest of the string has to be even

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

So the solution to D which checks if $$$t$$$ is a subsequence of $$$s$$$ fails on the second testcase in the sample test and then on test $$$17$$$ if anybody is interested.

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

I feel that D could have been worded better. "If you type the string s and press backspace instead of typing several characters of s."

This made it seem like using at least one backspace was compulsory.

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

Can Anyone please explain Why This Solution is giving TLE when being run on GNUC++17(64) compiler and is getting accepted on being run on GNUC++17 Compiler only Link To Accepted Submission

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

Poor contest. G is trash, don't understand why it is approved.

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

    That and bad pretests on B and D. D was literally 10 lines of code that were basically nearly guessable as logic by pupils that hardly have any experience with such contests. B was probably in the end harder than C or D. Also, that left quite a big difference in difficulty between D and E.

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

      There wasn't a gap between D and E
      In fact, if you look at number of solvers and the fact that E is after D, E is barely more difficult at all

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

    I'm curious--why do you dislike G? I think the weak pretests in this round are problematic, but I enjoyed solving G. The main observation (that the answer is at most two) was fairly nice and well-motivated, and my eventual solution was relatively concise. The authors could perhaps have done more to make the round as a whole less focused on speed and on avoiding FSTs, but I thought this problem itself was a fun one to solve.

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

      Quite straight forward, the idea is trivial, I can solve immediately after reading it.

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

    I agree that G is simple and one can come up with a solution in a few minutes (which is bad if you then need to code for 10-15 minutes). That wasn't the case for many testers and organizers though. The number of ACs confirms that the difficulty was fine.

    Even though I was very involved in preparing this problem, I think it's the worst one out of E-I. EFHI are good problems.

    Also, I think that this contest would be much more enjoyable for div1 without the first few problems. I stated many times that combined rounds are bad. What about using just D-I or E-I, maybe with problem G replaced with something more interesting.

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

      Combined rounds are bad but contests with prizes can't be split into divisions.

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

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

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

If cf-predictor is correct, We will see Benq on top replacing tourist.

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

say hello to weak pretests on D

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what's TC 19 in problem D ?

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

    One of them is checking if the postfix after the match of the last char of t[] is of even len.

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

    1

    aba

    ab

    Correct Output: NO

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

Great I TLEd on the system test of D with PyPy because of slow input even though the same solution was less than 300ms with normal Python.

By the way, is stdin.readline always faster than raw_input (in Python 2 / PyPy 2)?

Should I always use raw_input = stdin.readline?

Is output speed important?

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

Basically B and D:

Meme
→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In D, https://mirror.codeforces.com/contest/1553/submission/123351567 I am getting WA on pretest 4, any idea what is the issue? I can see in my submissions but pretest 4 is too huge, so portions of it has got cut out, so I cant understand my mistake. can someone help?

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

    Your mistake is on line 31. You don't need to check this condition and change i and j. We just need to get rid of lines 31-34. But after that, you will have TL. The test will look something like this AAAAAA...AAA AAAAAA...AAB You can get rid of this if you do not check all positions where s[i] == t[0], but only the first one standing on an even and the first one on an odd position.

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

How idiotic of me!

Submitted correct solution, for D — Solution

3 minutes after submitting, realised that it would be better to traverse backwards, and not to miss some edge cases (because the pretests seemed week cause of hacks), in case, if any, so changed a bit in the current code, and submitted this — Code

I thought I had covered the case of even parity left out characters in the end, in my latest reverse traversal submission. But, when I checked it again just after the contest finished, and I was like :(

PS: I had hacked 2 solutions in my room, for the same "odd parity case", which my last solution didn't cover.

Press F :(

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is this code not getting RE on any of system tests with "YES" as answer and sz(t) >= 505?

Link

It gives RE on my local machine.

I even tried to hack it after the contest, but it didn't get RE, and passed the hack.

How is this possible? Can someone explain?

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

I was so certain that in D we didn't have to type the whole s and could skip its suffix and it even passed the pretests
No idea why I thought this way

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

errichto

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

PROBLEM LINK:https://mirror.codeforces.com/contest/1553/problem/B

my solution to this problem got hacked during the contest after it passes the pretests(4).I want to know is there a possibility suppose the hacker didnt hack my solution during the contest and in system testing my solution get accepted because the tests prepared for the question was not good enough or lets say it excludes the test case through which the hacker hacked.??

Also i want to know after somebody succesfully hack other solution do code forces add that particular hack test to their set of tests for system testing or code forces set of tests already has that test case covered.?? please answer

Thanks in advance

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In what system testcase B is failing ?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to share the link of your all submissions for a contest to others

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1
abbb
abbba what should be the ideal ouput in this test case for problem b of this contest

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

rubbish pretest on problem D. How dare you put at most 100 strings in the pretest in a problem which have at most 100000 test cases !!!????

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

I loved the contest despite getting system test failed on B and wrong test 17 on D , I learned to debug my code and it also taught me to test your code on different edge cases before submitting and dont truely be dependent on pretests .

Many people are downvoting due to weak pretest which according to me is wrong .

One more positive thing due to weak pretest is that many cheaters also got system test failed or hacked on their solution as they just copy(cheat). And I guess they are the ones who are frustrated and downvoting lol!.

It's our fault that we cannot come up with correct solution for given problem . Those who understood the problem and solved by themselves will figure out their mistakes and are happy from the round .

And we have div 3 round today to regain our lost ratings :) Learn from your mistakes and peace out !

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a problem with the 26th test point of question F? The code of the person I have used is still wrong.

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

has harbour announced or contacted any winners?

→ Reply