Denisov's blog

By Denisov, 4 months ago, In English

Hello, Codeforces!

We (Denisov, Karavaev1101, perekopskiy) are glad to introduce to you Codeforces Round #660 (Div. 2), which will happen on Jul/30/2020 17:35 (Moscow time). The round will be rated for the participants with rating lower than 2100, although higher rated users are more than welcome to take part out of competition.

Huge thanks to those who helped make this round possible:

There will be 5 problems and 2 hours to solve them.

We really hope you enjoy our first contest!

UPD: Here is the score distribution:

750—1000—1500—2000—2750

UPD: Editorial is published!

UPD: Congratulations to the winners!

Div. 1:

  1. neal

  2. Um_nik

  3. heno239

  4. jiangly

  5. dreamoon_love_AA

Div. 2:

  1. okikust

  2. SpatialMovement

  3. laralalala

  4. KD-Tree

  5. Mai_madarchod_hu

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

»
4 months ago, # |
  Vote: I like it +91 Vote: I do not like it

Piccy.info - Free Image Hosting!

»
4 months ago, # |
  Vote: I like it +47 Vote: I do not like it

if(count(red color) >= 5) {Contest go pew pew over the brain}

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

The contest with 5 problems are terrible but nice.

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

Wow... 2 contests back to back... I am entering heaven. Thank You Codeforces. I was really sad because there was no contest for the past three days.

All the Best Everyone.

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

I think this looks much better (the presence of many colors in the contest announcement). I hope this will help and the contest will be balanced this time.

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

    I went for upvoting but accidentally did the opposite, now I'm not able to revert. It feels I committed a sin for which there is no redemption.

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

    You were right this contest was much more balanced. Also I finally could solve div2B for once.

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

Five grandmasters as testers... hahahahhahahaha what a great opportunity for another -100 rating drop

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

    There's many different testers from many different ratings this time, so I think this comp won't be as hard as previous ones...?

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

    everything is fine but i am afraid from the name after pikmike.

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

      I give contests in 3 months approximately. Prepare D and E questions. I had 1600+ rating earlier. Now I have 1500+ rating.

      I don't give contests in 3 months now.

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

        i am not able to understand what you are trying to convey,may you clarify more

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

        Can you give your english tutor's contact number ....

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

          Yeah I re-read my statement and it didn't make any fucking sense. Then I couldn't think of anything less embarrassing so :/

          TL;DR: The last round's B fucked me. And this time, 'twas a brain fuck.

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

5 questions means another DIV 1.5 contest.

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

