Educational Codeforces Round 105 [Rated for Div. 2]
By awoo, history, 4 years ago, translation, In English

Hello Codeforces!

On Mar/02/2021 17:45 (Moscow time) Educational Codeforces Round 105 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Amazing news once again, Codeforces!

We are especially glad to have a chance to share our scholarship opportunities more often!

This time we have partnered with OneRagtime again to open the door for an exciting career in technology for the most talented people in our network.

In partnership with OneRagtime, we are offering a full scholarship to study a Master’s in Computer Science at Harbour.Space while working as a Full Stack Developer at OneRagtime!

Scholarship Highlights:

➡ Work in Europe’s most exciting tech cities

➡ Scholarship value of up to €31,500

➡ Competitive compensation for the internship at OneRagtime (€800 / month)

➡ Opportunity to join OneRagtime full-time after graduation

Some of the advantages of working at OneRagtime:

  • International team
  • Fast-paced workplace
  • Be a part of the OneRagtime adventure!
  • Be fully immersed in the European tech ecosystem
  • Thrive within a Venture Capital that does things a little differently
  • Work in Europe’s most exciting tech cities

Codeforces and Harbour.Space

We have previously partnered with other companies like OneRagtime, Hansgrohe, Coherra, and Remy Robotics to empower young talents around the world and help them boost their tech career. We’ve already filled a few of the positions with OneRagtime including:

  • Full Stack Developer at OneRagtime awarded to Alejandro Martinez from Mexico
  • UI/UX designer at OneRagtime awarded to Davit Petriashvili from Georgia

We are always happy to see Codeforces members join the Harbour.Space family. Apply now to get a chance to learn from the best in the field and kickstart your career!

Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to evidence student life, events, and success stories from our apprenticeship program students.

Good luck on your round, and see you next time!

Harbour.Space University

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 antontrygubO_o 6 251
1 Pyqe 6 251
3 244mhq 6 260
4 tute7627 6 272
5 Um_nik 6 288

Congratulations to the best hackers:

Rank Competitor Hack Count
1 noimi 11
2 neal 7
3 Origenes 6
4 Kregor 5:-2
5 chilliagon 5:-4
94 successful hacks and 293 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A noimi 0:01
B noimi 0:04
C wygzgyw 0:15
D conan1412yang99 0:16
E thenymphsofdelphi 0:15
F rainboy 0:35

UPD: Editorial is out

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

Comments Comments (248)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -37 Vote: I do not like it

Good luck on the contest everyone!(if you are participating that is)

hmm

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

    if you were red coder then you would get upvote

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

      I know, but what can I say, it's a RED dominant community.

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

Lets hope people(like me) losing rating in Global round can gain positive delta in this round :)

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

[DELETED]

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

My chance to become specialist :-P

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

Such a long announcement

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

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

It would be very cool too see in future video editorial from the authors!

P.S Sorry for bad English.

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

Hope for green.

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

