Warawreh's blog

By Warawreh, history, 3 years ago, In English

Hi fellow Coders!

Kilani, Salem_Alwarawreh and I are glad to invite you to take part in Codeforces Round 699 (Div. 2), which will take place on Feb/05/2021 17:35 (Moscow time). Round will be rated for participants with rating less than 2100. Participants from the first division are also welcomed to take part out of competition.

You will be given 2 hours to solve 6 problems, each problem has a picture and a story above it. The stories are skippable if you want to focus on the real problems.

We would also like to thank:

Score distribution will be announced before the start of the round, hopefully.

We hope you like the problems and enjoy solving them!

UPD: Scoring is 500 — 750 — 1500 — 2000 — 2500 — 3000

UPD: Editorial

UPD: Congratulations to the winners

Div1 :

  1. dreamoon_love_AA

  2. neal

  3. Sugar_fan

  4. hank55663

  5. kotatsugame

Div2 :

  1. Quirrel

  2. -ohweonfire

  3. tuagoale

  4. buihoatpt2k3bc

  5. njwrz

Thank you all for participating!

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

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

Finally an expert in problem setting :)

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

    I don't know what's wrong with your comment. You mentioned a rare fact and some people just demotivated you. A couple of contests before I wrote a fact that if code is not optimized then it shouldn't pass pretest and I got negative contributions for saying that. And a red coder just puts a dot and he gets a 100 contribution. This is what it is now.

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

      yes bro I am also wondering why I am getting too much downvotes :(

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

      Codeforces is a huge competitive programming community. People expect some worth in reading comments. Useful comments may get hidden by "not so useful" comments/facts like yours. So in my opinion, we should comment only if it's highly necessary.

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

        No one expects anything useful in comments before the contest.

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

        1-gon usually just puts a dot, and he ridiculously got first in contributions, while Errichto did hundreds of explanatory comments and helped a lot of people, and he really deserves his place.

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

        You are right! Many new coders like me hesitate to ask something in the comments as maybe it is very trivial and easy for some people and could lead to a downvote! (I don't want to have negative contributions!) [ Please don't downvote on this comment :) ]

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

          Why are you afraid of negative contribution? It means nothing. Contribution points are not intended to scare you off from seeking help from the community.

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

      And about the thing u said about red coders is not always true. example: http://codeforces.com/blog/entry/86048?#comment-738203

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

        I haven't said always... And about the worth reading part, see below u will find it's not always about knowledge sharing or "highly useful" comments. You should have checked this comment section below first before replying. You should have.

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

        I knew that you are gonna point to HealthyUG's comment. XD

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

      But why do you care about contributions? Is it worth having +100 contributions( What you would do with those contributions trade them with money? ), rather we are here for CP and most importantly to enjoying solving problems.

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

        No, I cared once but not anymore. I thought people with more contribution points are providing something that others aren't. So I even tried following someone like Errichto.

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

          See there is a difference between doing something for contribution and getting contribution for what you did.

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

As a non tester, I just commented to make SlavicG's comment appear further down.

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

Jordanian round ❤

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

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

    That's real.

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

      omg meet you huh.

      Howevr F is too hard...

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

        Kevin090228 became Master at the age of 11!

        stO Kevin090228 Orz

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

          WTF! mind blown. There's crazy talent on this site Lol. I'm a decade older than he is. gj Kevin.

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

            Yeah.I'm a year older than him but he is much stronger than me.

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

              Wow, good job to you too, keep it up! An advice I'll give is, if you'd like, try and build some projects too with your skills.

              I do wish I had started programming a bit earlier, not that I'd have been as good as you guys, but that would have been fun. I started in college.

              Above all, keep having fun, even if you don't like building any projects.

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

    How to solve A? :)

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

      I don't even want to see what that dog looks like.

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

    Your memes are great.

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

    Me on problem B: Got WA on pretest 2 :(

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

      how to solve problem B

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

        If one boulder falls into the collection system,the ones after it will end up in the same place.

        We can simulate the boulders' actions until one falls into the collection system.Then we can simply output -1.

        If no boulders fall into the collection system,we can just output the result of the last boulder.

        There will be at most 100n boulders that end up on a mountain,So this is an $$$O(100n)$$$ solution.

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

    Absolutely your are true.

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

    then comes me How to solve B?

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

    How to solve C :<

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

Thank U Kilani, Warawreh & Salem_Alwarawreh so much for setting problems on this round, I am sure the problems are gonna be so much fun to think of, also to solve ^^ Can't wait to participate!

Jordanian round ❤

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

Even though final exams, we don't have contest prepared by our neighbors everyday.

Jordanian round ❤

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

As a participant, I thank Khaled for drawing pictures for all the problems.

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

Looking forward to the colorful pictures!

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

Thanks for the stories and also making them skippable. They are really fun to read, but only when the contest is over :D

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

We definitely need more picture problems :) Also, please lesser of these

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