next round after 11 days :(

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

Back to back DIV 2 contests, perfect for my rating to enter hell. ;--;

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

2 rounds back to back. And the next round (#661) is 10 days away. Wow. Sure 10 days will be useful for gaining back the trust in self.

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

they have started making difficult contests to ease the system

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

Thank you CodeForces.Love this site very much.....

»
4 months ago, # |
  Vote: I like it +30 Vote: I do not like it

5 red testers ===>>> great pretests and less heartbreak at system tests.
7 testers of lower levels ===>>> balanced round.
===>>>
5 red testers && 7 testers of lower levels ===>>> balanced round with great pretests and less heartbreak at system tests.

»
4 months ago, # |
  Vote: I like it +31 Vote: I do not like it

I miss the days when we discussed if we want more Div3 or more Div4 contests :/

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

hope to give an official submission this time . Left round 657 and 659 cuz can't do anything bout that xD

»
4 months ago, # |
  Vote: I like it -67 Vote: I do not like it

There will be 5 problems and 2 hours to solve them.
Surely the difficulty of contest will be high. After 2 back to back unrated contests due to long queue codeforces has come up with brilliant idea.
Less questions --> higher the difficulty --> less submissions--> no queue --> no unrated round --> No questioning on CODEFORCES PLATFORM.

Forget about Division-3 Rounds Codeforces is trying to make even Division 2, a new DIVISION 1.5.

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

    I wonder if that's true

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

    This contest was easier than #657 (Div. 2). The difficulty of the problem A is significantly lower.

»
4 months ago, # |
  Vote: I like it -67 Vote: I do not like it

wait , no div3 or div4 ?

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hoping for a good contest for me so that i can get out from the bad time i am spending right now.

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

Hope for a good and balanced round. Testers from specialists to grandmasters provide hope for low to high rated participants for being round of their type. Hoping for good positive in this round.

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

(Screenshot-from-2020-07-30-13-56-31)

»
4 months ago, # |
  Vote: I like it +26 Vote: I do not like it

I wonder why does it take time to reveal the scoring distribution ?

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

    In order to unlock the perfect score distribution, the authors must complete a series of quests. They range from solving rejected problems from the previous round to fixing bugs in Codeforces API, and it ends with the most challenging of them all: debug geometry code.

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Hello problem setters, please try to balance the round. I am suffering from continuous imbalanced rounds. Have mercy on me.

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

Now, we have score 750 for problem A. Let's wait for another challenging disaster.

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

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

750 points for A? Solid A I guess

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

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

I am getting a runtime error with the message "Exit code is -1073741819" again and again for educational round 92, problem B. I tried my best but does not understand its causes. Please tell me what could be reason for this error. my submission is https://codeforces.com/contest/1389/submission/88348466

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

    For case k=3, your vector v will be empty.

    int z = v.size() -1;
    

    Here, z=-1 and hence in step

    while(v[z].sec>j && z>0) z--;
    

    you are accessing v[-1]

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

I am quite concerned about the score distribution of this contest. Is it too difficult for members with a rating below 1500?

And over 1500, I think it's okay

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

    Every div. 2 is too difficult for below 1500.

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

      I agree with you, but that was before the rating point was changed, because now, some coders with a rating below 1500 can successfully complete the contest div.2

      I don't know if it's the clone accounts of coders with rating points above 2500 or really a new coder

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

Does anyone know why atcoder is not having ABC for last couple of weeks?

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

Why this score distribution? A starts from 750. Seems to be somewhat difficult. Anyways, surely gonna enjoy the problems :D

»
4 months ago, # |
  Vote: I like it +40 Vote: I do not like it

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

    Yes, but unfortunately, there won't be any rounds for the next week. I think if MikeMirzayanov add a conditional div3 in 4 days, it will be perfect :)

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

Testers kindly comment on the kind of the problems. I hope there is something for a newbie like me to solve. This is my first rated contest and I hope to solve at least one problem today. Nevertheless, I am going to enjoy them :) Thank you , Codeforces!!

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

Is it like people aren’t interested in this round? By seeing only 484 upvotes which is less than the normal upvotes for a Div2 round. Can anybody please share the reason for the same ?

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

How is it decided that an incorrect submission will result in -50 (in the score) or -10 minutes? Or is it just up to the creators?

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

    -50 points, as the problems each have points, if they didn't like in educational round or div3 then -10 minutes

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

      Ohh, so educational rounds have this -10 minutes thing. Great Thanks Cheers!!!

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

    From my knowledge they are different rules. Usually educational rounds and div3 rounds are held on extended ICPC rules, which result -10 minutes. Others result in -50 in score.

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

    As far as I know, Educational rounds and Div.3 rounds are not score based, i.e., in those rounds only the number of solved problems matter. Since those rounds do not involve score, hence they have Time penalty for incorrect submission. On the other hand, Div.1 and 2 are scores based, i.e. each problem has a score associated to it, hence they have Score penalty for incorrect submission.

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

we are friends now! hello, friend! [user:Mike!Mirzayanov,2020-07-30]

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

too op :-(

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

All the best friends!!

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

Do you have editorial for this contest?

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

Could codeforces consider weekend contest? I have conflicts on the weekdays (unless it's before 6 AM PST or after 5 PM PST). I'm pretty sure other people have more time on weekends too.

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

Speedforces!

»
4 months ago, # |
  Vote: I like it -128 Vote: I do not like it

pic1.png pic2.png

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

    Not being able to solve a problem doesn't make the round bad (or shit as you said).

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

    At least on Topcoder or AtCoder you can leave your submission up there until hacked, here you just get a demanding test case. These problems are getting harder to solve, even on the easiest levels. :(

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

I submitted my solution of problem A at 0:15. And after submitted my solution to problem B I tried Problem C but couldn't do it.. Then I was feeling kind of bored so I resubmitted my Problem A and B but in Kotlin as I am learning this new language from the last couple of days.. As soon as I submitted it, it added time penalty and my rank decreased.. Why did this happen ?? MikeMirzayanov please can u help ..

»
4 months ago, # |
  Vote: I like it +33 Vote: I do not like it

Who is uncle bogdan I wish I am as talented as him

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Well even if the contest ended up being speedforces but I still really enjoyed thinking about C,D & E. They seemed really interesting and I can't wait for the editorial. Thanks for the interesting round!

»
4 months ago, # |
  Vote: I like it +14 Vote: I do not like it

gradient(difficulty change from D to E) = +infinite

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

Is topological sort wrong for problem D? I am adding edge from x->b[x] if a[x] is positive, and b[x]!=-1, and the opposite edge if a[x] is negative! Please tell me whats wrong in this?

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

    Try this test

    3
    -1 2 3
    3 1 -1
    
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. Almost there :P

    Say that you have this case

    10000 -1 0
    2 3 -1

    Now can you find the issue?
    P.S. I also made this mistake during the contest.

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

      Start from nodes with in degree 0, remove edges from it, and it should work.

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

      Thx I got it :)

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

    The negative a[x] can be positive during the operation, which is good for maximizing ans

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

help me with C after the contest

  • »
    »
    4 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it
    Explanation to problem C
»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

First reaction after reading C: bruh

»
4 months ago, # |
  Vote: I like it -20 Vote: I do not like it

is it rated?

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

    Yes it is rated for you <(")

    Just read the blog before asking it :)

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

After making silly implementation mistake in B I thought myself as cabin boy Kostya.

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

Irritating B, as all B's should be

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

Thanks for the round!

»
4 months ago, # |
  Vote: I like it +42 Vote: I do not like it

Nice contest, great problems. I really liked how you put the background stories at the top so we could simply ignore them. Although there was a huge difficulty gap between B and C (causing speedsolvers of A and B to get a high ranking), I think the problems were good overall. Hopefully pretests are strong (don't let me down), and I'm still very thankful that you included 36 in the samples for A (I'd probably get WA on pretest 2 and be scratching my head if you didn't)

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

Your text to link here...

whats wrong with my code of second problem please help??

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

    Its mentioned in the question that binary form of(0-9) is concatenated without leading zeros.

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

Wasn't a lot of problem B solution given by the example input.

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

Seems like yet another rushed contest to maintain schedule.

(With all due gratitude to the the writers) Urging organizers to please be patient for decent enough problems for a well balanced set before arranging a contest.

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

lol, C is more difficult than D and E

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

For me C and D have same difficulty

I got the solution of D but don't have enough time to implement it.

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

    I got the idea but couldn't understand how to implement. Maybe D is slightly harder.

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

    i could calculate the maximum score correctly but still struggling with the order of operations

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

    I think D was easier than C.If C and D were swapped then it might have more number of submission.

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

Whay is the solution for C?

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

    Try to solve a simpler version in which all cities are in a straight line. The intuition there carries forward to the general tree case. Its a good dfs question.

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

    Do a bottom-up dfs and for each node i, 2 conditions must be satisfied

    1. You should be able to divide totalPassing = (p[i]+(sum of p[u] in whole subtree)) to "happy" and "unhappy" to get the required h[i]. This can be done be simply checking if totalPassing%2==abs(h[i])%2.

    2. Total number of happy in all of its children should be greater than the "happy" calculated from h[i]. This is because, if a node as n happy people then everyone in the subtree can have at max only n happy people.

    If one of them is false for any node, answer is "NO"

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

      also will this hold : |mood[leaf]|=p[leaf] ? (|x| is absolute val)

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

        Yes, why not? |mood[leaf]|=p[leaf] means that for any leaf, all its inhabitants are either all unhappy or happy

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

          Yes got it, so help me here alright, We get the node(call it v) which is parent of some leaves and leaves only (let it be parent of x leaves), so this must hold :

          people[v]=| mood[v]- (mood[leaf1]+mood[leaf2]+...+mood[leafx]) |

          Now my question is what about the other nodes, I am getting confused here on writing the people equation for other nodes.

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

            That equation isn't correct. Just look at it this way, Total number of people passing a node is the total number of people living in the whole subtree.

            First of all you need to be able to divide this total into the required h[i]. Ex- If the total people is 10 and and h[i]=4 then happy people is 7 and unhappy people is 3.

            NOw some of these people are gonna pass down into the subtree. Here is the important part, The 7 happy people can be converted to unhappy people but the 3 unhappy people cannot be converted back to happy. So here is where we need to check the condition that

            Total number of happy passing a node >= sum of happy people of all everyone in the subtree

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

              Ahh I get it,..Thanks for the quick response!

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

              Submission 88531594 I understood the logic but still can't understand what is wrong in my code. Can you please go through and suggest changes? Thanks again!

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

Is 3rd pretest for problem D — 3rd sample test case?

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

    yeah should be.

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

      I need 100% true answer

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

        Check your submissions, your recent code fails on the sample test — 3. So yeah i'm 100% true.

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

        yes it is, you can see the that test case along with your submission

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

        If you got stuck on it you could literally just look... pretests are shown when you click on submission.

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

          Yeah, thanks, I was so confused and have not noticed that.

»
4 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Nice problems. I think this round is somewhat similar in difficulty to old div 2s and I like it. Been a while since I struggled with C.

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

You are lost when you get WA on C. Like how can you debug this. How can you generate test cases and see which works. I am lucky to debug C

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

How to solve problem D? Would topological sort fail?

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

    Make a graph using array b and topologically sort it. Start from the beginning and if value of a[i] is non- negative, choose vertex i and update a[b[i]]. After that, sum up the array a.

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

      Can you point out the mistake. I did a topological sorting with graph made using Array a. Link — https://codeforces.com/contest/1388/submission/88522224

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

      yeah, i came up with the same idea, but dunno how to print the order correctly

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

        For positive a[i] just push them in order that you encounter them and for negative, put them in reverse order in which they are present in topo sort.

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

          yeah, did you mean to put all the negative a[i] to another vector then print the positive a[i] as topological order and then print the negative vector in reversed order?

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

            No. Let topologically sorted vertices be in array topo. Then, traverse the array topo from start and if you encounter any vertex i with a[i] >= 0, push it into the answer array and update the corresponding value of a[j] where j = b[i]. Mark vertex i as visited. After that, traverse the topo array in reverse order and add to answer any unvisited vertex.

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

              lol, that is basically the same as my comment, anyway thank you, i got it.

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

Is E to binary search for most vertical vector?

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

Does problem D involve topological sorting?

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

    Yes. Do you want more information?

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

      Can you point out the mistake in logic or code i did. Link — https://codeforces.com/contest/1388/submission/88522224

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

        It's because you printed all the values in their topological order. Some need to go last. Suppose the graph has the following path -1000,10,10,10. You don't want to use -1000 more than once, right? If you use it before the second element, it will be used at least twice, so you want to use it last.

        My python code of the important loop (top is in the order the topological sort):

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

          i did the same by checking if the current value A is less than 0. Then instead of doing A->B i did B->A

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

            Well that's wrong for other reasons. Suppose you have the edges 1,3 and 2,3. supposed 1 is very big, so you reverse it to 3,1. Now you have the graph 2,3,1 and you make a path that was never there (the value of 2 will be added to 1, which shouldn't happen).

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

I dont have idea how to solve D, but guide me if what im thinking might be correct,(if it's related to graphs? )

So, we have a directed edges with few nodes with negetive value and other with positive.

My approach:

1) find cycles in graph.

2) for remaining nodes(which are not in cycle),

2.a) if it's positive, add the value to the node it is pointing to,

2.b) if it's negetive, add it in the final sum, i.e only once?.

