By awoo, history, 6 weeks 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 kefaa2 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

»
6 weeks 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

»
6 weeks 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 :)

»
6 weeks ago, # |
Rev. 2   Vote: I like it -26 Vote: I do not like it

[DELETED]

»
6 weeks ago, # |
  Vote: I like it -63 Vote: I do not like it

My chance to become specialist :-P

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Me,too. Oh...,wake up,i'm just dreaming...

»
6 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Such a long announcement

»
6 weeks ago, # |
  Vote: I like it +308 Vote: I do not like it

»
6 weeks 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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    I agree.In atcoder,in ABC there are often video editorials.Those are very helpful indeed.

»
6 weeks ago, # |
Rev. 3   Vote: I like it -9 Vote: I do not like it

Hope for green.

»
6 weeks 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?

  • »
    »
    6 weeks 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 .

»
6 weeks ago, # |
  Vote: I like it +45 Vote: I do not like it

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it -34 Vote: I do not like it

Thanks to awoo, Roms, adedalic, vovuh, BledDest and Neon for preparing the Div.2 competition.

»
6 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sooo what would be left? Backtrack and graphs?

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

I wish higher problems had higher points :(

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
6 weeks 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?

»
6 weeks ago, # |
  Vote: I like it +58 Vote: I do not like it

My Last brain cell during contest :/

»
6 weeks 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 .

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    No this lockdown has messed you up to be honest!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What about college?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Leaving day after tomorrow but since i am in final year there would hardly be any classes.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your rating graph is so close to mine, surprised to find such a guy

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

I wish I can do well in this round!

»
6 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Delayed by 10 minutes!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

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

    • »
      »
      »
      6 weeks 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 ;)

»
6 weeks ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

Delayed! hope there isn't any issue

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

delayed by 10 minutes..duh

»
6 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

.

»
6 weeks ago, # |
Rev. 3   Vote: I like it -28 Vote: I do not like it

Delayed by 10 mins.Hope the contest to remain rated

»
6 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

10 more minutes

»
6 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

delayed for 10 minutes :(

»
6 weeks 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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Read a book lol

  • »
    »
    6 weeks 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

»
6 weeks 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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it -22 Vote: I do not like it

.

»
6 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

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

»
6 weeks 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 ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

10 mins delayed?

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Last min time extended?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

10 more minutes of TWICE it is :D

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

if(!Contest.IsPrepared) { Contest.Delay(10); }

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i call 10 more minutes

»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

queue issues — MikeMirzayanov Can you please check?

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope to become cyan.

»
6 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

This type of Div 2 B demotivates me very much

»
6 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

bruteForces

»
6 weeks 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

»
6 weeks 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

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why should all be less than n-1 ?

      • »
        »
        »
        »
        6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Thanks a lot! Can you please explain the brute-force also a bit
          [EDIT] Not all situations but just the basic idea

        • »
          »
          »
          »
          »
          6 weeks 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"

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I dont think A and B are almost the same

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you think about this for B

      Code
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone tell how to solve B

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ya Checked other comments and got it! Thanks for replying! :D

»
6 weeks 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 !!

  • »
    »
    6 weeks 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

    • »
      »
      »
      6 weeks 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 :(

      • »
        »
        »
        »
        6 weeks 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...

»
6 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

ImplementationForces

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

UPD:

AC code
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    it == a.end() should come prior to *it I guess.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yeah, and my approach only works when there's maximum consecutive special elements :sob:

»
6 weeks ago, # |
  Vote: I like it +46 Vote: I do not like it

Really bad problems

  • »
    »
    6 weeks 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.

»
6 weeks 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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell the 16 situations?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For problem B I used some if / else. I created a function $$$F (a, b, c, d)$$$, which returns false if it is impossible to satisfy the conditions. In the function I check if two opposite sides have the minimum required amount if the other two sides overlap. There are 4 possible corners that overlap. Then I just check that it satisfies all $$$F (u, d, r, l)$$$, $$$F (d, u, l, r)$$$, $$$F (r, l, u, d)$$$, $$$F (l, r, d, u)$$$. Code: 108921564

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also, in problem A you only need to check 6 situations and find if at least one of them will get a regular brackets sequence :)

    See my code here: 108894342

»
6 weeks 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
  • »
    »
    6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

I hope to become a potato now.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the solution to C a two pointers?

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks 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 :/

    • »
      »
      »
      6 weeks 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 :(

      • »
        »
        »
        »
        6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks 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.

          • »
            »
            »
            »
            »
            »
            6 weeks 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.

»
6 weeks 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.

  • »
    »
    6 weeks 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)

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

VerboseForces

»
6 weeks 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: http://cf.yanyanlongxia.cn/contest/1494/submission/108943905

Thanks.

  • »
    »
    6 weeks 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
    
    • »
      »
      »
      6 weeks 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!

      • »
        »
        »
        »
        6 weeks 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.

        • »
          »
          »
          »
          »
          6 weeks 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

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I understand my mistake now. Thanks for helping !

      • »
        »
        »
        »
        6 weeks 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
        
»
6 weeks 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)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Solution: http://cf.yanyanlongxia.cn/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 ?