It's a joyful thing to me to see Arabic round again. Hope our contribution in problem solving community keep it's progress and see more Arabic rounds in the future.

I am realy intersted to praticipate in your round ,thank you guys.

»
3 years ago, # |
Rev. 2   Vote: I like it -34 Vote: I do not like it

I wonder who's gonna read all those interesting stories?

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

It feels so good having a contest in your birthday when you're lifeless and have nothing to do.

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

My Pledge for round #699: I will solve at least Three problems! And then declare the Fourth great Ninja War!

»
3 years ago, # |
  Vote: I like it -29 Vote: I do not like it

We hope you like the problems and enjoy solving them!

How to enjoy when one is not able to solve them? reading stories xd?

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

    The more you think about your delta, the less interesting the round becomes.

    Play your favorite song before the contest, have a sportsman spirit, and try your best not to think about failure/success during the competition.

    Have fun solving problems :D

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

      Playing my favourite song before the contest actually worked in my last contest!!

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

      Play your favorite song before the contest

      Doesn't it gives earworm sometimes ? It ruins the concentration .

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

        Not during the contest but before the contest!

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

        You are right, though I can't remember having this issue. It seems like for me, the problems are too interesting to be distracted from :)

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

As a tester, I recommend enjoying problems!

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

Kilani == Thanks :D

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it
    std::string Shanks("Shanks");
    Shanks.front()++;
    Shanks == "Thanks";
    
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -32 Vote: I do not like it

      yo how can u add one to a letter, this would runtime error.

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

        each character has a unique ASCII code where The 'S' ASCII code is 83 and the 'T' ASCII code is 84 So char('S'+1)=='T'.

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

          I guess c++ is weird.

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

            You came to the wrong place saying this. :)

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

      Best comment seen in a while... eugalt

»
3 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Pictorial explaination of all the problems, nice !! It seems an interesting round.

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

As a tester, I wish everyone good luck!

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

Downvote this comment for ancient goodluck curse !

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

Irrelevant

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

As a participant, I'm happy with the frequency of the contests! ;)

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

Hope it will be a good round

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

What's the point of stories in problems if they are skippable? Like tourist mentioned in one of his streams, the stories must sync in with the problems themselves, similar to like Google Codejam's problems. Otherwise, why not just remove stories altogether for the problems that do not require such?

In any case, hopefully, the contest will be enjoyable.

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

    It has happened where the story and the statement do sync up, but the authors just choose to separate it to make it easier for participants. They separate the informal statement and the formal one, so participants can choose whether they want to read it or not. I personally like this choice, because it makes the problems more enjoyable for the participants (and the authors to write), without getting in the way of the actual problem solving if the participant doesn't actually want to read it.

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

.

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

Hello.

»
3 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Tonight I can write the saddest lines.

Write, for example, “The night is starry and the blue stars shiver in the distance.”

The night wind revolves in the sky and sings.

Tonight I can write the saddest lines. I loved her, and sometimes she loved me too.

Through nights like this one I held her in my arms. I kissed her again and again under the endless sky.

She loved me sometimes, and I loved her too. How could one not have loved her great still eyes.

Tonight I can write the saddest lines. To think that I do not have her. To feel that I have lost her.

