vovuh's blog

By vovuh, history, 4 weeks ago, translation, In English,

<too-old-joke-about-copy-paste>

Hello! Codeforces Round #656 (Div. 3) will start at Jul/17/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round. Also thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for the discussion of ideas and testing the round!

Good luck!

</too-old-joke-about-copy-paste>

UPD: Also thanks to infinitepro for help with statements and testing the round!

UPD2: Editorial is published!

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

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

will it be rated??

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

Third unrated round for me in a row :(

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

    codeforces nowadays .

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

      I can relate and I bet every beginners like me can relate as well :(

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

        Hi, i'm new, how do i know if a round is rated or not?

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

          It is written in the contest announcement, and if the round becomes unrated there will also be an announcement saying that. But most rounds held are rated.

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

          A contest is generally not unrated unless the announcement says so.

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

          Hi... Welcome to Codeforces buddy.. I hope you got your answer and sorry for being late :(

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

Monogon contest again got rescheduled :(

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

    It's good that it got rescheduled. Would have been sad if it became unrated like the previous two rounds.

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

I think they are running this round because they think there will not be a crash and an infinite queue. looking forward to it

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

Codeforces is my new School ... teaching me and hosting Contest :XD Thanks a lot CodeForces!!

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

    Edit: Sorry for the spelling mistake

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

      грамматика

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

        Can you please translate it to english. I don't understand russian

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

          Grammar*

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

          It should be ""Russian" ,not "russian".Grammar Nazi

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

            I don't think this is a grammatical error.

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

              Don't provoke a Grammar Nazi That's like the top rule of what not to do

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

              A proper noun must have its first letter capitalised. This is a rule from English grammar

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

    Your profile picture correctly depicts you :)

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

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

"the round will be rated for you." Hope this time,,, this line will be true for me..Btw Thanks for your hard work..

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

Deleted

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

Hopefully this wont be unrated !!

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

I was eagerly waiting for the announcement :)

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

Let's all pray for smooth conduction of this round.

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

It was better make a test round before real contest :D

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

    There is one testing round arranged, it will start in ~45 min. check here

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

      thanks i didn't see that :)

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

This will be my first ever time competing.. any pointers?

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

Situation or system in last 2 rounds.

hope all will be fine this time :)

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

I hope MikeMirzayanov resolved the problem..

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

Why there is unusual time for round 657 ?..

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

    May be authors comfortable with that time.

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

      Codeforces contest time are generally xx:05 or xx:35 according to GMT. But that rounds scheduled at 09:00 GMT(not 09:05). So that i assume that round is tied with some other contest(may be some onsite contest).

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

        on july 19 there is the cookoff on codechef. maybe to avoid a clash

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

good set of questions :)

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

I will try my best to improve my skill in this contest :)

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

Eagerly waiting!

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

</too-old-joke-about-copy-paste> not too old for me :D

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

To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of >>> 1900 <<< or higher in the rating.

I believe this is incorrect :)

Edit: Nevermind, just noticed it's the same in previous rounds. There's a different limit for being a trusted participant and being ranked. Sorry for the noise.

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

hopefully it will be rated.....

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

Hi guys,we have a free contest for you.....

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

Hoping that this contest goes on smoothly _____

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

Everyone is waiting for this round eagerly . Hope this is gonna rated ultimately .

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

Who could tell me how to remove or report that comment?so dirty..

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

Is it rated? . . . Hope the answer is "YES" :-P

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

i'm coming back to this site after a break of 3+ years. so i'm new to this "12-hour open hacks" system.

firstly, is it something new? or has it been a regular thing in contests recently?
also, does it mean there will be a kind of "hacking phase" which lasts for 12hrs after the 2-hour "coding phase" has ended?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +21 Vote: I do not like it
    1. It's a regular thing for div.3 and Educational Rounds.

    2. Yes.

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

      oh this is new for me ... i guess we would need to solve the problem (or atleast, pass the Pretests) in order to hack other participants' solutions?

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

        Nope. You can hack any problem, even if you didn't solve it.

        What's more, sources can be copied for local test.

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

    dolphins returning to Italy and footballers returning to CodeForces, Cool!

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

Hoping positive delta change for all :p

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

    That literally can't happen afaik.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      What If everyone has exactly the same rank(same score with same penalty).

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

        even then the higher rated participants will have a negative delta while lower rated ones will have positive

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

        Everyone will get 0 rating change.

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