3) for every cycle begin counting the sum, from node which has highest value of Pi

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

    There is written that graph does not have cycles.

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

Hey can someone explain me, why this sample test case is NO??

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

    The mood in city 3 is 4, but it has 7 people in it.
    4 % 2 == 0 but 7 % 2 == 1.

    Edit: The mood of a city must have the same parity as the number of people who pass through it.

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

    the parity of the happiness index and the number of people going through that city should be same. for example if there are 4 people going through a city the happiness index can be 4,2,0,-2 or -4 but it cant be 3,1,-1 or -3. In your case for city 3 number of people is 7 that is odd therefore happiness index cant be 4 as its even

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

Problem C was quite interesting .. Overall, nice contest.. Thanks :)

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

There was a huge gap between B and C.Indeed it was a speedforces type.Ig they are making nowadays tougher one to reduce the load to the system.

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

I was not able to submit working B. Is there a "funny" trick or something?

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

    Its all 9s except the last ceil(n/4) digits which are 8. I guess you could say its a funny trick.

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

      Ah... I kind of mixed up the logic :/

      If somebody is interested in how one can make this one still wrong after aprox and hour of thinking: 88513867

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

    It's always some number of 9's followed by some number of 8's. Number of 8's increases when length of string is 1,5,9,13... as you would be erasing the 1 that separates 8 / 9.

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

    Ans was of form count(9) + count(8), at first I was replacing trailing 8 with 0, and did 2 wrong submission

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

    all the last (n+3)/4 numbers must be 8 and the remaining ones shall be 9. because you want to get maximum r which is only possible if numbers in x have higher length in binary format. since 9 and 8 are only possible 4 bit binary digits , thus we always require to choose numbers as 9 and 8. first of all place n 9s in a string then if last bit of any 9 is getting chucked off then replace that 9 with 8 continue doing so until you replaces last n bits.

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