To hear the immense night, still more immense without her. And the verse falls to the soul like dew to the pasture.

What does it matter that my love could not keep her. The night is starry and she is not with me.

This is all. In the distance someone is singing. In the distance. My soul is not satisfied that it has lost her.

My sight tries to find her as though to bring her closer. My heart looks for her, and she is not with me.

The same night whitening the same trees. We, of that time, are no longer the same.

I no longer love her, that’s certain, but how I loved her. My voice tried to find the wind to touch her hearing.

Another’s. She will be another’s. As she was before my kisses. Her voice, her bright body. Her infinite eyes.

I no longer love her, that’s certain, but maybe I love her. Love is so short, forgetting is so long.

Because through nights like this one I held her in my arms my soul is not satisfied that it has lost her.

Though this be the last pain that she makes me suffer and these the last verses that I write for her.

  • Pablo Neruda
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

The contests are very rewarding I will be participating in the upcoming contests.

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

Hope to be Master

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

Shanks, Salem_Alwarawreh and Warawreh thankyou to all of you for another contest.

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

Expecting the problems difficulty order to A<B<C rather than (A or B)<C<(B or A).

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

All the best to everyone participating in the contest.

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

If existing muti-solve in problemC, just output a random one?

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

Hello who can point me to a good tutorial covering graphs topic?

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

    Go for Competitive Programmer's Hand book by antti laaksonen. There graphs are explained very well. the you can simply try for simple problems.

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

Tasks was interesting. Thank you

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

Why are C's and D's implementations so dirty?

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

    don't know about C, but D wasn't implementation heavy.

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

      C wasn't too.

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

      How to solve D?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 6   Vote: I like it +7 Vote: I do not like it

        For odd $$$m$$$, we can see that any sequence of the form $$$i, j, i, \ldots$$$ is valid as it will either be something like $$$ab \ldots ba$$$ or $$$a \ldots a$$$.

        For even, lets notice that a sufficient condition for the answer to exist is at least one of the following two conditions:

        1. A node pair of nodes $$$x, y$$$ such that $$$x \rightarrow y$$$ and $$$y \rightarrow x$$$ are coloured similarly (the sequence will be of the form $$$a \ldots a$$$ or $$$b \ldots b$$$)

        2. A node $$$x$$$ such that it has an edge $$$i \rightarrow x$$$ into it and an edge $$$x \rightarrow j$$$ out of it with the same colour, then $$$j \rightarrow x$$$ and $$$x \rightarrow i$$$ will have the opposite colour (or condition 1 will hold). So we can just generate a sequence of the form $$$aa(bbaa)*$$$ or $$$(abba)*$$$ as needed to satisfy $$$m \mod 4 = 2$$$ or $$$m \mod 4 = 0$$$ respectively.

        Clearly if neither of these conditions hold, any sequence generated will be of the form $$$abab\ldots$$$ or $$$baba\ldots$$$, so it is necessary as well.

        While unneeded, it can also be shown that this condition will always exist for a complete graph of $$$3$$$ or more nodes.

        Out of curiosity, is there something wrong with this proof for general graphs or is problem D just a complete graph for the sake of elegance? I think this find the answer if it exists for any arbitrary graph given that both directions exist for each edge in $$$O(n + m)$$$.

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

      How to solve D?

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

        Case working. 1. if m%2 = 1, it is possible.(1, 2, 1, 2, ..) 2. if i -> j = j -> i, it is possible (i, j, i, j, ..) 3. if n = 2 and m is even, it is impossible 4. if n >= 3 and m is even, it is always possible. It needs only 3 vertices

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

    I can see how the implementation for D could be tricky, but C's implementation seems fine, the core part of the logic could be coded in 20-30 lines using an array of vectors.

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

2 WA submissions on C for writing n instead of m and half an hour to find this bug that feels like shit especially I fu**ed in B