Nice

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

I believe there should be a half-hour unrated short contest some time before the actual contest, to test the system's current load handling capacity.

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

I love how many people in the comments section are self proclaimed memers

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

I hope I can solve all the problems :-D .

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

As a tester, I won't say anything, since you already know how good vovuh contests are!

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

Hope atleast first problem do not take time.

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

really excited for this contest. I just hope it doesn't get ruined unlike past few contests. Looking forward to learn a lot from Vovuh's tasks.

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

    Try not to tag the person unless it's needed

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

why is the time extended 15 min?

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

    i guess because number of problems will be more then usual that is 7 or 8

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

Good luck and high rating to everyone! :)

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

lol, why did they make it 15 minutes longer?

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

    guess everyone understands this now! self explanatory.

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

      Wasn't before the contest. It pretty much messed up my place. But it is fair, There were just more problems than usual.

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

Hey, I don't think this is right:

  • do not have a point of >>1900<< or higher in the rating.

Although you can find this sentence after it:

if your rating is less than >>1600<<, then the round will be rated for you.

I think this may puzzle those people who are new and without any experiences before in Codeforces.

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

23k registered, let's hope for the best with the queue.

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

Seems more like a Div2 than Div3

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

Great contest, thanks a lot for this, now I see what vovuh hype was about.

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

Deleted
Just realized 2^26 is more than 200000 lol the meme is pointless

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

    living in a country with a different number of alphabets surely make you confuse

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

how to solve question D???????????????

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

    Just brute force with recursion.

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

      what will be the time complexiy in that case

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

        O(2^logn) i guess

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

          Simple bruteforce . set l=0 , r=n-1 , mid=(l+r)/2 , at each moment you can either change range [l,mid] to current character or change [mid,r] ; Time complexity : O(2^log2(n)+26n) which is O(n) Ps : O(26n) to compute prefix sums of occurences of each character .

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

          O(2^logn)=O(n)

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

          With every time using "count", it should be O(n*2^logn) which is equal to O(n^2) right?

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

            Actually length of string is also halved each time. It could have been precalculated,it thinked this way also, but realized that count within solve() is better in term of time.

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

              Oh yes, for all first log(n) characters we can precalculate it. Nice.

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

    Divide and Conquer, complexity should be O(n), because each character would be counted at most twice. (I am not sure about the complexity part tho)

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

      yes, it´s $$$O(n)$$$. Look: let $$$T(n)$$$ be the amount of operations for an array of length $$$n$$$.

      $$$T(n) = 2\cdot T(\frac n 2) + O(1)$$$, for $$$n > 1$$$.

      $$$T(1) = O(1)$$$.

      if you solve this: you´ll get that $$$T(n) = O(n)$$$

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

My solutions (untested, but overall ideas should be right):