It was amazing, thanks!!

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

What a great contest with fun problems!!!

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

Sorry my bad :((

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

Nice Contest Able to solve Only 2 .. but real Div2 is Back How to solve D ?

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

    Build the graph from array 'b', since it's acyclic topo sort exists, process the numbers in that order...watch out when the value is negative, in that case process it's child first....

»
4 months ago, # |
  Vote: I like it -9 Vote: I do not like it

Man I was first officially right after solving A and B but then got bogged down by debugging on C and didn't get much time to implement D so pretty much no delta change.

Speedforces

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

Question B ** Why output for 4 is 9998? shouldn't it be 9990? There I can't see any restriction for using 0 in the end.

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

    $$$0$$$ is represented as $$$0$$$ and not $$$0000$$$

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

    binary representation of 9990 is 1001 1001 1001 0 , note that you don't add 4 bits for 0

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

    if you use 0 at end then string k will be(no leading zeros so 0 will be 0 and not 0000) 1001100110010 removing 4 digits from end we get : r1=100110011. Now consider taking 9998, we get 1001100110011000 removing 4 again, r2=100110011001 clearly r2>r1 so 9998 is optimal.

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

    9998 then 1001100110011001 --> 100110011001 9990 then 1001100110010 --> 100110011

    since 100110011001 > 100110011 hence 9998

    your reasoning will be true if we represent 0 also as 0000, but as can be seen in question they representing it without leading zeros.

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

    You should have every digit 8 or 9, else R will have less digits and won't be the maximum.

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

    no because for x=9990, k=1001100110010 and for x=9998,k=1001100110011000 after removing 4 digits from back in both cses obviously 2nd no. will greater

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

    Oh got it now. Thanks everyone. Happy coding.

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

Uncle Bogdan is OP!

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

For problem c, we had to topologically sort elements of a using b, and then do a forward pass picking only non-negative elements and another backward pass picking the remaining elements right?

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

My solution for problem D outputs "1 3 4 2 5 6 8 9 10 7" as an order of operation for 3rd sample test case. I checked this order by simulating it on computer and it is giving answer -9 which is correct. Can someone help me to find out what is wrong?

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

    the 8 should go after the 7. you should reverse the ones that have neg at the end.

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

Q2.Can any one help me where I am wrong in question

`#include<bits/stdc++.h> using namespace std; const int a=1e5; int main() { int t; cin>>t; while(t--) { long long n; string s; cin>>n; if(n==1) cout<<8<<"\n"; if(n==2) cout<<98<<"\n"; if(n==3) cout<<998<<"\n"; if(n>=4) { int a=n/4; if(n%4==0) { for(int i=0;i<a;++i) { s.push_back('0'); } for(int i=0;i<n-a;++i) { s.push_back('9'); }

}
        if(n%4!=0)
        {
            for(int i=0;i<a;++i)
            {
                s.push_back('0');
            }
            s.push_back('8');
            for(int i=0;i<n-a-1;++i)
            {
                s.push_back('9');
            }



        }
        reverse(s.begin(), s.end());
        cout<<stoi(s,0,10)<<"\n";
    }

}

return 0;

} `

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

    You should be using 8's instead of 0's, as 0 will be read as 0 and not 0000

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

Problem B. n = 4 k = 1001 1001 1001 0000, r = 1001 1001 1001, x = 9990. But answer is x = 9998. Why??

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

    if you use 0 at end then string k will be(no leading zeros so 0 will be 0 and not 0000) 1001100110010 removing 4 digits from end we get : r1=100110011. Now consider taking 9998, we get 1001100110011000 removing 4 again, r2=100110011001 clearly r2>r1 so 9998 is optimal.

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

    Oh, My mistake. zero is just 0, not 0000.

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

    K for x = 9990 is 1001 1001 1001 0, it is not 1001 1001 1001 0000 because it is given in the problem statement that we must write the digits of x in binary representation without leading zeros.

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

Problem C: Can anyone explain why is the answer for test case 2 in example 2 of Problem C is "NO".

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

    The P for city 3 is 4, when H is 7. We can't make P even, when H is odd and the city don't has subtree.

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

    In city 3 try to figure out happiness 4 among 7 people. I think it's impossible.

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

In C, I checked at each node if the happiness count at each node is not smaller than its subtree, I calculated the count of happiness at i th node by fetching total people living at that node and its subtree. Now I have happy-sad at that node (given) and happy+sad = total, I checked if the number of happy people in its subtree is not greater than this value, apart from adding other small conditions. Is it the right approach? Although I could not implement it :(

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

    Did you also check if the total number of people living in node and subtree can be divided into the required happy and sad for that node

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

      Yes, that is what I meant when I said, additional constraints.

»
4 months ago, # |
  Vote: I like it +97 Vote: I do not like it

I think writing $$$2000$$$ is better than $$$2\cdot 10^3$$$ in case of small constraints. I spent an hour trying to solve E for $$$2\cdot 10^5$$$ before I noticed the constraint. Of course, it was my fault (I even read maximum in place of minimum) but it still is more convenient.

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

https://codeforces.com/contest/1388/submission/88470430

For problem B. Can anyone explain why this gives TLE? This is in PyPy, but same submission in Python gives AC.

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

    Maybe python interpreter not doing loop, but just s+="8"*smth

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

    When you add a character python creates a whole new string, so your complexity is n^2.
    Get used to making lists of characters and then ''.join(L) at the end.

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

      If i understand correctly then s=s+'8' is O(n) and s+='8' is O(1) and i have used s+='8' in my code. Even the same code run in python gives AC so definitely it does not create a new string in Python. Maybe in PyPy it does.

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

        Could be, but that why I:
        1) Only use pypy if there is lots of calcualtions involved (for strings,graphs — always python)
        2) Use str.join so I won't fail even if I choose pypy by mistake (and it happened many times before).
        3) Use str.join because I am human and I can always do s = s + c by mistake...

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

        Well. Optimized appending to the string is pretty much CPython implementation detail and is not guaranteed by the python language per se.

        So you're right. In CPython this operation is heavily optimized and I believe is O(1), i.e. it does not allocate a new string every time (there are exceptions actually to maintain external immutability and this immutability is exactly the reason why most people believe that it should always be O(n)) and in PyPy is O(n).

        Actualy, I knew that this is not guaranteed in python, but never thought it would become a problem in cp when switching to pypy.