(dying sad dog picture)How to solve B?

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

    brute force

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

    After some boulders are thrown , the heights of mountain will become such that no case of hi<h(i+1) exists and then the boulder will always roll to the end, so we can find which ends first, k or no case of hi<h(i+1) and print the answer. Since heights are <=100 and n<=100 , it can be done with brute force.

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

      that's what I did I'm really pissed off I have no idea why it's WA

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

        Same bro I keep getting WA on test 2

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

        Bro You know more than me, but I think your code is computing the total need element to level from right to left on every term smaller than the next one. But you have to give the solution as sequence way for eg: 10 7 1 1 1 1 1 1 1 1 1 3 your code will give 6(for 9 k-2, for 8 k-2,for 7 k-2 and for 6 k-2) now k=-1; but the answer is 3(for 9 k--,for 8 k--,for 7 k--,for 6 k--,for 5 k--,..,for 3 k--) now k=0; it your code you can change a[0]=INT_MAX; and make it 1 based index then,

        if(i==n){co "-1\n";break;}
        if(a[i]<a[i+1]){
             a[i]++;
             k--;
             if(k<=0){co i<<nl;break;}
                 i--;
             }else i++;
             if(k<=0)break;
        

        in the while loop and since the constraint are 100 ans 100 it will not give tle. Hope it make some sense.

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

    As heights are less than or equal to 100 in the worst case (1,1,1..100) after throwing around 10000 stones all remaining stones will fall into waste system. So if k is greater than 10^4 answer is no else just brute force.

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

      idk about the limit when the answer will always be "NO" . I was too lazy to find out so i just break my loop when my counter reached 10^4.

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

    use 2 pointer

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

    Simple simulation.

    One fact to know is that once an boulder falls into the collection system,the ones after it will also do that.

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

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

How to solve E?

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

Can someone give a test-case for which my code fails for problem C WA_CODE

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