A
B
C
D
E
F
G
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in D do you need the prefix sum? since it will iterate in ln(n) anyway?

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

      I did D without prefix sum

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

      no, it's not needed (although I used it), look:


      int cost(int i, int j, char c){ int res = 0; while(i <= j) res += (s[i++] != c); return res; } int solution(int i, int j, char c){ if(i == j) return s[i] != c; int mid = (l+r)/2; int s1 = solution(i, mid, c+1) + cost(mid+1, j, c); int s2 = solution(mid+1, j, c+1) + cost(i, mid, c); return min(s1, s2); } /// inside main() cout << solution(1,n);

      This has complexity $$$O(n\cdot \log n)$$$, so it is fine. If you want to do it linearly, use a prefix sum to compute the cost.

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

    is DP was necessary in question D or normal recursion will work

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

      Bruteforce recursion works in just 30ms

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

      Actually, simple recursion does work. Oops.

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

        I am not understanding why my solution to D is giving TLE when I don't use s.substr() and instead pass the limits in the function(Link to submission) and gets accepted when I pass the substring to the function(Link to submission). Can anyone tell me the reason for it?

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

          Passing a string to a function passes it as a copy if you don't take the reference as the attribute and hence it leads to a O(n^2*log(n)) solution which is TLE. Instead, when you pass the substring, it is of the same order as the number of operations in your for loop and the complexity is not affected. You can instead do:

          int func(string &s,int st,int ed,char c)

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

            Thanks!

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

            Thanks sayam! I had the same doubt!I even used prefix sum still I got TLE, was unable to understand the issue.

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

            it is even better to take to string as a global variable

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

            Can you please elaborate?

            I got TLE on my first submission which i thought was having O(2*logn) as time complexity, after reading your comment i just changed (string s) to (string &s) and boooom the sol got accepted :(

            Doesn't that change only affect the space complexity? How time complexity is getting affected?

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

              creating a copy of a string of length n takes O(n) time and O(n) extra space. (this happens if you call by value) which when done over n times gives time complexity O(n^2).

              & operator in parameter name helps it to pass by reference, (as if using the same string but with a different name) so no time or space required.

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

                Thanks bro ! But understanding that it takes O(n^2) time (if we call by value) took me some time .....finally understood :)

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

      Normal recursion will work

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

    For D you can also try every possibility of the good array and find the minimum answer from all possibility. The total possible good array will be n

    Solution

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

      How did you come up with the number of good arrays for a given n? I thought there is only n good arrays for a given n...

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

        Yeah! Thank you for pointing out. I just recalculated, It should be n. My math sucks.

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

    Can you find a counterexample of my submission for E?

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

    can you please tell me what's wrong with this solution https://codeforces.com/contest/1385/submission/87150269

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

    I used the local minimum approach on C but getting WA on test 876 pls help

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

Was G component wise 2-SAT or there is a easier approach to it?

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

    The easier approach is just bipartite coloring. You just need to build a bit special graph to apply it.

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

      Thanks for such an amazing contest, enjoyed it a lot. :)

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

That was an amazing contest! Thanks Vovuh

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

    Its Problem E I think. Also it shattered me when I cam to know that a good problem can be googled easily.

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

    Ohhkk.. So whosoever read that article just had to implement it.

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

Is it me or the contest was at a bit higher level than usual Div3?

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

This can help you with first 4 problems. https://docs.google.com/document/d/1Fq4UAJBh9Tn48hiF6bLzwvl7ce5XikqWeFmFfw1Q0OE/edit?usp=sharing

Help me with the last 3 problems.

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

How to solve E ?

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

Used binary search for C. If all elements after i-th index form a good array, then check set high to i and repeat.

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

G was implementation heavy i believe.

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

Okay , my rating got fucked up again anc I need a quick editorial now.

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

My Solution to C , i try to provide a proof of the solution too . Hope You like It.

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

in D I forgot to call the string by reference and got one TLE omg

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

    Just realized what I was doing wrong after reading your comment. Big facepalm! I usually always pass things by reference.... F

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

      And here I am trying to use DP, thinking my solution is too slow instead of passing string by reference :(

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

Did anyone solve F with dp on trees + rerooting technique ?

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

    I solved it by using the same technique . You can check out my code.

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

I think there was typo while naming the round It should be Codeforces Round#656(Div 2)

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

https://codeforces.com/contest/1385/submission/87160668

Can anyone tell me what's wrong here? I guess the complexity O(n),still giving TLE.

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

    What is your expected time complexity for memset?

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

    First thing is you should pass string by reference otherwise even if it is right you will get TLE, but even after that your code gives TLE, so there must be some other problem.

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

    Here's your AC, don't use memset in this case as there are many test cases and you are resetting the whole prefix array. Also pass string by reference. https://codeforces.com/contest/1385/submission/87164492

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

Is there anyone who solved E without topological sort? I tried with dfs but getting WA on test 2.

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

    I did. First check for cycle with directed edges. If not found you can always direct the undirected edges and still have an acyclic graph. I had two adjacency lists, one for directed edges and the other for undirected edges. Have 3 states each for visited, completed and not visited separately. In a dfs run from a vertex, if any of the undirected edge is directed to a completed vertex, then this can never be a part of the cycle. So remove this vertex from the adjacency list of the completed vertex. Code : 87141053

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

    Check out my solution to Problem E using basic topo sort :)

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

D is annoying complecated statement. Once understood the defintions it is "implement what statement says".

Not sure why such problem is in the set. From my point of view the most idiotic kind. It is not more than decypher obfuscated problem statement.

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

    I don't think so, you have to think a little bit to solve D, and the statement is very clear to understand. I see no problems with task D.

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

    D is pretty interesting (to me) and i found no complication in understanding the problem statement. And thanks to the author, I learned a new thing that passing by reference do makes a difference in time complexity

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