»
4 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Appreciate the very strong pretests in the contest. Also interesting problems, C was a graph problem after many contests and it was pretty nice imo.

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

Problem C is quite annoying. I look through some PP code after contest and get nothing about why I'm wrong or even whether I failed to judge something.

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

    Why did you divide by 2?

    Edit:
    I'll tell you what I don't see. I don't see a condition: h[i] >= sum(h[children_of_i])-p[i]
    I don't see the minus p[i] part.

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

      I got what's wrong. My DFS is incorrect. If I wrote correct DFS I would get AC with 50 points penalty.

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

        Was it because "sz[to[i]]" of the parent could be not 0?
        I'm sad for you :<

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

A very good Problemset after decades.

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

MikeMirzayanov

Cheating caught in today's contest https://codeforces.com/contest/1388/submission/88511065 https://codeforces.com/contest/1388/submission/88510232

They have same codes only function names and variables are cleverly changed.

And the second guy deliberately submitted late when he was sure he will get 3 AC's.

Dont know why people show such teamwork in CF just to increase their ratings.

Their other submissions from the contest are also same.

Shame.

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

In second question, if n=4 then the answer should be 9990, right?. Similarly if n=5, it should be 99980?

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

    No, 0 is only 0, not 0000. however, 8 is 1000, so 8 should always be used because it's 4 bits instead of 1.

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

    For 0 it is represented by 1 bit only so in that case it will not give the required answer. Check problem description for clarification.

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

    No...n=4 -> ans=9998 and n=5 -> ans=99988

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