A great and well balanced problem-set. Also, C was a nice question, although it took me an hour to implement it and fix bugs :(.

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

I think who passed the first test case of the c problem he must pass all pretests

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

    No. I pass the first test case and wrong in test case 2 :D

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

      Same, my logic seems fine tho. Probably a stupid bug im missing

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

    Is that the case because if pretest are weak many people's solution will fail on real test in these implementation heavy questions

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

    The NOs in pretest 1 can be identified with just observing whether the color of the last painter appear in the required array. This is insufficient alone.

    Pretest one does not cover the possibility that there is not enough painters to paint all fences to the required color.

    For me, I still have not identified all the cases where it is a NO. I return NO if my own checker finds a fault in my constructive solution. This passed the pretests.

»
3 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I have codeforces account and wanted to participate in above contest. But I haven't registered for it. Why CodeForces don't allow to participate unregistered coders like me in Contest.

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

    According to rules: If you are late to register in 5 minutes before the start, you can register later during the extra registration. Extra registration opens 10 minutes after the contest starts and lasts 20 minutes.

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

B turned out to be a bluff

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

I was so close on solving D just did not have had the time... You just had to notice that when there is no such pair that edge[i][j] = edge[j][i] and when m%2 != 1 (which are the 2 conditions that one can solve very easily with constructive solutions) then you could see that if you had 3 vertices again a constructive solution is possible.

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

Loved the art! Thanks for a great contest!

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

One of the best CF rounds I have recently taken part in. Finally, we had WriteSomeCodeForces rather than omnipresent Notice1E9ThingsAndWriteOneLineForces. Kudos!

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

Can anyone help me find why my code for B always get TLE? I thought the complexity for my code is O(10^6) Thanks ;w; http://codepad.org/Nf4Rkb1n

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

May I know what is pretest 2 of B?

UPD: Managed to solve it, my brute force was not brute force enough and missed some corner cases sigh

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

    Hey, please have a look at my latest solution. I'm unable to figure out why is it failing test 2. Would be of great help!

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

      I think you misread the question? With the following input

      1
      6 4
      0 0 0 0 0 100
      

      the correct output is 2. The four thrown boulders will go to the 5th, 4th, 3rd, and 2rd mountains in that order.

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

Nice pictures in problems! I like them.

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

How to solve B?? I was getting TLE on 2nd test case.

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

    Brute force worked for me, although since k can be large you have to stop as soon as a rock goes off the end.

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

    check if your code goes wrong when n=1

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

Very nice problems set in this contest. Can anyone explain how to solve E?

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

In part D , what was needed to handle the case when there is no such pair of nodes (i,j) such that a[i][j] = a[j][i] and M was an Even number. I think this was the entire question , because rest all part were quite easy. How to solve for this case?

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

    Hint 1: Suppose a valid path exists when m is even. This implies that there must exist some nodes u, v, w such that a[u][v] = a[v][w] (Think of the middle two characters in palindromic string).

    Hint 2: Consider the case when you start at u, and the case when you start at v, and only travel between these three nodes in a cyclic fashion.

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

      Yeah, thanks lavish315 for this. Now, it is evident that if there are 3 such nodes such that a[u][v] = a[v][w]. I can complete (M-2)/2 visits between (u,w) and then end at either u or w. Take 2 more steps to go to the alternate vertex w or u. And then , continue another (M-2)/2 visits.

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

      I was wondering the proof of the existence of (u,v,w) is quite satisfactory. But , if such a (triplet)/(a cycle with all edges of same letters) does not exist , can we say for sure that solution does not exist?

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

        Yes, we can claim so. Consider m = 2k, and let say there is no such triplet. Assume that a possible path exists. Then, again by the same logic, character at position k and k+1 are same, and by contradiction, this implies that such a triplet/cycle exists.

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

    You can proof that there must be a method in three random vertices

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

    If m is even and If there are 3 edges that form the pattern aabb/bbaa when you go from 1-2-3-2-1 then answer exists and you just have to repeat the pattern or else answer is No.

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

    Hint 1: You're right, that's the case you need to figure out to solve the problem.

    Hint 2: In this case, consider 3 vertices and the path between them.

    Hint 3: In this case, if there exist distinct i,j,k such that a[i][j] = a[j][k] then does it work? What values of M does it work for?

    Hint 4: Can you make it work for the remaining values of M?

    Extra credit: What about if they don't exist, can you prove that it doesn't work? Even stronger, you can actually prove that for n>=4 there will always be i,j,k that satisfy the condition.

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

Really loved the problems! While I didn't really give my best performance (something close to the opposite actually xP) but the experience was definitely appreciable.

Huge thanks to everyone involved in the creation and conduction of the contest! :)

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

I felt this round to be more implementation based !!

»
3 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Problem D is a trash and third-class problem. Stop setting such brain-dead problems. They take away time from the really interesting problems.

Pretty sure this garbage D would have been rejected if Anton was the coordinator.

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

    problem C wasn't world class too . It was also just mess implementation .

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

    Bruh problem D is very anton-style. Your code is just awful.

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

      Most of it is just copy-paste. I am not angry about the code length. I am disappointed that it was just very obvious and all you had to do was code.

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

    Why? since when are (prove->code) problems brain-dead third class problems?

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

    I liked problem D, I don't see what here is copy-paste or brain-dead. Even more, I liked DEF, thanks setters for the contest!

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

Got to say, a great contest finally after a long time. Loved the problemset !

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

How to solve D ??
and Is CF little bit slow to browse ??

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

    You can proof that there must be a method in three random vertices

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

I didn't like problem D because even though I had the entire idea it took way too long to code it. I don't find these types of problems enjoyable. If they are interesting that is another case. But it was neither interesting nor easy to code.

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

Despite having done horribly in this contest, I'd like to say that this was a nice contest!

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

In problem A & C there are sentences like

  • You can print each letter in any case (upper or lower).

but in problem D there's not. This is only a minor issue but i think it's better to be consistent about the case of YESs and NOs.

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

Why h in B is not <= 10e9 too? With h<=10 it's just straight simulation, Div2B should be something more difficult than it.

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

Loved the problems... This went too good to be true for me...

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

When I saw problem B and see 1<k<=10^9, I thought the h must also be 10^9, so I just use a stack to implement, which take me over half an hour.

I was wondering why so many people get accepted by problem B until I see the constraint 1<h<100.