Tasks were interesting, more div 2 than div 3 in my opinion.

Only thing I do not like, that you are allowing more than two occurrences of same element in $$$G$$$. That is not funny joke.

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

    Yep, I thought it could be stupid because it is the only case when $$$-1$$$ appears, but now it's too late to change anything.

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

      Problem G test case:

      5
      5 3 5 1 4
      1 2 3 2 4
      

      ans:

      2
      1 2
      

      why it is wrong? help please :)

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

        If you swap columns $$$1$$$ and $$$2$$$, you get $$$a_1 = [1, 2, 5, 1, 4]$$$ and $$$a_2 = [5, 3, 3, 2, 4]$$$. Both rows are not permutations.

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

          see the other way, I am swapping 5 from 1st with 2 from 2nd i.e [2,3,5,1,4] n [1,5,3,2,4]

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

            You are not allowed to perform such operations. The element can't change its initial column.

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

              I am sorry, I thought we are swapping values of two colns, must have read understood the question wrong. sorry for trouble :(

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

    Wasn't that included in the samples?

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

      Yeah, you are right. I have noticed it after contest. I had another case when I expected ans to be $$$-1$$$ (and that situation is impossible, except case where more than two numbers are equal). I need to check samples more careful.

      Anyway, still it is not funny :)

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

What is the proof of E sol.?

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

can someone till me the difference between this submission 87132940 and that 87161171 I thought that they are the same idea, but I don't know why the first submission failed

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

My solutions :

A. Iterate on all possible triplets from set of numbers 1, x, y, z, 1e9 for each a,b,c, and check if a given triplet exists that satisfies the given condition

B. Take only first occurrences of each number while iterating make the permutation

C. One obvious way to generate array c is to always take minimum end element of the array and generate the final array. So as we move right, we get a smaller array and better odds to generate a valid array c. So binary search on the answer from range(0,n-1) and check if array C formed by above method is correct.

D. To build the answer for (1,n,c), we obviously need the answers for the range (1,n/2,c+1) as well as for (n/2+1,n,c+1), so either use memoization dp or just build the answer for each character for a range recursively, ie, for (1,n) for 26 characters, build the answer for (1,n/2) and (n/2+1,n) for 26 characters each. Then generate answer for each character for (1,n) using conditions described in the question.

E. An observation was that if there is no cycle in directed graph using only directed edges, then all other edges can be directed to avoid a cycle. One such orientation is to direct edges on the basis of topological sort. So check if graph built using only directed edges contains cycle, and if it doesn't ,generate a topological sort from that, and order edge nodes on the basis of topological order.

F. An observation was that if at some time we have k leaves for a node, or k leaves for many nodes, it won't affect the answer's maximum if we decide to do operation on any such valid node because if leaves of that node stay, then that node is as good as unusable node at any point in the future. So a possible algorithm is to take the node with highest leaf count, remove (cnt — cnt mod k) leaves and hence do floor(cnt/k) operations, where cnt is the count of leaves attached to that node. We can do this by maintaining the adjacency list, adjacent leaf nodes list, and leaf frequency list and a set to store the node with highest leaf count and updating these as we pop elements from the set.

G. I did this using bipartite graphs. First we check if each value from 1 to n has exact frequency of 2 for making 2 valid permutations. If so, build a bipartite graph where nodes are pair of (row,column) for each value. 2 nodes are in disjoint parts(of bipartite graph) or have edge in between if they are either in the same column or have the same value. Build this graph, and check if it is bipartite. If it is, then an answer exists. To find the optimal answer , let s just find the cost for a connected component. It is the minimum of the cost of moving one disjoint part of the component to row 1 and the adjacent part to row 2, and vice versa. That is where implementation might become a bit heavy.The total cost is the sum of cost for each component.

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

    master_noobie How do we prove this observation for E?

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

      1 -> 2 -> 3 -> 4 -> 5 -> 1 and an undirected edge between 4 and 1. Be it 4 -> 1 as final or 1 -> 4, either one gives you a cycle.

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

      Consider the graph with only the directed edges. If there is a cycle, then obviously we can't remove it, so the answer is NO.

      If there isn't a cycle, then there exists a topological ordering of the nodes, that is an array $$$pos$$$ such that if there is a path from node $$$u$$$ to node $$$v$$$, $$$pos[u] < pos[v]$$$.

      Now consider an undirected edge $$$(x, y)$$$ and assume WLOG that $$$pos[x] < pos[y]$$$. Then if we direct the edge from $$$x$$$ to $$$y$$$ and add it to the graph, the topological order of the new graph remains the same as the topological order of the old graph (there are a few cases here I guess, but nothing difficult). Thus, since the order still exists, there cannot be a cycle in the new graph. Thus after directing and adding all the undirected edges in this way, the resulting graph will have no cycles.

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