88492256 Why my submission of question B got TLE in system testing.... help

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

    Same thing happened to me.

    s += '9' will work in time. s = s+'9' will not...

    I think the += operator knows to add on to an existing string (like push_back on a vector) while the + operation treats it as creating a new string.

    Very annoying (and to me, something I thought would have been caught in a pretest at least).

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

    While adding new charachters to the string you wrote: s = s + '8' which has complexity O(n) and as you do this operation n times the overall complexity of your code becomes O(n^2)

    You should have written s+='8' for appending charachters as it has compexity O(1)

»
4 months ago, # |
  Vote: I like it +81 Vote: I do not like it

It's interesting that if I don't hack Geothermal's problem E code, my first submission of problem E will pass all tests.

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

    :(

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

    Hack人终hack己

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

    :((

    I don't understand why your solutions fail this test. Is it because all projections should touch or because of the (0; -1) optimal vector? Can you explain, please.

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

      It's because there are many points pairs are parallel and we don't consider the case well when sorting them. In our method, it will make the program don't catch the case projection is parallel to these points pairs.

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

Can someone please help me out with C. Here is my approach :
1. Do DFS and store the total population of current city and the cities below it.
2. Then do DFS and find the number of people having mood in the children cities.
3. Find if the current population of city is good enough to satisfy all conditions .

Link to code : https://codeforces.com/contest/1388/submission/88521378
Thanks in advance !

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

I think I still have to practice a lot.

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

Problems of this round were truly amazing. Loved it <3.

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

The contest was great! And many many thanks for the good samples.

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

In the contest i wrote a solution for problem C which exceeded time limit on test 11: According to me it is an O(N) solution. Can somebody figure out the issue.

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

    Try passing your vectors by reference as your current solution makes copies on every function call.

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

can someone please help as to why this code gives tle on test case 7 in problem B??88487950

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

    instead of s=s+'9' and s=s+'8' try s+='9',s+='8'.i too faced the same problem

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

    Used the s += "8"("9") rather than s = s + "8"("9")

    += take O(1) time

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

    When you do s = s+'9' you are basically creating a new string s+'9' and then assigning it ot s. So for one step its complexity is O(s.length()). So the overall complexity becomes O(n^2).

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

solved the problem D during the contest.forgot to declare ans as long long. result:-suffer.

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

So, for problem E, if I assume at least two projections touch each other in the optimal answer, I have 2*n possible vectors to choose. And if I check all these cases, the answer should be the minimum of all the answers, right? Is this approach correct ? If so, why is the number of submissions so less ( because of geometry? )?

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

    Don't you have n^2 possible vectors to check? And then you have to check in O(1) instead of O(n)

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

      There won't be n2 possible vectors because we only need to consider the adjacent pairs when sorted by the start point or end points. If we choose two random pairs, the segments whose starting point lie between these pairs cannot be projected without them intersecting.

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

    If we consider the effect of the projection $$$(a, b)$$$ on an interval $$$(l, r)$$$ at height $$$y$$$, then our new interval is projected onto $$$(l - y\cdot\frac ab, r - y\cdot\frac ab)$$$. If we let $$$t = -\frac ab$$$, then this is simply $$$(l+yt, r+yt)$$$. Thus, view the intervals as buses with speed $$$y$$$ and location at time $$$0$$$ equal to $$$(l, r)$$$. We want to find a time $$$t$$$ where no two buses overlap, and we minimize the length of any interval containing all the buses.

    If we go to time $$$t = -\infty$$$, the fastest bus should be all the way on the left, while the slowest bus is all the way on the right. At time $$$t = +\infty$$$, the fastest bus in on the right, and the slowest bus is on the left. It's also clear that the time with the minimal interval is when two bus endpoints are touching. To reverse the order, there are $$$\mathcal O(N^2)$$$ crossings. We can process them by time, and keep track of how many buses are crossing at each point in time. Whenever there are $$$0$$$ crossings, then we simply want to find the maximal value of the endpoint of a bus minus the minimal value of the endpoint of a bus. This can be done with Convex Hull Trick. Overall, this will take $$$\mathcal O(N^2 \log N)$$$ where this comes both from sorting the $$$\mathcal O(N^2)$$$ events and the Convex Hull Trick.

    88530891

»
4 months ago, # |
  Vote: I like it -58 Vote: I do not like it

C: Could anyone please tell why is it giving TLE?

https://codeforces.com/contest/1388/submission/88528267

typedef long long ll;

ll fillp(vector<vector<ll>> &g, vector<ll> &p, ll cc, vector<ll> &nop, vector<int> &vis)
{
	ll tnop = 0;
	vis[cc] = 1;
	for(int i = 0; i < g[cc].size(); i++)
	{
		ll nc = g[cc][i];
		if(!vis[nc])
			tnop = tnop + fillp(g, p, nc, nop, vis);
	}

	nop[cc] = p[cc] + tnop;

	return nop[cc];
}

bool flag = true;
ll check(vector<vector<ll>> &g, vector<ll> &sad2, ll cc, vector<int> &vis, vector<ll> &p)
{
	int nos = 0;
	bool ok = true;
	vis[cc] = 1;
	for(int i = 0; i < g[cc].size(); i++)
	{
		ll nc = g[cc][i];
		if(!vis[nc])
		{
			nos = nos + check(g, sad2, nc, vis, p);
			if(flag == false)
				return INT_MIN;

			ok = false;
		}
	}

	if(!ok && min(2 * p[cc], sad2[cc]) + nos < sad2[cc])
	{
		flag = false;
		return INT_MAX;
	}
	
	return sad2[cc];
}

int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		ll n, m;
		scanf("%ld %ld", &n, &m);

		vector<ll> p(n + 1);
		for(int i = 1; i < n + 1; i++)
			scanf("%ld", &p[i]);

		vector<ll> h(n + 1);
		for(int i = 1; i < n + 1; i++)
			scanf("%ld", &h[i]);

		vector<vector<ll>> g(n + 1);
		for(int i = 0; i < n - 1; i++)
		{
			ll x, y;
			scanf("%ld %ld", &x, &y);

			g[x].push_back(y);
			g[y].push_back(x);
		}

		vector<ll> nop(n + 1);
		vector<ll> sad2(n + 1);

		vector<int> vis(n + 1);
		fillp(g, p, 1, nop, vis);

		bool ok = true;
		for(int i = 1; i < n + 1 && ok; i++)
		{
			sad2[i] = nop[i] - h[i];
			if(nop[i] < abs(h[i]) || sad2[i] % 2)
			{
				ok = false;
			}
		}

		if(!ok)
		{
			printf("NO\n");
			continue;
		}


		flag = true;
		vector<int> vis2(n + 1);
		check(g, sad2, 1, vis2, p);

		if(flag)
			printf("YES\n");
		else
			printf("NO\n");
	}
}
»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My approach for C was:

Stored the dfs from 1 in an array. Then Reversed it.

Now we iterate the array. (starting from the leaf nodes.)

For each node we maintain good and bad people passed through it. Then we traverse this reversed dfs, and for each node all it's children's good and bad can be good for our current node. Also the people who live in the present city can be good as well , thereby we try to maximize the good cases. Then we fix current node's good and bad such that we maximize good and have just enough bad to make happiness[i].

For any node if we don't have enough good or bad , it's simply a NO.

Please help in my Code. A failing test case please.

Edit: Sorry I thought its bad instead of sad.

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

    Hey, I feel that you didn't accommodate the fact that bad (sad) people can actually be residents of the given node and children nodes may have less sad nodes than parent because their home was inside parent.

    I created a class with intuitive variable names if you want to check my code out! 88503365

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

what a great contest ! Thank You all .. Denisov make more contest with your team <3

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

A very good match, but the difficulty gradient is not good. Question b can be a little harder, and question c should be easier. I passed c after the match. If I have two and a half hours in the match, I can solve c. To summarize my code, I feel that my code is too long and not concise. And typing speed is too slow. Many areas need to be improved.

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

I appreciated the convexity in Problem E. I could best picture the projections as the shadows from an infinitely distant light source.

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

Respected Sir,

I would request for a recheck on my solution submitted to Problem B from Codeforces Round #660. I have been shown Time_Limit_Exceeded on my solution, but that same solution when I executed it through the custom invocation in codeforces on the same test case it was executed in 658 milliseconds. I would create a great impact on my ratings. I would request you to give a recheck if possible.

I have attached my solution to the problem.

88478273 Codeforces Round #660 (Div. 2) standings

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

    Interesting, it is your s=s+"9" that is slow: it is probably copying everything into a buffer, i.e. it results in a O(n²) solution.

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

      I am still wondering why is this code accepted then[submission:88534456]

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

        n² is not that large. When I tried, I also got accepted sometimes, but with times close to the limit. It means the conditions were not set tight enough.

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

          So I guess for a fair judgment they should allow everyone's solution whether it be s=s+"9" or s+="9" because otherwise, the time limit should have been 1 second

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

    Surprisingly, the same solution is accepted now-Accepted Code. I think, its because of s=s+'8' which take $$$O(n^2)$$$. Replace it with s+='8', it will take significantly less memory

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

Thank you for very nice problems! They was a good balance of diffculty (at least A, B, C that I tried).

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the ratings update?

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

https://codeforces.com/contest/1388/submission/88494957 (Contest Submission) https://codeforces.com/contest/1388/submission/88531246 (Unofficial Submission)

EXACTLY IDENTICAL FILES First file gave TLE in System Testing, second file got Accepted. May I know why?

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

    You should never do "s = s + '8'". This takes O(length(s)) operations. So your code is actually O(n^2). Replace all the " s = s + x" with "s += x" and you will notice a sharp time difference. See my submission below where I made that change in your code and it took only 30ms compared to the previous 1700 ms.

    Usually there is heavy load on the servers during the contest and the code may take longer to run

    https://codeforces.com/contest/1388/submission/88533226

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

      I had a same doubt while solving a problem recently.So i used push_back function on string which is O(1). Still , I have a doubt how to push a character in front of a string in O(1)?

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

        You can't, except a trick in the case you only need to push to the front: push to the back and then reverse at the end.

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

        I am not aware of an STL functions which would prepend a character to a string. However, you can store the string as a deque<char> where insertion and deletion at both ends can be done in O(1).

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

      Time difference is real sharp man! Thanks, didn't knew this.

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

this is my first contest. i solved the first 2 problems but i am still unrated... waws this contest unrated??

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

    NO, the ratings aren't updated yet it will be updated in some time.

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

      how much time does it take to get updated?

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

        It should have been updated by now.but i think they will most probably be updated within 30 minutes.

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

Why in the problem B this solution gave TLE in the contest [submission:https://codeforces.com/contest/1388/submission/88476304] while in practice the same solution passed [submission:https://codeforces.com/contest/1388/submission/88533918]? Please can you clarify this doubt Denisov MikeMirzayanov

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

    Look at my comment above. The TLE is due to the expression "s = s + '9'"

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

      I agree with that but the official submission gave TLE and the same exact solution passed in practice in 701 ms how is that possible? Both the codes are exactly same.

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

Bad comprehending killed me..

»
4 months ago, # |
  Vote: I like it +29 Vote: I do not like it

Rating predictor seems to be a little off on accuracy today

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

    Rating Predictor gave me false hopes of master.

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

      Why bother you'll anyways make it to master in the next round for sure, you seem to be on a rampage lately, good luck!

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

      Rating predictors work only for div. 1s.
      Other contests are fked up due to new accs.

      With the increase of div1 users with less than 6 contests. Rating predictor will start fking up in div 1s as well.

»
4 months ago, # |
  Vote: I like it +13 Vote: I do not like it

My video solutions to problems A, B, C, D.

Enjoy watching.

https://youtu.be/0ExktAwScLc

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

I used to do cf regularly couple of years back but has started attending recently again. Honestly the new rounds came to me a bit unfamiliar until this round. Gave me a taste of past classic rounds.

Hoping to see round like this one more. Kudos !!!

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Check out the video editorial of Problem D

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

I think the testcases for B are not complete, my O(mn) dp solution was accepted but I think of a case where it should fail.

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

Can someone plz tell me why we cannot add 0 rather than 8 in some of the positions in B??

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

    Because we want the biggest possible result, and a 0 adds only one digit, while a 8 or 9 add 4 digits. So the result is not biggest possible if a digit other than 8 or 9 is used.

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

    binary representation of 0 = '0' while that of 8 = '1000' If you use 0 you will be three digits shorter.

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

Rating changes for this round is looking a bit weird according to the predictor.Are these changes final or will they be checked again?

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

    Yes, i felt the same in the begininning so I recheked on what basis the predictor was working on. Looks like the predictor didn't consider the rating changes of Educational Codeforces round 92.

    I will tell my own case. My rating before EDU round 92 was 1202. After that contest, my rating changed to 1300. In Codeforces round #660, it was showing +8 for me at the end of the contest but my rating decreased by 9 to 1291. The predictor was showing +8 instead of -9 because it considered my old rating of 1202 instead of 1300 (Rating after EDU round 92). It is the same case for everyone.

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

In Problem A: It is said to print "4 different positive integers", but why one of those 4 positive integers can not be zero ('0')? Where is the range is mentioned? Please help me to understand the constraint. Thank you.

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

    Normally "0" is not considered when they say "Positive Integers" meaning it is the set [1,infinity). If they say "0" can also be included in the answer, then they will Explicitly mention "Non-Negative Integers" (instead of Positive integers) which is the set [0,infinity).

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

Is that possible that vector does not response to push_back() in any case?

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

.

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Dear Codeforces Community, I received a mail from you and there were issues regarding same solutions using different accounts. Both the accounts belong to me and I have the second one as a backup account. The code is written solely by me only. I have proofs that both accounts belong to me and I am the only one writing the code. I had a rating bump yesterday but its been cancelled now. I didn't know CF community has harsh rules against 2 accounts. This was my first time so if you could look into the problem. MikeMirzayanov System Please help me.

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

    You can have two accounts, but you cant use two of them in a contest, it is in the rules. It is because you will only submit in one of them when you have solved the problem, so you will have less penalty in that account.

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

    MikeMirzayanov adedalic Please reconsider this issue and get back to me. I was penalised a huge rating bump. I didn't know the issue about using 2 accounts in the same contest. This was my first time and I wrote that code by my very self.

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Congratulations to adedalic for amazing coordination of this round!

»
4 months ago, # |
  Vote: I like it +11 Vote: I do not like it

In this round, something strange happened, I had a pretest passed the verdict , but I got RTE on Test 1 during the system test due to me calling a[-1] in one part of the code. Now I understand that the mistake is mine but how does the same compiler give different answers for the same input. Here is the link to my submission. Since I was effected negatively due to the compiler issue, is it possible to be exempted from rating change in this round?

Link to the submission : https://codeforces.com/contest/1388/submission/88495272

MikeMirzayanov adedalic

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

    It isn't a compiler issue. It's an undefined behavior

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

      Can you explain a bit why it is different every time and how did it pass all protests without raising flag and now is giving RTE 1 everytime

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

        I don't know how it works exactly and why it passed pretests. But undefined behavior means that its behavior can differ every time you run this code.

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

          Ohokay, thanks ... but I still feel something is strange that it passed all pretests. I would be grateful if someone could elaborate on what exactly happened and is there a way to avoid it in the future by perhaps using some flags in my local build.

      • »
        »
        »
        »
        4 months ag