Oh, shit! If I saw this at the first glance, I will have enough time to do problem D.

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

    it took me the entire contest and I realized it in the last second :/

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

    Even with h <= 10^9 code is simple enough.

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

      Hey, can you please explain why my code is failing in TC 2? Would be of great help!!

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

        for 3 2 1 1 3 your code will give 2, but correct ans is 1

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

I'm lost 1 hour and 30 min to find the bug in problem C and I can't find it :(. I can AC D but I'm lost too much time in problem C :( This is my big lesson. Specialist time.

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

one step back to accelerate (rating -23)

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

https://codeforces.com/contest/1481/submission/106608013 Div2C could someone kindly provide me a test which causes wrong answer?

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

Why am I getting Memory Limit exceeded on this? Any help?

Submission: 106602826

»
3 years ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

Kilani Salem_Alwarawreh

Warawreh MikeMirzayanov

106611585

This is my code for Round 699 div 2 task b. I have used dynamic memory allocation for the array. In this approach i am getting memory limit exceeded. Whereas the same approach with static memory allocation works just fine. I know that i haven't deallocated the memory after every iteration but it was given that sum of n over all test cases is less than 100 so i dont see why deallocating that array after every iteration is required because at the end of the day i am only making a long long array of size 100

Please Help and point out my mistake here if any.

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

    My Condolence.

    Probably the worst way to get System Test Fail.

    Thanks for letting us know though.

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

My solution for D is wrong answer on test 2's 145th test case! Can someone give me a smaller example to debug?106582694

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

106598727 (My submission for Problem B) . Can anyone please point out why this code is failing ? I am really not able to figure out the possbile reason. Thanks.

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

    Reread the question again? If the heights of the mountains are 1, 1, and 100, then the first thrown boulder goes to the 2nd mountain, but the second thrown boulder goes to the 1st mountain.

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

      that is why I have dont i=1 after every increment.

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

        But if I'm reading your code correctly, with two boulders, you'll throw them together at the second mountain?

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

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

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

    Thanks for the quick rating change and the extra work that you have to put in for removing the cheaters!.

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

How to solve C?

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

I can't seem to figure out the mistake in C. My idea is the same as given in the tutorial. Some help would be really appreciated. Here is my submission Submission

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

Thanks for fast tutorial release

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

Here is my Screencast for today's contest, if anybody is interested in watching a noob attempt this round xD

YouTube Video

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

Thank you very for the contest

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

In Div 2 Problem C: Fence Painting

I read the editorial and tried writing it's code however it is giving me TLE, can someone please help me out?

We must first see that the most important painter is the last one (and he will paint plank x where bx=cm) because of two reasons: when he paints plank x it won't be changed and if some other painter have a color that we don't need we can make him paint plank x, which will be repainted later.

Now we need to find x where bx=cm, there are three options:

bx≠ax. bx=ax. There are no bx=cm this case is impossible and the answer is "NO". If the first two are true we choose x such that bx≠ax, then we greedily distribute all painters j (1≤j<m) such that:

There is plank i such that bi=cj and bi≠ai then the jth painter will paint plank i (as a result the color of the ith plank will be changed). There is no plank i such that bi=cj and bi≠ai then the jth painter will paint plank x. At the end there might be some planks that didn't end up as we want so we make a last liner check on all planks i and check if bi=ai, the total time is O(n).

Code Link: https://ide.geeksforgeeks.org/DqHB8ngckI

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

    The continue statement in line number 56 does not continue the outer while loop but it continues the for loop in which it is present. Hence the value of k is becoming negative there itself and so the outer while loop becomes an infinite loop, giving TLE.

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

Weak pretests :( In problem C, by mistake i did l=mid-1 and r=mid+1. I should have to assign l=mid+1 and r=mid-1. But still it passed the pretests. It's just the reverse which we have to do with some extra element from other side. Link

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

MikeMirzayanov

Problem ratings for this round have not been updated, although the ratings for the round after this (Round $$$700$$$) have been updated.

EDIT: wow, that was fast :P