Thanks for such a nice problemset vovuh :)

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

Here are my solution ideas for all problems if you are waiting for the editorial. (video published after the contest ended of course). It is possible that my idea for F isn't actually right; I don't have a proof for it yet.

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

Why is this submission wrong? 87125487 It passes the tests if I clear the dp array, but it should not affect the answer, if I understand resize() correctly.

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

    Resize does not reset the existing values in a vector. It only expands/shrinks the tail to match the new size.

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

      Thank you, I found the bug. I kinda knew that, but for some reason thought that it only concerns values (not data structures, and new values are initialized, but old values stay the same), but vector is also a value. This bug has ruined several contests for me, and I am very glad I finally tracked it down.

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

I will be adding detailed editorials for CF problems with appropriate proofs and implementations on my YT channel

Editorial for problem C: https://youtu.be/vjRHaZb16bU
Editorial for problem D: https://youtu.be/9gVpnosPKec
Editorial for problem E: https://youtu.be/yn6ZPaqwlso

Enjoy watching!!

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

Thanks for the contest, in Problem D — I did learn that passing strings to recursive function can lead to TLE, so pass reference :(

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

Wait is it unrated??? when did it change to unrated???

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

Editorial kidhar he — pappi bhai

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

Very interesting tasks!! Almost every task required something new. Now after seeing solutions of E, i am awestruck with the use of topological sort in it.

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

can anyone tell me whats wrong with my code? Problem C https://codeforces.com/contest/1385/submission/87169051

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

can someone explain why i am getting TLE in problem D here is link to my code https://codeforces.com/contest/1385/submission/87163991)

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

vovuh ZeroAmbition Pikmike

d_rushabh is hacking the solutions that he submitted using his fake accounts. Remove him from the contest.

+adding similar contestant: mihirarora

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

    I think he doesen't know that in div. 3 rounds you don't get points by hacking. If he hack all his alts, I guess there is no problem then

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

      i_say_what_i_want Where is that mentioned?

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

        In div. 3 rounds you don't get points if you hack someone. Also, if all his alts gets 0 problems solved, then they won't change the rank of contestants, then, it wont change other contestants performance or rating change.

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

    I hope you know the fact we don't get points by hacking in div3. I never tried "hack" earlier and wanted to know how does it work. So I tried it in the contest where it is meaningless. I hope you understand the fact! @spinbot

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

I have tried to explain my approach for E , basically explaining the code for topological sort .

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

Can anyone tell what is this code wrong for solution of Problem B? I take all integers in permutation1 until next integer of permutation2 appears. But it throws wrong ans.

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

    There is a possibility that when you increase the value of j, it might become more than the last index of B and the value at that memory location might be equal to the next A[i], in this situation your code will skip that value and might give you the wrong permutation.

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

Hacking problem B gives the following error:

codeforces Validator 'validator.exe' returns exit code 3 [FAIL Unexpected character , but ' ' expected] line 3

I'm terminating each line with '\n'. Validation fails for this: 1 2 3 1 2 3 which is the first test case being terminated by '\n'.

Anyone knows about this?

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

8 bbaaddcc explain this pls

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

Isn't it strange today's contest E question is my doubt post on codeforces only that has been answered ? https://codeforces.com/blog/entry/68765

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

    It is imposible to check your problems against all other problems in the world, especially if they weren't actually published in an OJ. Of course this shouldn't happen, but in general it is common for easy problems to collide with each other.

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

Can somebody help me in question E .My code is giving error on test case 2 and the error says jury has an answer but your code doesn't .Pls help link to my code https://codeforces.com/contest/1385/my

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

    Please use the correct link to your submission! I'm not sure what the issue is yet, but judging from my experience with this question, have you cleared the adjacent matrix for the vertices after each test case? That might have caused your code to give a wrong answer on testcase 2.

    My code is here 87179787 (I hope it helps)!

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

      Thanks I was finding cycle by wrong method but after seeing your code I realized my mistake and worked upon it to fix it thanks a lot.

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

Can anyone please help me on this in C problem? Getting RTE on Test 2.

https://codeforces.com/contest/1385/submission/87169468

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

    I looked at your submission. For starters, I think you have overcomplicated your code. However, here is why you're getting your run time error.

    Try running this as a test case.

    1
    2
    4 3
    

    If you dry run your code, in the second iteration of your while loop, you'll see that, you have popped all elements from your deque, but you're still running the loop and comparing the elements, which throws an exception.

    I have not corrected your code, but a simple approach that will help you is this. The solution idea is to look for a suffix of the array such that it's one of the three types. 1. All numbers are non-decreasing 2. All numbers are non-increasing 3. At first the numbers are non-decreasing, then they are non-increasing.

    Among all such suffixes, you needed to find the one that had largest length (ensuring smallest prefix to be removed). I did it in a simpler way. See it here 87122310

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

Check out my solution to Problem E using basic topo sort :)

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