»
6 weeks 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.

  • »
    »
    6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Yes sir

  • »
    »
    6 weeks 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 :(

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      how do you know your rating change before finishing contest?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Use CF-predictor plugin or CF rating predictor website

»
6 weeks ago, # |
  Vote: I like it -28 Vote: I do not like it

:'(

»
6 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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

»
6 weeks 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?

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
6 weeks 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 ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You'll also have to check this condition while iteration through the two possibile strings: at any moment, no. of closed brackets should not exceed open brackets Look for this test case, you'd understand why : "ABBCAB".

  • »
    »
    6 weeks 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..

»
6 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

GraphForces

»
6 weeks 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 :)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (unlikely but still happen sometimes)

    It's more likely than you think

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same with other rounds. 1.5hr AC on C <= 15min AC on B.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I don't think it is same with other rounds because in normal div-2/1 and global rounds the scoring distribution are in increasing order and difference between consecutive problems are greater than 250(most of the times it is 500) which gives you enough time to race ahead someone who didn't solve that problem at all.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Point decay per minute for each problem also increases. But anyways, non-decaying scoring distribution with time penalty is far better imo.

  • »
    »
    6 weeks 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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What i'm trying to say is sometimes the solution of a problem doesn't strike to someone and its completely okay but a tougher problem requires more time and skills and that's why it should be more rewarding than the easier ones. This works perfect and that is why div-2/1 and global round problems have increasing points.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    ICPC

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    It is classic ICPC format

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

sent by mistake

»
6 weeks 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.

  • »
    »
    6 weeks 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

»
6 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone help me what I am missing in prob A, I got WA on tc2

Spoiler
»
6 weeks 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??

»
6 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Seems like todays winner is not alone check his submissions.

standings

  • »
    »
    6 weeks 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?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      because both have rank1 due to the same score and penalties

»
6 weeks 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.

  • »
    »
    6 weeks 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

»
6 weeks 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!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks 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

      • »
        »
        »
        »
        6 weeks 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);

        • »
          »
          »
          »
          »
          6 weeks 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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

»
6 weeks 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 ?

»
6 weeks 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 ☹

»
6 weeks 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 .

  • »
    »
    6 weeks 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".

»
6 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

SIMULATION-FORCES

»
6 weeks ago, # |
Rev. 2   Vote: I like it +47 Vote: I do not like it

2021-02-08-1

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it -21 Vote: I do not like it

    But now it got unrated :(

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What? Where did you see this? It's not in the announcement section!!

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it -12 Vote: I do not like it

        Yours is also unrated :(
        Go to see your rating graph or click here

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 4   Vote: I like it 0 Vote: I do not like it

          I think it will be updated soon as i think there is no official announcement. Wait for some time, rating changes for educational rounds take some time.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          oof! That graph shows a contest unrated till the ratings are updated for the contest.

»
6 weeks 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
  • »
    »
    6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

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

»
6 weeks 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)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

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

    • »
      »
      »
      6 weeks 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.

      • »
        »
        »
        »
        6 weeks 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

        • »
          »
          »
          »
          »
          6 weeks 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.

»
6 weeks 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

»
6 weeks 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: http://cf.yanyanlongxia.cn/contest/1494/submission/108965452)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Try this:

    Spoiler
»
6 weeks ago, # |
  Vote: I like it -15 Vote: I do not like it

I'm very vegetable.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When we got editorial?

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Where is my solution for B going wrong?? I am using 4 iterations to go through the 4 rotations of the grid and on each rotation , I am checking the top, left and right cells and decreasing them accordingly. I tried debugging but I cant think of any edge case.. I am also using cu(corners used) array representing each side to check if it's no more than 2 just in case.

Code
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Please upload the editorial..!!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I find editorial for this?

»
6 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Will this round be unrated now?

»
6 weeks ago, # |
  Vote: I like it -22 Vote: I do not like it

2021-02-08-4

»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

NEED EDITORIAL. PLEASE UPLOAD THE EDITORIAL.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That is amazing and it really helps me understand the question better. Thankyou for your help :)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That is also great and really efficient! Thank you!

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

When will the ratings be out? :)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide the testcase 225th of problem 1494A?

»
6 weeks 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 ;(

»
6 weeks 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?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Mine also showing unrated ;(
    If it's rated I could become green :(

»
6 weeks 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. http://cf.yanyanlongxia.cn/contest/1494/submission/108949724 . The tree i have built doesn't seem to have LCA as 4. It should be 5.

»
6 weeks 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
»
6 weeks ago, # |
Rev. 2   Vote: I like it -11 Vote: I do not like it

.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why aren't the ratings out yet(for div2)? Have they made this contest unrated for all?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Are the system tests over?

»
6 weeks 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!

  • »
    »
    6 weeks 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 http://cf.yanyanlongxia.cn/contest/1494/submission/108925449

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

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, your translated version is perfect for me to understand xD!!!

»
6 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Wating for rating changes & tutorial...

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the editorial be out?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I cannot find where I went wrong in 2nd question.

http://cf.yanyanlongxia.cn/contest/1494/submission/108943134

»
6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Guys, please give editorial if not rating changes !

»
6 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Edit: Nevermind, ratings updated!

»
6 weeks ago, # |
  Vote: I like it -32 Vote: I do not like it

Time to downvote the article to get attention.

»
6 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

E was easier than B.

  • »
    »
    6 weeks 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.

    • »
      »
      »
      6 weeks 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.

»
6 weeks 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

»
6 weeks 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?

»
6 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Literally me when edu rounds rating changes appear :)

  • »
    »
    6 weeks 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?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

No eidtorials and no rating updates.... BRAVO!!

»
6 weeks 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: http://cf.yanyanlongxia.cn/contest/1494/submission/109001204 109001204

  • »
    »
    6 weeks 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.

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

    I have done the same.

  • »
    »
    6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when will ratings get updated??

  • »
    »
    6 weeks 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

»
6 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

»
6 weeks 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).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For editorial try this

»
6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

Finally Editorial is out

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

At last!!

Editorial is ready: http://cf.yanyanlongxia.cn/blog/entry/88344

»
6 weeks 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).

»
6 weeks 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.

»
5 weeks 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.