Is there any points system associated with educational rounds and how do successful/unsuccessful hacks affect the points system (if there is one), ranking and the rating?

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

    The person whose solution you back will get deduction of points as his solution will be marked as wrong. You will not gain any point for successful hacking and neither loose any point for unsuccessful hacking .

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

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

    Reality :)

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

    So real for me

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

    Worst Experienced :(

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

    Did you change your PC in the meantime? :D

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

    That feeling when you got a 1500th place in the beginning and tried to solve B problem the rest of the time and you end up in 4000th place

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

      maintaining speed solving is necessary.I was not solving easy problems in last few days.That really backfired

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

    Somebody can explain how to solve problem B

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

      4 corners, each having 2 choices (black/white). Iterate over 2^4=16 possibilities

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

    hhhhhhhhhha

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

Let's just hope that problem A isn't 2 lines of code while problem B requires 3 dimensional dynamic programming and you need to precalculate all the stock market crashes in the next 5 months.

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

I hope there are no adhoc/constructive/geometry/very mathy problems.

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

I wish higher problems had higher points :(

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

.

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

I have participated in 50 contests! Will i be CM before my 100th contest?

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

My Last brain cell during contest :/

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

Ahh life's too stressed ....wake up 12 in the noon pass the time learning algos till 7...then CP till 11 and then Counter Strike till 3 am ,sleep at 4:30 and repeat. I guess i messed up this lockdown .

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

I wish I can do well in this round!

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

Delayed by 10 minutes!

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

    The last time this happened, the round was declared unrated...

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

      The last time this happened, the round was declared unrated...
      Lol.
      Didn't check before posting that I was a newbie again ;)

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

Well, it's delayed. Here we go again)

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

delayed by 10 minutes..duh

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

.

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

Delayed by 10 mins.Hope the contest to remain rated

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

Contest has been delayed so I'm here because I don't know what to do with my life for the next 10 mins.

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

    Read a book lol

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

    We can just pray It starts after this 10 minutes, otherwise we won't know what to do for few more minutes xd

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

What ever the reason of delay is, I hope the contest doesn't become unrated again.

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

.

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

I just pray it don't go unrated.:(

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

why they extend time , it affects mindset of some coders ,what do u think guys ?

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

    you do realize they don't delay it for fun right?

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

oh,a delayed contest may lead somthing unlucky and I hope the contest will go well.

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

10 more minutes of TWICE it is :D

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

I this 10 min I realize how useless I am..

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

Hope to become cyan.

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

This type of Div 2 B demotivates me very much

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

bruteForces

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

I really hated this B because I tried to solve it the wrong way I guess

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

Some one please tell me about process of B i was trying since 1.5 h but i can't find a answer. Please help me to find out the answer

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

    It's almost same as A, just bruteforce the 4 corners (2^4), and check if 4 numbers are not negative and less than n — 1.

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

      why should all be less than n-1 ?

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

        Because you already know the 2 corners for each row/column so you have n-2 remaining cells.

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

          just a thought.

          "2 corners for each row/column so you have n-2 remaining cells"

          If above is the reason for

          "check if 4 numbers are not negative and less than n — 1"

          in your first comment, It's more clear in the first glance if you say

          "less than or equal n-2" instead of "less than n-1"

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

      I dont think A and B are almost the same

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

      What do you think about this for B

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

Can someone tell how to solve B

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

    Brute force cases for corners and fill the edges, then check if it's correct.

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

Gap between B and C was very huge , fucked up in the contest literally fucked up !!

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

    It's actually hard to achieve...

    And It seems that E is easier than D (aftering having a look... XD

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

      Yes it is! Regret not looking at it during the contest while spent 1+ hour on D and got nothing :(

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

        This round seems more educational. :(

        Less dp problems, more implementation problems...

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

ImplementationForces

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

UPD:

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

Really bad problems

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

    Problems were hard, indeed, but I think there is no bad problem.

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

In problem B, you only need to check 4 corners, which is totally 16 situation, and just brute force all of them, If you use if else... if else..... you will probably get WA till the end.

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

My impression when i see the accepted on B after 1.44 hour continuous trying xD .. I am getting negative delta but still happy xD

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

    You can just check the minimum number of blocks that should be black in the border columns. You can check my submission for more clarity.

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

I hope to become a potato now.

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

basically https://codeforces.net/blog/entry/88284?#comment-767085

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

Is the solution to C a two pointers?

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

    Either two pointers or binary search (I think the latter is easier).

    The main idea is to split the line on $$$0$$$ to get two independent problems. After that, suppose we are pushing blocks to the left (solve the part with negative coordinates). We should push them so the last block we pushed coincides with some special position. We can iterate on this position, calculate the number of blocks we push with, for example, lower_bound, and then calculate the number of special positions in the resulting segment of blocks with another lower_bound.

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

      Thanks a lot! I think the binary search is easier to implement. I spent 1h 50min on C, and I just realized one variable was misswritten. Got AC with the two pointers idea :/

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

      Oops !!! I was trying to coincide the first block with some special position and got around 10 WA on pretest 2 :(

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

        Could you tell me any test case, why matching the first block to some special position leads to non optimal solution.

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

          I think there is nothing wrong in putting the first block in the special position. But it was difficult for me to track how many blocks will be one after another from the first block which I realised after the contest. I think both approaches are correct.

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

            Yes, I got AC by placing the first block in the special position.

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

Hey,is there any reason why we had to use complicated language like supervisor etc for Probelm-D? Stating it simply in graph theoretic terms like "There exists a rooted tree, each node has has a number and a value. The value of each node is strictly greater than the value of each of its children. You are given the number of leaf nodes and the value of the lca node of each pair of leaf nodes. Construct any such possible tree". I was so confused for so long thinking the given values for each pair was the minimum of direct supervisors.

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

    Most problem setters have majored in literature and they don't want us to forget that fact. (EDIT: Just kiddin)

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

VerboseForces

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

In D, I did the following: if two vertices' common salary is the maximum overall, it means that the root of their tree must have that salary. Thus, we can start with an initial set of leaf nodes, and split them into two sets according to which ones have the max common salary or not. Then create a new root node and recursively process the two sets.

Is that approach incorrect? I can't find a counter example :(

Here's my submission: https://codeforces.net/contest/1494/submission/108943905

Thanks.

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

    One vertex can have more than 2 sons. Test:

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

      Could u please help me in finding the error in my logic as well?

      I claim — "That every distinct value written in the 2D array is a new node in the tree"

      Let's say, that for some val, which is connected to nodes $$$a0,a1...ak$$$, we will create a new node and make top_most_parent[a0], top_most_parent[a1],... top_most_parent[ak]=node.

      The idea is motivated from the idea of LCA itself, which is, that the $$$LCA(a,b)=parent(topMostParent[a])=parent(topMostParent[b])$$$

      It seems, that Ashishgup also implemented the same idea. I don't know what went wrong.

      Link to my code

      Link to Ashisgup's code

      Thanks in advance!

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

        I havent look at the code, but there csn be many nodes with same value.

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

          Do you mean to say, that for some value val, instead of having just one new node, we might have more than one new nodes?

          I think in that case also, we can create just one single node

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

          I understand my mistake now. Thanks for helping !

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

        Well yeah, there can be many nodes with the same value. Test:

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

Screencast with commentary (the quality will get better when YouTube will process it)

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

Solution: https://codeforces.net/contest/1494/submission/108942229

Input

3
2 5 7
5 1 7
7 7 4

Participant's output

5
2 1 4 5 7 
4
1 4
2 4
3 5
4 5

Checker comment

wrong answer LCA of 1 and 3 is 4 and c[4]=5, but a[1][3]=7

LCA of 1 and 3 should be 5 but checker says that it is 4. Is there anything wrong ? Is my output format is wrong ?

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

I solved A and B in a similar manner (brute force). For A, I iterated from 000 to 111 (Binary) and checked every possible string b. For B, I iterated from 0000 to 1111 (Binary) and checked all possible black intersections.

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

    Thanks for reminding bitmask idea, I brute forced using recursive functions which was more messy to code.

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

it was a bit different. did anyone else get stuck in B?

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

    Yes sir

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

    In my case, not only was I stuck at B for almost two hours, but also I have a -130 rating change :(

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

      how do you know your rating change before finishing contest?

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

        Use CF-predictor plugin or CF rating predictor website

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

:'(

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

i thought i should output number of edges in problem D :(.

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

Why sometimes "out of bound" gives WA and sometimes RE for the same compiler on codeforeces?

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

I think the last educational round was very easy than this one.

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

what's the wrong with my idea of problem A.. My idea was in a greedy fashion. every balanced parenthesis start with ( and ends with ")". so I checked s[0] and converted all of with "(". then I checked s[n-1] and converted all of them with ")". then, there is only one character(A or B or C) in S. at first, I convert that with ")". after that with "(". then, checked the validity for this two options. But wrong answer. my submission may you help me ?

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

    Maybe you missed the case where s[0]=s[n-1]

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

    Its because you may get cnt as negative that means you will have more number of closing brackets than the opening one which is not true..

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

GraphForces

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

I know it might be out of context but I wanted to say this for a while.

I think the point system in educational round(also div-3) is a bit unfair. All of the problems are assigned 1 point even though they are in increasing difficulty. For instance if somebody has solved problem A and C but not problem B (unlikely but still happen sometimes) then his ranking would be similar to someone who has solved A and B but not C. Even though the first person was able to solve a tougher problem(theoretically and practically) he is still in the same position as the second person which seems unfair to me.

A problem with higher difficulty should have more points, For instance the score distribution in Edu and div-3 contests should be 1,2,3,4,... so on. What's the problem with this score distribution? Maybe I'm missing something.

Open to criticism :)

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

    (unlikely but still happen sometimes)

    It's more likely than you think

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

    If the first person couldn't solved the easier problem then apparently it wasn't an easy one for him. If he could solve the easier problem he should have solved it, since he already know the rules before the contest. Even though the first person was able to solve a tougher problem(theoretically and practically) he is still in the same position as the second person which seems unfair to me

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

    ICPC

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

    It is classic ICPC format

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

sent by mistake

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

For Div 2B,

Can anyone please help me with the testcase where my code fails? 108917717

I am unable to understand the issue with my code.

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

    Try this case:

    1
4 3 1 3 1

    Your Answer : NO Actual Answer: YES

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

.

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

    Try with ABBAAC. Your code thinks that ())(() is okay.

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

many of the solutions of F can be hacked with the case

6 7
1 2
1 3
1 4
1 5
4 5
4 6
5 6

there seems other hack case for other participants which couldn't hack with this case too. Is the testcases prepared for the system test strong enough??

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

Seems like todays winner is not alone check his submissions.

standings

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

    Why do you say That he is not alone! am I the only one who didnot get it?

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

      because both have rank1 due to the same score and penalties

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

One of shorter solutions for B obtained by factoring out symmetries: 108950466 -(Perl). Idea was to squeeze all posible corner cases. I.e. consecutive n 0 is impossible, and it is symmetric to 0 n in reversed direction.

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

    I don't know Perl but your submission looks like it's begging to be hacked

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

Can someone tell me case number 78 in test case 2 for problem C? Here is the link to my submission that fails at 78th test so can't figure out why. Thanks!

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

    Same

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

    Hi, i got the same wa, and found that case (isn't the 78th, but breaks the code)

    1

    4 5

    1 2 4 6

    4 5 7 15 17

    Correct answer it's 3.

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

      can you help me out with case 126 of TC 2 in problem C. Here is my link to submission

      My Approach:

      Divided the problem into two parts (1. positive 2. Negative). solve the negative part in the same way as positive. positive part ( made 2 array for positon to be kept/ special position(sp) and original position our block(p) ) 1. I made a suffix array of already set blocks.

      1. Traversed through the sp(i = 0 to i < len(sp)) and lowerbounded on p with sp[i] those whose position is <= sp[i] , say found the val at j(index in p).

      2. lowerbounded on sp with sp[i] — j (which would give us the maximum contiguous block such that some or all of them are on special position having end at sp[i]), say found at k.

      3. the no of blocks satisfying the condition = k-i+1+bolcks that are alredy on the special position after this position(suf[i+1]).

      4. found maximum for all all indexs

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

        The idea it's okay. But your code has a little a bug:

        ll j = lower_bound(p.begin(), p.end(), sp[i]) — p.begin();

        if(p[j] > sp[i]) j--;

        if sp[i] it's bigger than maxValue on P, then your code will access to an unkown position. Same for negative one.

        You can fix it by put this before the iteration:

        p.pb(INF); n.pb(INF);

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

          ohhh, I thought of that secenario but for some reason i always thought it would be handled automatically.

          thank you , For clearing my doubt.

          Will keep this in my mind next time.

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

      Thanks!

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

How to overcome pain in ass when you keep getting WA on test 2 after implementing for almost 2 hours ?

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

Today I waste 1.5h to solved problem B but still I can't solved it. that's make me ☹

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

Realy bad contest ,, its just about hard implementation not about problem solving. also late editorial .

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

    I think that's why it is educational. A lot of "how to get that parts right...". Not so much "lets have fun".

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

SIMULATION-FORCES

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

2021-02-08-1

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

In B, I am trying every possible move by recursion

can anyone point out what's wrong in it ?

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

    Your code is giving YES for this but I think it's wrong.

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

Please share some memes I can laugh at; to ease the pain.

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

Competitive compensation for the internship at OneRagtime (€800 / month)

A non-intern student can earn twice that amount while doing less work. What a joke! (assuming internship = 40 hours/week, location = Paris|Barcelona)

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

    In which country/city? Tell me, I am interested to relocate

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

      In most western EU countries, Germany, France, Ireland... you can check the minimum wage across these nations which is compulsory as long as the word 'intern' doesn't apply.

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

        Well, for a western country or a big city, the 800 Euro sum doesn't seem like something big. In my city though, it's three times the average salary

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

          The same for my home country (enough for 1 year of living if you live in the village) but what I am trying to criticize here is the fact that they are exploiting student labor. An intern is practically just a student but the pay gap is huge because it is compulsory in their curriculum even though the work is similar.

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

How many of you think that awoo was better as the coordinator for edu rounds.

PS I thought pikmike !=awoo

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

What is the expected solution to problem F?

I thought about the following one, but it recieved WA on test 19:

  1. If the graph contain 2 or 0 odd degree nodes, just find an Eulerian Path.

  2. Otherwise, I claimed that: It is not possible to start a shift on node U, go to neighbor V and dont return to U immediately. Suppose that we went to node V and didnt return to U immediately. This means we didnt deleted the edge (U, V) so we must delet it later. Then, we will traverse a path that goes back to U, using the shift, implying that there will be edges on this path that will survive, leading to a contradiction, because we would never destroy all the edges of the graph.

Then, it follows that: After some "Eulerian Path" that ends on a node U, the remaining graph must be a star centered on U. Is this solution incorrect? (There are some cases regarding to the part of the code that finds the possible star, but is all coded here: https://codeforces.net/contest/1494/submission/108965452)

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

    Try this:

    Spoiler
    → Reply
»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

I'm very vegetable.

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

When we got editorial?

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

Please upload the editorial..!!

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

Will this round be unrated now?

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

NEED EDITORIAL. PLEASE UPLOAD THE EDITORIAL.

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

How to solve problem A. Iam new to this please help

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

    So given a string, we need to check if it will be a regular bracket sequence,

    We can only use '(' and ')' to replace the characters of the string, it is also mentioned that all the A's should be replaced with the same bracket, all the B's should be replaced with the same bracket, and also all the C's should be replaced with the same bracket, this narrows down the problem much more, for any bracketed sequence to be a regular bracket sequence it needs to start with '(' and end with ')', this can only happen when the first and the last characters of the string are different so that all the occurrences of the first character can be replaced with '(' and all the occurrences of the last characters can be replaced with ')'. If this is not the case then it is not possible. So for now replace all the characters of the string as given above, after this there exist 2 cases:

    1. All the characters of the string are converted to brackets i.e., the string contains only 2 unique elements. Here just write a function to check for a regular bracketed sequence. and pass your string into it
    2. The string contains 3 unique characters thus there are characters that have not been replaced with brackets. Here first replace all occurrences of the unreplaced character with '(' and pass it into a regular bracketed sequence checker, if it returns false, replace it with ')' instead and pass the string into the regular bracketed sequence checker.

    well, that is it :) my method is a bit lengthy and brute force-y haha but it gets the job done, comment if you did not understand anything.

    Solution my code in python, ignore the staring wrappers and functions the solution is from the checker function.

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

    See my comments above

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

When will the ratings be out? :)

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

Is this round unrated? For the first time I got 4k rank and now my rating doesnt change ;(

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

It was rated for div 2 but why it is showing unrated to me?

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

Can someone help me figure out why is the first pretest failing for me for Problem D. https://codeforces.net/contest/1494/submission/108949724 . The tree i have built doesn't seem to have LCA as 4. It should be 5.

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

Someone, please tell me why is this code failing for B 108907428

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

.

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

Are the system tests over?

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

How to solve D? Please if someone knows explain it! Thanks in advance xD!

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

    Put pairs of points with the same point weight in a vector and enumerate the point weight from smallest to largest. Maintain a merge set, and for point pair (i,j), get the ancestors x and y of them. if they are the same then skip. If one of them has the same point weight as the currently enumerated point weight, then connect the other point to that point. Otherwise, a new point is created and both x and y are connected to the new point.

    You can see ny code at https://codeforces.net/contest/1494/submission/108925449

    Sorry that I'm Chinese and I use DeepL to translate. Never mind the mistakes in my words.

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

Wating for rating changes & tutorial...

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

When will the editorial be out?

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

WAITING FOR RATING CHANGE .....2 HOURS LATER........ WAITING FOR RATING CHANGE .....2 DAYS LATER......... WAITING FOR RATING CHANGE .....2000 YEARS LATER..... WATING FOR RATING CHANGE

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

Guys, please give editorial if not rating changes !

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

Edit: Nevermind, ratings updated!

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

Time to downvote the article to get attention.

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

E was easier than B.

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

    We had a similar question in Round 699 ( I guess it was D). So E was even more easier because of that.

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

      I was wondering If I have seen this before. Yeah, it's almost the same.

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

Me : getting positive delta and waiting for the rating changes

Mike : It's time for another test

Me : What's that ?

Mike : Patience Test

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

Why edu rounds take too much time updating rating even after hacking phase?

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

Literally me when edu rounds rating changes appear :)

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

    Does it take this long for every Edu round or is it only because we had a delay this time?

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

I think I have a short greedy solution for problem B (as it passes system tests).

This is my solution: The variables na, nb, nc, nd (in my code) represent the number of black cells left after taking away the black cells that also belong to other sides. So, if there is a side with n black cells, I reduce each of the two variables that represent adjacent sides by 1. If there is a side with n-1 black cells, it means there is one or two sides that share with it a black cell. I greedily reduce only one side — the side that has more black cells left. I return "YES" only if none of the variables has become negative.

Has anybody done the same? Was this intended to work? Link to my solution: https://codeforces.net/contest/1494/submission/109001204 109001204

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

    Yeah, mine solution is the same as yours and it passed the system test too.

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

    I have done the same.

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

    Same here, tho I made the picking of the side to add 1 black cell to for a side with n-1 black cells a little complicated. And i wasn't also sure if it works starting from any random side, so i looped, the algo to run 4 times starting from all sides then checking the one that works.

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

when will ratings get updated??

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

    when the next Halley's Comet will be seen... You will get your rating! XD

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

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

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

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

For editorial try this

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

If the rating change system is slow, you could release it as a problem for the next Div 1 contest and get 1000 better algorithms.

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

At last!!

Editorial is ready: https://codeforces.net/blog/entry/88344

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

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

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

Is it rated?

-- The contest seems to be under-rated.

The round hadn't much lags and hadn't long queues. It had nice problems, all seem original, having wide diversity. B wasn't about implementation, but about logic and patterns, solving of which reduces implementation difficulty.

Thanks for organizers team.

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

I published my code on ideone.com with default settings as public. It was a coincidence. Please restore my ratings. I'm just a newbie so I didn't know much about this. I'll take care about this in future, I'm so sorry.

→ Reply