Again div3 with the same difficulty as div2 bruh.

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

    Really? I can't think of making the problems easier than this without compromising the quality of contest. If anything, its the div 2 rounds that seem more like div 3 nowadays.

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

    Difficulty level of problem A was like the first problem of any div 2 round.

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

      look at me trying solve A.. feeling stupid now..

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

Div2.5

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

I am checking out cp for the first time, this was my first contest , when will the ratings be available , and do i have a rating?

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

    The rating changes will appear after the hacking phase, that started right before the contest ending. The hacking fase has 12 hours. Read the announcment, it is all explained there.

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

ratings are not updating even of prev contests

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

Rated.

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

Noob question alert...This contest is rated for people below 1600, why my rating graph doesn't show any point for this?

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

Hello i'm newbie, can someone explain why is my contest doesn't get rated?

This is not my first contest, I've participate more than 2 contest. I solved atleast 1 problems for each contest.

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

    The past contest you attended became unrated, due to server problems. The rating for this contest will get updated in some time.

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

This was my first RATED contest. I'm a new user. I participated in last two contest Codeforces Round #655 (Div. 2) and Educational Codeforces Round 91 (Rated for Div. 2), but somehow both the contest got unrated. So in this #656 Contest I solved 3 question. Few moments ago I got my rating, which surprised me.....only 460. How can this be possible? Please help me understanding this.

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

    It will take 4-5 contests to stabilize....

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

      I have seen other user's profile.....everyone have starting rating >1000. Then why I got only 460 ratings

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

    Your previous contests were happened to be unrated. So according to rules of div3, "Accounts that materially participated in less than 2 rating rounds (materially means solved at least one problem there) before the start of the Div. 3 rounds, and those who have ever gained 1900 or more rating units will not get into the official standings and will be assigned to separate rooms. However, this does not mean that there is no rating recalculation for them." you were in this category. So the rating changed accordingly.

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

      U mean that this 460 rating will be recalculated after I participate in more rated contest.

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

        No, if you have not participated in any rated contest before the div3 contest, then the base rating would be zero. (which is recalculated as +460 =460) You can check other profiles too. oly399 got 53 rank still 0+729.

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

A and B should have been swapped :P

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

Dude can someone please talk about the contest problems!

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

87261931 i am getting TLE in 4th question but my answer is same as tutorial (nlogn)

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

Can anyone help me out with Problem C? I approached it using the fact that the 'last local minima of the array (going from left to right) — 1' will be the required answer (and 0, if no local minima exists), but I got it wrong. Maybe my code didnt handle edge cases, but can anybody tell me if this approach is correct?

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

Edit : Wrong Post

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

edit: commented on wrong post

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

Hello, I got quetion, in the problem D the test case include el case asdfghjk and the answer is 7, but the answer shouldn't be 6?. The string of the answer would be ddddgfee

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

In question 1, Why answer cannot be {max(x,y,z),min(x,y,z),min(x,y,z)-1}. In case of YES only.....

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

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