Anadi's blog

Codeforces Round #647 — Thanks, Algo Muse!
By Anadi, history, 4 years ago, In English

Hello Codeforces!

We have a pleasure to invite you to Codeforces Round #647 (Div. 1) and Codeforces Round #647 (Div. 2). This round will take place on 04.06.2020 17:35 (Московское время). In both divisions, you will have 2.5 hours to solve 6 problems. Three of them will be shared.

The problems for this round were prepared by MicGor, Grzmot, Okrut and me.

We would like to thank everyone who made this round possible:

We hope you will enjoy the problem set! Good luck!

UPD: Score distribution:

  • Div 1: $$$500$$$ $$$-$$$ $$$1250$$$ $$$-$$$ $$$2000$$$ $$$-$$$ $$$2500$$$ $$$-$$$ $$$3000$$$ $$$-$$$ $$$3500$$$
  • Div 2: $$$500$$$ $$$-$$$ $$$1000$$$ $$$-$$$ $$$1500$$$ $$$-$$$ $$$2000$$$ $$$-$$$ $$$2750$$$ $$$-$$$ $$$3500$$$

UPD: Editorial

UPD: Congratulations to the winners!

Div. 1:

Div. 2

Below is a message for you from MikeMirzayanov:

AlgoMuse

With this round, we want to say thank you to Algo Muse for the significant contribution and support!

Algo Muse is an educational site that conducts online algorithmic contests in pen-and-paper style (no coding). It was originally started to help students prepare for theory qualifiers for graduate admissions. At present, the problems have a broader appeal, though occasionally an odd problem may require knowledge of linear algebra, probability, or group theory. The website is maintained by former students of IIT Bombay. To find out more, visit their website or their twitter account.

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

Comments Comments (412)
| Write comment?
»
4 years ago, # |
  Vote: I like it -59 Vote: I do not like it

orz orz

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

Thank you students from Wroclaw

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

Where is the round "Sorry, Ivan Belonogov!"?

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

    That might be the first ever div1 only contest.

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

    Where is round "Sorry, Monogon!"? tbh

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

      Btw ... why are you looking like forced for the profile picture arthurconmy ??...No offense mate ...Just curious !! XD

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

        1) I like to have the same shirt colour as my handle (hopefully one day you'll see me in a red shirt). Some other users do this, e.g AnandOza (but I think I did it first :p)

        2) I only really take photos of myself for strava, so I'd just been on a run

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

          I think I first did it on July 12th, 2019 (when I reached purple for the second time).

          Btw, mine are all the same photo, just edited. (The original shirt is blue & matched my Expert rating when I started out, by coincidence, so after I changed color I had the idea to keep the matching theme.)

          Thanks for the shoutout! :)

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

            Some people messaged me to ask how I did this. I'm by no means an editing master, but here are the steps I figured out.

            I used GIMP (free Photoshop equivalent). I used the selection tools to carefully select my shirt without selecting the rest of the picture (this was kind of tedious).

            Then I simply used the Hue-Saturation tool (https://docs.gimp.org/2.10/en/gimp-tool-hue-saturation.html has an explanation). Instead of adjusting all the colors, I just adjusted the blue (to purple or orange or whatever) by changing the hue and saturation until it looked how I wanted. (The original shirt was blue, so this way it only adjusts the shirt and not any traces of my arm that I accidentally selected.)

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

hope so,this will be a great round

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

Hoping for gradual increase in question level from A to D. Rather than a very high increase from A to B and from B to C. Thank You for contest.

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

Wow! Polish round! So proud :)

Thanks for the round :) :)

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

In parallel div1 and div2 rounds,Are participants rated above 1900 considered div1 or above 2100? Will this change after the new rating system is applied?

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

    The participants rated 1900 and above are considered as div 1 in such rounds.

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

This will be good round :D

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

Hoping for a great contest!!(Especially for me xd)

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

Hoping for short and concise problem statements!

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

My general experience of 2.5hrs round. Statements are long. Large gap in questions levels difficulty.

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

    I think the first 4 problems will be on the easier side as Div 2 D will be same as Div 1 A this time. Hopefully no sudden surge in difficulty

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

    As a tester of this round, I can say that the problems are diverse and very interesting to solve. I found the problem statements concise enough and really liked the round, so I recommend others to have fun participating in this contest.

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

Following the trend, any review from the testers?

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

    Consider a case if any of the tester wrote problem's are not good will you participate?

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

      An acknowledgement from the testers boosts the confidence of the participants, nothing else ;)

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

        Yeah but trolling them by writing it had became a trend will stop them to do so. Don't you think??

        P.S. No offence:)

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

          I think it is bad habit. Testers should not public comment before the contest. It adds no value.

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

I think that contest will be very exciting if you can hack so when testers give as such opportunity

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

Ok so this round if from Poland !

So why is Errichto missing ????

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

Another Indian round. Check the writers profile.

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

    Delusional

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

    What does it have to do with the quality of the problem set? Furthermore, they're all Polish citizens so I'd rather call it a polish round.

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

    Why Downvotes?

    Anadi Anadi Agrawal is an Indian name and his skin is brown too(from the profile picture). So the guy is definately Indian. Nothing wrong with the comment.

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

      In enlightened societies, it is common to attribute no cultural characteristics to people based on names or physical characteristics, because this is generally the motive when characteristics are used as abusive words.

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

        From what I've observed about the so-called (and usually self-proclaimed in some way) "enlightened" parts of society, it's very much not the case, they just pay lip service to the idea.

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

        Could you speak in simple words? I cannot understand your point. This is not an English class in school.

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

      I meant it in a positive way, like " Hi , everyone . I noticed something and want to tell you about it." But poeple got me wrong fast. Everyone mistook it, because some who didn't know what I wrote downvoted. Nevermind.

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

        Yeah dude, i know your intentions were pure just like mine. But people like nFlamel and spookywooky dont hesitate to label anybody a racist. It makes me sad! They would just label anyone a racist without even understanding what the comment actually means.

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

What about the score distribution tho'?

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

Im-Still-Worthy-03062020073022

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

    It was a misunderstanding. I apologized him for that.

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

      He changed his post, you can see it's first revision, i misunderstood it(as i'm not good at memes), then i posted that comment, then he sent me a privet massage complaining about my comment and he said he meant that "we are happy to see lots of contests"(and then iv'e realized i was mistaken), then i apologized him and changed my comment. I don't know what is wrong/annoying. I'm pretty sure that its not hurting anyone etc.

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

        You lost 30 seconds requesting people not to judge you.

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

          Its a good habit when you are waiting for system testing, isn't it? :D

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

          LOL that is so true

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

This website of algo muse has only 3 problems? what is this? is it under construction?

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

    Open the past contests page — there are plenty of nice problems (with solutions)

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

      I found it, but it would have been better if all problems queued at the problems page.

      Anyway, thanks Algo Muse for the significant contribution and support to codeforces.

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

I think there might be something wrong with the time link. Normally a time link is rendered as the local time for the blog reader but this one isn't.

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

Hoping for no geometry problems ....XD

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

Master Sumeet.Shirgure!!! you are master here too!!!

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

[Deleted]

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

I wish for no long queues, as there is right now.

UPD: The queue was there when I wrote this comment.

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

Tank you Algo Muse, i really liked the site and problems, I really recommend it for Computing Olympiads as a Computing Olympiads participant. I have a question, how to submit in Algo Muse?

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

I hope I can solve problem C in div1 /rating++ !!

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

51-214017

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

Hope I will get good results.
（Though often after the contest I cry：“Nooooo~，Why am I sooo noob~”）

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

    same with me. I cry then I beat some meat from the kitchen. It's all good at the end of the day.

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

is it rated

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

    Seems like your sorry ass never had one.You might have a chance if you don't copy someone else username too.

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

Thank，Algo ZBW (doge)

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

Missing this iconic line :- "Scoring distribution will be announced (just before the contest/later)".

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

Hope to solve c in this round...

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

Hope I can do well in my first Div.1 :)

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

[Help]

I am unable to register in Div-1 Contest. When I click Register It does nothing.

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

    Because your rating is too low to participate in Division 1. Participate in Division 2 instead.

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

    Believe me..it's for your own good.. XD

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

I wish high rating to all contestants and high contribution to writers ;)

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

Hey, guys!

Right after contest ends, we will discuss the problemset live on Algopedia: https://youtu.be/ZPQzYDf5A4Y

Good luck to all!

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

    Hacked!

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

      GG bruh, I figured out during the livestream that I messed up one case :))

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

        Romeo, I took your advice and started wearing blazers while coding. Now my GF thinks that I am a psycho wearing blazer and shorts in the middle of the night. We broke up. Now I am crying. Y_Y

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

Thank you, Algo Muse! A very good website indeed. Thank you for your support.

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

Hope I can solve 3 of 6 successfully
Good luck to you all！ :D

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

How many shared problems will be?

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

    Three problems will be shared (announcement).

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

:(

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

Excited to solve the contest,happy coding.

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

Why so few registrants(compared with the previous several contests)?

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

    May be people are going back to their regular life like before covid-19 in many countries.

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

    Because of time (?

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

Only red and orange coordinators this time... 3rd question might me little more interesting

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

Where are the funny memes, why aren't they here?(.

I think it will not be interesting if this blog will be without memes (

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

    I don't think memes are a good idea for a programming competition, not all people find them funny.

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

      just before that, there were memes at many blog contests and many of these memes took a lot of plus(i don't think that they were not funny if anybody plussed);

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

Is this a rated contest or not?

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

Looking forward to the contest. But I wonder why the number of registrations is less than usual.

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

    Lockdown is getting over at many places. So people are getting busy with their daily works. That might be the reason behind less no of registration.

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

    It is just around $$$20k$$$ both divisions combined.

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

tourist gonna make it to the top again today

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

Can anyone tell me what does "Algo Muse" mean?

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

    Algo Muse is an educational site that conducts online algorithmic contests in pen-and-paper style (no coding)!

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

cf-3

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

I'm not sure exactly why, but Div 1C sucked all joy and happiness out of my soul. I haven't hated a problem this much in a while.

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

    +++

    The beauty of a connection of pearls in colors $$$u$$$ and $$$v$$$ is defined as follows: let $$$2^k$$$ be the greatest power of two dividing $$$u \oplus v$$$ — exclusive or of $$$u$$$ and $$$v$$$. Then the beauty equals $$$k$$$. If $$$u = v$$$, you may assume that beauty is equal to 20.

    "Beauty"

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

    I agree with you. The statement was boring. Moreover, the problem was stated quite weirdly and could definitely have been much simpler. Even though I got the solution a while before the end, I chose to sit back and enjoy the other problems rather than waste precious time implementing something that is so irritating.

    (The other problems were good (Okay, really — B was just some implementation) though.)

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

    It's quite standard, yeah. Try all possible answers — take the last $$$b$$$ bits, convert it into the domino cycle problem, find an Euler cycle.

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

why A->C are all the binary related problems?

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

Am I the only one who thinks that the gap between Div2-D and Div2-E was HUGE ?

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

    I thought so but look at Div1 submissions (Div1A vs Div1B) :)

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

    I think that problem statement for D was way too difficult to understand. That really did bridge up the gap

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

Is there a special reason why the limits have to be so high so Python solutions are too slow? I mean at div2D there is no reason to set the limit at 5*10^5 when classic 10^5 or 2*10^5 would work just fine. What kind of solutions are you trying to prevent setting the limits so high?

Otherwise a nice contest with interesting problems, but the TLEs at D and E completely frustrated me on this one ...

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

what a bitforces contest

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

Calling an arbitrary number in the input $$$p$$$ is not a good idea? I think $$$m$$$ or $$$a$$$ would be a more justified choice.

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

Statement for Div 2 D was a little unclear in my opinion..

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

    Stupid D... They even changed the statement a bit.

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

      Statements caused me 45 minutes to understand. Foolishness caused my rest 30 minutes.

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

    Even after reading the same statement for 1Hr. Can't understand what is going on

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

"It should have 1 hour contest" -- my feelings after solving A,B,C :P

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

Anyone wasted time on B ignoring the sum of n over all test cases statement?

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

Participants.

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

    So your D failed system test. So prefer investing your time in checking for boundary cases inseting of posting this meme all time. You solved D on 8:56. So you were having enough time to atleast recheck your submissions(if you are unable to move further) but no you prefer showing off. Now enjoy failed system test

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

What would be the rating of div2D

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

    For Understanding : 3000 For solving: 1900

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

      It took me out of breath to understand the clumsier statements. And then foolishness took me to search for dfs solutions having an easy greedy one. But, finally mananged to solve a D in a div2 contest.

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

        Can you please explain your solution ?

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

          There was a checker whether answer exists or not. Suppose we have node with topic x then for each of its neighbours 1) There must be at least one node must have topic ranging from 1 to x-1. 2) No neighbouring node has value x. If answer exists: Print all blogs which has topic 1 then 2 and so on. Solution Link: 82531854

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

          a greedy solution will work.

          initialise assigned array of size n and default value =0

          now the nodes on the basis of required final topics

          for each node from sorted list.

          if any node adjacent to current if required value is same then conflict and print(-1)


else check if the required final topic of this node can be 
   assigned

          checking step : if x to be assigned to a node then all the values from 1 to x-1 should appear on the neighbours of this node (this step can be done using a set).

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

    Probably 1600 or 1700. Even though the problem statement was confusing the implementation was pretty straightforward.

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

What was test case 9 on D?

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

Solved 5 problems for the first time!

I hope the pretests on D were strong. Last time there was a problem like that with large amounts of input, my code passed pretests but not system testing ;.; I made sure my scanner was fast this time but you never know -- it was around 1700 ms on the pretest so might be a bit tight/

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

How to solve Div2E/Div1B?

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

    Sort the $$$k_i$$$'s in descending order. Put the largest $$$k_i$$$ in the first set, then add the next few $$$k_i$$$'s in the second set until the sums are the same. Repeat this process until there are no more $$$k_i$$$'s to choose from.

    The key observation is that when you have $$$p$$$ $$$p^{x}$$$'s, that's equivalent to having a single $$$p^{x+1}$$$. You can keep a list $$$L$$$ of all your $$$k_i$$$'s and combine the last $$$p$$$ elements once $$$L[m-p+1] = L[m]$$$ where $$$m$$$ is the current length of $$$L$$$.

    My submission

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

      You meant it is equivalent to have p^(x+1) and not (p+1)^x ?

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

        Yes, thanks :)

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

          I thought of a solution on these lines but was totally clueless since couldn't prove nor my intuition agree to this.

          Any ideas on the proof that this should work?

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

            Consider writing some number $$$X$$$ in base $$$p$$$. Then, $$$X = a_0p^0 + a_1p^1 + a_2p^2 + ...$$$. If any $$$a_j \ge p$$$, then we just add $$$a_j/p$$$ to $$$a_{j+1}$$$ and mod $$$a_j$$$ by $$$p$$$. At some point, all $$$a_j$$$ will be strictly less than $$$p$$$.

            For every $$$k_i$$$, we're adding 1 to $$$a_{k_i}$$$. Because of the sorting order, this means that we'll always be adding values less than or equal to the largest $$$k_i$$$. Each contribution only adds 1 to some number of $$$a_j$$$'s where $$$k_i \le j \le k_{max}$$$, so we'll never overshoot the first set's sum.

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

      I used the same logic but got WA on TC 7. Now I feel so bad. Could've been the first time I solved E.

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

How to solve E?

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

What was the point of making div1D a geometry problem? Forcing us to angle sort adds nothing to the problem.

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

    It was initially a little bit different, and it just stayed in our heads in that form.

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

Did anyone else spend long hours debugging Div1C because they did not check whether the graph is connected when checking whether Euler cycle exists?

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

Still got no clue what happened in problem after reading div1A statement for three times.

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

I doubted my English Reading Skills after Reading Div2 D.

PS :I feel D was easy but difficult to decipher what is asked to do!

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

    Same lol, I solved it at last but it's too late to submit

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

Idk how people solved C that easily I guess I solved it the hard way

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

    I just feel : lets try doing this and it worked, then proof by pretests passed!

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

    what was your logic?

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

      I don't know how to explain it in English here's my Submission

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

      Try writing some numbers (till 11 maybe ) in binary, now try to find out contribution from each bit position of all numbers to final answer. There can be at most 63 bits in number and contribution from the ith bit is n/2^i.

      My code :

      void solve() throws Exception {
   int t=ni();
   while(t-->0){
        long n=nl();
        long ans = 0;
        for(int i=0;i<63;++i){
            
            ans+=(n/(1L<<i));
        }
        pn(ans);
 
   }
}
      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Speedforces for Div2

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

cf-4

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

Mfw my first integer overflow bug after like $$$10^{9}$$$ years :PepeHands:

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

How to solve D2E?

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

is D1C/D2F finding the eulerian circuit based on the graph made by splitting the numbers into sets with equivalent last k bits? If so asking for an actual necklace seems kind of pointless.

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

    Yes, and that's what makes asking for actual necklace useful. Otherwise you could guess conditions for euler circuit without really understanding solution, and it was an actual coding problem for once before d1 D! (I got stupid tle though...)

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

    Yes. It is finding an Eulerian circuit.

    However, the algorithm to actually find the circuit is a separate, and significantly harder algorithm than only checking whether the circuit exists.

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

      May someone point me to resources for Graph Algorithms? I reduced it to the fact that we needed to find Eulerian circuit but did not know how to.

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

        I think it's covered in pllk's Competitive Programmer's Handbook

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

Can someone please help me figure out my solution for Div2E fails hidden tests?

82562768

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

How can I test my solution before the system test's done?

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

Am i the only one that wasn't able to understand exactly what 2D was asking?

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

    same here buddy... couldn't understand shit

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

    Finally, I knew the meaning of D but havn't got time to solve it. Even got to know a wrong meaning of D took me about half an hour.

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

    same

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

    Sorry, probably we should just put the formal statement there.

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

    Even an example was not friendly enough to understand what question was asking.

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

    & i thought that i was the only who was not able to understand this problem and cursing myself that my english is so bad. Believe me it took almost an hour to properly understand what the hell is this statement saying. Also i didn't read the line that references are bidirectional.

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

Div 1 C's statement could have been written better. The word "connection" was used to refer to both the connection between two pearls in a necklace part and a connection formed by glue. The statement also alternates between saying the glue merges two pearls into one and saying the glue forms a connection between two pearls. IMO it shouldn't be necessary to look at the sample in order to understand the problem. They should just said we have to form a necklace by gluing together pairs of pearls, and the beauty is the greatest beauty of each glue connection. This way it's clear that only the glue connections are counted.

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

DIV2 D is just like an English comprerhension which I always do to get pass the English level exam.

BTW, it's so frustrated to konw in the last few minutes before the contest is over that the points are only referenced with its neighbors not the whole graph which they can get to. Havnt got much time to solve the new realized D. Ratings down again :(

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

Imagine competing from a train and waiting till you exit a tunnel so you could submit.

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

    You are lucky you even got internet connection. I once tried to do that and it sucked so bad.

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

      4G on phone, the coverage isn't perfect but it's decent. There's supposed to be free wifi in the train, but it doesn't work... unsurprisingly.

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

        Is there really so many tunnels in the route where you were travelling??

        Which route were you in that tunnels were so frequent that it was affecting submissions??

        No offense

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

          Bruh Slovakia is mostly mountains. Trains go along rivers when they can, but sometimes it's just a mix of tunnels and thin valleys between mountains where no internet exists.

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

            Can you justify the third line of your template :)

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

    Imagine not to eat anything for about 12 hours and taking part in a contest in the last 2 hours. :(

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

spend over 1 hr on that B and finally got brute force accepted XDD!!

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

    yeah, the only observation needed was that taking a number k greater than 1023 will make the xor with $$$a_i$$$ > 1023, and hence there is no chance to get the original array.

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

    Actually I was trying to come up with faster solution and then I saw leaderboard submissions for B were shooting like anything. So I thought maybe brute force will pass.. :D

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

Nice contest, i really liked the problemset. Thank you all who worked hard to make this nice contest.

I'm looking for the editorial :D.

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

Was Div1C pretest 13 anything special? I kept getting TLE. Edge case or a matter of optimiziation?

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

    Whenever there is Euler cycle problem on CF there is always some high-rated coder that is surprised cause he got TLE. Such surprised coders include people like Yuhao or subscriber iirc. I can almost surely tell you without looking at your code that it has some bug making it work in sth like O(nm).

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

      Yea that's likely it -- the euler cycle code in my TCR didn't compile so I wrote a new one from scratch. Asking for problems :'-)

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

      The DFS implementation is best. It's obvious that it only visits each edge once because we pop_back edges and that it visits the whole graph because it's DFS. When it doesn't work, it needs to have such a stupid bug that it doesn't give right answers almost ever. Whenever I was able to write it in such a way that I'd believe that it works, it was always correct.

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

    I didn't actually read your solution, but did you find out whether the Euler cycle code was the problem? I TLE'd on 13 as well and it turned out I needed to fix constant factor optimization (later TLE'd on 14 and 17 as well), but my solution didn't use Euler cycle code and had really high constant factor so perhaps that's why.

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

      Yes it was as Swistakk suggested, the complexity was actually $$$O(nm)$$$. After fixing my euler cycle code it ran in half a second, so the timelimit seems fine to me. 82567726

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

"The magic glue allows Megan to merge two pearls (possibly from the same necklace part) into one."

The sentence above is from C. I looked over and over again at the statement and samples to find out what does it mean to merge two pearls into one. Could anyone help?

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

    Me too, he meant to connect them. ( to then form a necklace at the end )

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

Div1C statement should be: "Given edges, numbers. Write Euler cycle. Hate answer recovery".

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

took me hours to understand 2D, I really hope it was more friendly and easy to read.

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

    Can you explain your solution ?

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

      I would love to, but still, it was last minutes implementation. I still worried if it can pass the system test or not.

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

      Just use greedy technique start filling nodes in increasing value order 1->2->3.....so on. U will understand in better way if u will do some paper work.

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

      turn out i got an accepted. So here's my implementation.

      For each vertex, i find if it was possible to make this vertex have its topic. For vertex u that desired to be in topic tu, i check if the neighbors (adjacent vertexes) have every topic between 1 and tu − 1(inclusive). If vertex u is desired for topic 5, I check if the neighbors have at least a vertex with a topic between 1 and 4(inclusive). If there are no neighbors with topic x for 1 ≤ x ≤ 4, the answer should be "-1". If a vertex has topic 1 i just ignore it, because there is no topic below '1'.

      It's also impossible to find a valid answer if a vertex has an adjacent vertex that has a same topic.

      To find the permutation i used Dijkstra that sort vertexes by their topic(ascending) using a set. First, i push vertex with topic 1, next when accessing u if there is an adjacent vertex that has topic tu + 1, i also pushed the vertex into the set. Lastly when i accessed a vertex i push that one in vector to print the answer later. If i cannot visit all vertex then there is no answer.

      I tried to explain as best as i could sorry for my bad english.

      Edit: fixed some error.

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

    same here

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

    A friend of mine asked me to rephrase the question, so they could understand it better.

    Maybe this could help others too.

    There are N nodes with M bidirectional edges connecting them, each node has no "value" currently.

    You can do an operation to a node, which is as follows: Define S as the set which contains all values of its neighboring nodes (that have values set to them), then take the smallest positive integer that is not in that set.

    Edit : If set S is empty, the smallest positive integer would be 1.

    Given the final values of all nodes, determine the order to do these operations to the nodes (each node can only be applied with an operation once) or if it is impossible.

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

      What if the set is empty ? Btw great explanation, this is how problem statements should be.

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

        If the set is empty, then we should take the smallest positive integer that is not in the set, which is 1.

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

        Thanks for the feedback, I fixed it.

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

Where did i mess up in B: 82560946?

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

    Can you please explain your approach I am not able to get what you are doing with this code ?

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

      Brute force from 1 to 2050. And then checking if the resultant array after xor-ing has same elements as original array.

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

        I think you messed up in frequency count in one place you are setting 1 for all the entries and when inside the loop you are using ++ which may be the cause ! You should have used Freq[i]++ in the first loop itself

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

          I did that in my previous submission. Only difference is that i also handled the case for n = 1 in that. So, idk. :(

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

    You also need to check how many a number appear in the desired set, not only if it appears in the set or not.

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

    If I understand your code correctly, you should have checked f[x[j]] == freq[x[j]] instead of f[x[j]] == 1 && freq[x[j]] == 1. My approach was to sort the XOR-ed array and compare it with the original one element-by-element: 82500274

    Edit: turns out you can even use the == operator for vector, which makes it even easier: 82567200

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

      According to the statement, every integer in the set is unique so it must occur only once right?

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

    .

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

How to solve div2-D?

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

    My solving: for each target number from least to biggest we trying to put this number to the vertices and check (using set and it`s size), is it smallest possible number and is it possible to put it to the current vertice.

    Here is submission

    Sorry for my english.

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

    a greedy solution will work.

    initialise assigned array of size n and default value =0

    now the nodes on the basis of required final topics


    for each node from sorted list.


       if any node adjacent to current if required value is same then conflict and print(-1)


      else check if the required final topic of this node can be  assigned


checking step : if x to be assigned to a node then all the values from 1 to x-1 should appear on the neighbours of this node (this step can be done using a set).
    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pick topic in increasing order and check if you can assign it to its respective blog(say curr). What to check : In the adjacency list are the blogs referenced to curr. See what topics are assigned to these blogs. Find the smallest positive topic(say temp) not assigned to these blogs

    Spoiler

    If temp == topic assign topic to curr and continue. Else ans is not possible. Sorry if my language is unclear, for reference you can see my submission

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

Ah! Submitted div2-D at the last minute. But server was busy. Several minutes later I saw that it did not get submitted.

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

For C : Why does "<<" results in overflow for finding power of a number? My solution failed for "1<<(i+1)" but worked for "pow(2,i+1)" // after contest :(

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

can somebody please explain div 2-D statement.

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

Does D2C answer fit in long long? i got wa on pretest 4 and then thought answer might not fit in ll, but time was over then.

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

Statement of C was terrible. But not in the "broken English" way, because English was fine, but it used a lot of confusing expression. Merging/gluing/chain/necklace parts etc. it was all very confusing. It took me about 10 minutes to understand the statement and 10 seconds to come up with the solution once I understood it.

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

Statement for Div2D was pretty hard to comprehend & difficulty gap between Div2D & Div2E pretty huge, but besides that I really enjoyed the contest!

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

Skipped div2C for div2D and ruined the contest. I am still not able to understand what question D is asking.

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

    Sigh. Had over 1 hour to solve D, but just couldn't understand what it was asking for. Still don't..

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

What's wrong with this Div2 D / Div 1 A?

https://mirror.codeforces.com/contest/1362/submission/82556780

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

    me too on pretest 5

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

    it is the case when like we have to put 5 on the current node and its adjacent nodes contain 1 2 3 3.

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

      Could you provide a concrete input/output example?

      Here:

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

      Isn't the answer supposed to be -1?

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

        yup actually i also once got wrong ans on TC5 and then i found my algo is not working on that type of cases that i proposed earlier

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

          Yeah, thanks. I can't find a small case for which it fails.

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

For the first time, I was on the verge on solving E during contest.

My logic was to first sort the numbers in reverse order. I'll always add the first number to the result. Then I maintain two variables rem and currency. rem denotes the number of elements equal to currency required to make the result zero. In each iteration, if rem is greater than zero, I subtract the element from the result. Otherwise, I add the element to the result and set rem to 1. I make sure to update both rem and currency as required while I loop through the array. I could get 7 testcases to pass.

Could you find the flaw in the code or the logic? 82557476

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

I don't know how but I get RTE for div2D/div1A. My algorithm is quite straight forward, but somehow get RTE when trying to sort g[u]: the list of adjacent nodes for node u in the increasing order of t[].

Can anyone help?. Here is my submission

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

Lol didn't notice that sum of n over all test cases will not exceed 1024. :P

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

    XD i spend over 1 hr on that tho i finally got that!! i was lucky XDD

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

The questions were fun to solve. It should be called Codeforces Round #647 — The Bitmask.

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

![ ](Drake-04062020224740.jpg)

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

Free Fall!!! I hope just don't die :(

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

I was done with Solution of B. P00R ME

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

    My Code:

    Can anyone figure out what extra things out i have done

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

      There was no need of having array of size 2050, moreover you could have returned false even when b[i] exceeded 1025.

      And you are declaring two new arrays in each function call, you could have done by declaring one global array and later modified it

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

        Yaa Runtime could have been better. But to be honest they were not the factors which affected.

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

      Consider this: $$$t=1000$$$ and $$$n=1$$$ for all tests. Now, you are resetting array $$$s$$$ for every check. So basically, for all checks, your code is using approx. $$$2*10^6$$$ operations $$$(1024*2050)$$$. Multiply this with the number of tests and you get $$$2*10^9$$$. Hence, TLE. Silly mistake. It can be easily overlooked. But one should have been cautious.

      I guess this happened with all the solutions that got TLE after system tests. The pretests should have included this test.

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

    Why do you expect that your O(N^3) solution should pass? Consider $$$t$$$ = 1000 and $$$n$$$ = 1 for all test cases and look at your submission you will get what i meant.

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

Hi guys, can someone help me find what's wrong on my code in div 2E/div 1B? It fails on test 4. (Submission: https://mirror.codeforces.com/contest/1362/submission/82560898 )

Explanation of my code:

I sort all the numbers in descending order. I only maintain the difference between the sums of the two sets, by storing their current power and the multiplier. First, I put the largest number on the first set (the difference is $$$p^{arr[0]}$$$, so we have $$$pow = arr[0]$$$ and $$$mult = 1$$$. After that, I iterate the array of the powers. Now, I handle various cases:

  • If the current number has the same power as the balance, I decrease mult by $$$1$$$.

  • If there is a smaller power, I try to convert the balance to that power. If at any time mult exceeds $$$n$$$, we are certain that if we continue subtracting numbers from our balance, it will always remain positive (for example if we have $$$pow = 3$$$, $$$mult = 50$$$ and $$$n = 20$$$ (and we know that all numbers that follow have pow <= 3), in the worst case our balance will end up with $$$mult = 30$$$ and nothing less!). So, we can calculate the answer from here directly!

  • Finally, if at any time we reach $$$mult = 0$$$, we know that the numbers have eliminated themselves and we have a balance of $$$0$$$. So, we can continue on the next number as set it as our new balance.

Any help appreciated!

UPD. It turned out that I messed up with the modulo operations. I am really considering writing a library for them, which I believe will reduce the time coding and the bugs that may arise on my code. Here is the accepted submission: https://mirror.codeforces.com/contest/1362/submission/82581223

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

    I believe test case 4 is testing whether your code can handle when smaller power is equal to higher powers.

    Similar test case I wrote:



    1

5 3

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

      It outputs 3, which I think it's correct.

      We have $$$3^2 - 3 - 3 - 3 + 3 = 3$$$

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

I still can't get over the fact that people read, understood and solved Div1A/Div2D in 2 mins

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

Got 2 WA in system test. Worst experience so far. :(

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

Problem D video Editorial: Solution

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

+Div1D was nice
+Div1E was nice
-A got really confusing statement
-C got really confusing statement

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

Great Contest! however have 1 Question: Who was responsible for naming these problems ? :D lol

A: Johnny and Ancient Computer. B: Johnny and His Hobbies. C: Johnny and Another Rating Drop. D: Johnny and Contribution. E: Johnny and Grandmaster. F: Johnny and Megan's Necklace.

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

    In some Polish tasks the main character is called Jasio, which we translated as Johnny

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

Can anyone explain to my why i got TLE for my submission on B? it seems like people with similar solutions got accepted.

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

    Your submission failed probably because of map but few submissions failed because their complexity was O(t * 1024 * 1024). Their complexity were independent of n.

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

why so many getting div2B wrong in system testing. I got RTE which i didn't expect

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

    ai XOR possible_value_of_k could be a greater value than 1024, i made the same mistake, realized it after i got the RTE.

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

Pls, add this test to problem B (div. 2) and rejudge

1
2
1024 1023

Many people set max size in array to 1024, insted of 2048. Eg. piegusek37 made this mistake.

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

I thought Div1C had 40 pretests (at least that's the number I've seen flash when sending the solution) and I got WA39?

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

    not sure but I think Xth system test is not neccesarily same as Xth pretest.

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

Why was the contest is against Java programmers? In DIV2 D : i keep getting TLE in java and the same solution passes in CPP.

In DIV2 B : i got AC in first go. then TLE in system Testing. And the same solution for CPP passed.

Like why?

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

    CPP is faster than other languages. Now, let's have a thing, it's unjustified to have a slow algorithm right, if yes then why it isn't unjustified to choose a slow language. Now, if you think of making the constraints a little looser, then chances are there that less efficient CPP solution gets accepted. Still discrimination.

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

      That's why they should judge java submission with 2x time limit as other platforms do. How can ever be the limit of CPP and other languages be same?

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

        Maybe it's not that the relation is linear. If it is, then maybe they would have no problem doing this.

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

          Maybe but it's a simple math that every platform do including codeforces. I don't know why they didn't in this contest.

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

    I got RTE and dont even know why. We'll get after the test cases will be shown

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

    Your solution to D was actually correct, but you needed to buffer your output. I normally use:

    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

// Code here

out.flush();

    Your fixed submission

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

Runtime Error on Test 209 :(

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

How fast is memory allocation in C++. I know that allocating a vector of size $$$n$$$ takes $$$O(n)$$$ time, but how small is the constant factor?

These 2 solutions passed system test:

https://mirror.codeforces.com/contest/1362/submission/82527658

https://mirror.codeforces.com/contest/1362/submission/82550886

And I am really perplexed as to how, especially about the second solution. I really hoped to hack one of them. Thankfully I typed them by hand, before submitting a hack, and avoided getting -50.

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

Extremely weak pretests for D2 B. Testcases with Maximum Value in the constraints should be added in the pretests too. Many people have suffered because of this. Although I totally understand that it was our mistake but if in the contest it showed RTE, many people would have rectified the mistake then and there only.

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

can someone explain why this code is wrong for Div2 C.? MyCode

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

    That program might have a precision error caused by pow.

    To avoid the usage of pow you may simply write count += (n>>i); instead of count += n/pow(2,i);.

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

B can be solved with easy implementation. 82524666

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

System testing stuck at 100% :(

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

Time Limit Exceeded on test 210 on C. Guess I was stupid to have $$$O(\log 20)$$$ as a constant factor :facepalm:

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

    Was it possible to solve it simply in $$$O(n)$$$? I got $$$O(20n)$$$ firstly, got TLE on a pretest and changed it to $$$O(n \cdot \log 20)$$$ and got AC

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

      I had a $$$O(\log n)$$$ factor because I was using sets to access the adjacency list and recover the solution (which I also tried to optimize but not completely), but didn't realize that (and bother to) I can remove the $$$O(\log n)$$$ easily during the binary search.

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

        I didn't binary search, just checked the existence of an Euler cycle for decreasing answers and constructed one when I first found that it exists. It's $$$O(20N+2^{20})$$$, but the slowest part consists of only reasonably fast operations — constructing a graph and BFSing it.

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

      Sadly i got no TLE on pretests with $$$O(20n)$$$. T_T

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

Two questions:

Problem C: Can someone explain why n /= 2 and n /= (long long)2 will get different results? I spent an hour debugging this for problem C, kind of feel silly.

Problem D: https://mirror.codeforces.com/contest/1362/submission/82560812: I used the same greedy method as everyone else, adding nodes in by topic order and checking to see that the minimum topic is equal to the target topic. Is there something wrong with my approach? Thanks! EDIT: Instead of pushing the node indices into an answer vector, I just directly printed them out at the end. Not sure why my original gets a WA though, should be doing the same thing...

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

    /= operator typecasts long long to int(long long/=int) . You can use 2ll to fix this issue. Happened with me too. You can try this code to check.

    #include <bits/stdc++.h>

using namespace std;

int main()
{
  long long x;
  x = 5;
  x*=2;
  x = INT_MAX+5;
  cout << x;
  return 0;
}

    C++ even gives a warning for this.-Woverflow, you can add these to catch such mistakes.

    As for D, there were two things that should have been checked.

    1. Any neighbours must not have the same value.

    2. If you are giving topic x to some node/blog. All the values from 1 to x-1 should be present in neighbouring nodes. You can see my solution, if that helps Solution

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

      Hi! Thanks for your insight on C. Turns out my submission for D should be correct, it's just for some reason printf gets WA while cout gets Accepted:

      https://mirror.codeforces.com/blog/entry/78276#comment-636114

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

        You should not use ios::sync_with_stdio(false); if you want to use C styled I/O in C++ code.

        By default, C and C++ streams are synced together allowing you to use cout and printf together. But after this statement printf can give undefined behaviour.

        You can read up more on this here

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

          I see, that sucks. Guess I learned my lesson the hard way through a 2000 point problem

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

            Yeah true, I agree, if that happened to me I would have cried rivers.

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

Screencast

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

I solved C by searching oeis.

Who else thinks codeforces should stop setting problems those can be solved by searching online?

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

    Do you think it's that easy to come up with an original problem that is, at the same time, expected to be of a specific difficulty

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

can someone tell me problrm in my code got WA on test case 8 (https://mirror.codeforces.com/problemset/submission/1362/82536959)

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

    1

    576460752303423487

    check for this case it is wrong for this test case

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

      Tell me why its coming wrong on this test case , I think pow function is not behaving properly in high values. There is nothing wrong in logic.

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

        No log is creating the problem there is no problem in power function

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

What's special in Test Case 6 of Div2 D?

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

Was it just me who didn't read B properly initially that sum of all n do not exceed 1024 ?. I was thinking of O(n) solution from the beginning.

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

nice contest... but i think u guys should keep the time constraint somewhat flexible... Solved E after 11 wrong submissions caused due to silly mistake but was somewhat happy which finally got TLE :-(

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

Congrats to the first ever Lebanese to make it to Top 2!

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

Why log2 gives wrong answer for bigger values??? In test case 8 of C, it is giving log2((2^n) — 1) = n!!! Why??? Can anyone explain.

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

My rating isn't improving because I am not able to solve any question .But , since I talk too much , my contribution is more than my rating! Jokes apart(gosh) , I want to solve at least one question . Give me some advice .

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

    Brother,Upsolve the problems(not all but of your level) which you were not able to solve in the contest by looking at the editorial.Understand the solution by paperwork.

    Just Keep Practicing and you will do it !!

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

      Thanks a lot man. Every piece of advice means a lot.

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

how is it possible? for n=765228007342234864, ceil(n/2.0) and (n+1)/2 give different answer.

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

    A double uses less bits for the number part than a 64-bit integer.

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

      but n has long long type

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

        You devide by 2.0, the result is double. Or in other words: Do not use these double functions here, use int arithmetic instead.

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

Setting OEIS task must be banned it took me 60-70 minutes to just realise the pattern and solving the formula with bitmasking and observations after this task I was not having much time to solve an easy DIV2 D which was purely implementation based and I suck in implementation ,really I suck.

And that compared to another person who just googled it out breaks the spirit of competition and I think codeforces is not meant for such activities . Hope problem setters will not set OEIS tasks in future. Actually those who solve or do the competitive programming for learning or as a hobby and purely for improving their problem solving skills will never google out this things but such contestants are fewer and too fewer nowadays as ratism is prevailing over the programmers and they want to get ratings either by hook or crook ,which in long run is not gonna benefit. Thus Hoping my comment provides message to all those who are googling solutions during the contest.Please be motivated and happy coding

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

Respected codeforces team, I submitted a code for problem c of div2,http://mirror.codeforces.com/contest/1362/problem/C, which gave WA on pretests 3 i.e. for n=8 when I submitted it in GNU G++17 7.3.0. but when i submitted that same code on GNUG++ 14 6.4.0 after the contest got ended it got accepted. when i ran the same code codechef ide on gnu g++ 17 7.3.0 it gave correct ans for n=8 i.e 15,but on codeforces it gave 14 for n=8. though my solution was correct it got wa .i need help. please clear my doubt why this happened.82561627,http://mirror.codeforces.com/contest/1362/submission/82561627, was the code id which gave wa. 82568946,http://mirror.codeforces.com/contest/1362/submission/82568946, was the code id of same code which got accepted. Anadi please help me.

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

Problem A taught me the difference between if(n&(n-1)!=0) and if((n&(n-1))!=0) . Two curly brackets hurts a lot.

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

Can you explain WTH is wrong with my solution? Code

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

I think that the problem statements would have been a little more concise. How does it make sense to give formal statements after the full fairy tale? Either don't add them or at least, please separate the story part and the formal statement it actually breaks the flow. One has to change its state of mind from algorithmic computing to English comprehension order to get the problem a statement into their head (and then after reading a full paragraph you see a to the point formal statement XD) Screenshot-163.jpg (I wont say anything for problem D)

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

Weak System tests for D1A, should have included the following testcase:

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

    My submission for D1A passed all system tests. But clearly would have failed on this one. I don't deserve the positive delta :(

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

    HOW , it was clearly written no multiple edges

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

      The line 2 1 denotes n and m respectively.

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

please help me i have received a message saying that i have done plagiarism. how to solve this issue??

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

    To solve this issue just do one thing : stop doing plagiarism :)

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

Div2 D is really just asking for a greedy coloring order for a given coloring. If you know these terms, you probably recognized what the question was asking very quickly.

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

Is the contest not rated? Why haven't the ratings changed?

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

Understanding problem D was harder than solving it. It took me around 10 minutes to think of the solution, next 5-8 minutes to implement it, but BOOM the contest is over cause it took me like 50 minutes to just understand the problem statement!!

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

    I can feel your pain bro when you miss it by just a few minutes because you were caught with understanding those fairy tales XD

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

For Problem Div2.D:

I tried my solution from the contest with cout instead of printf and it got accepted. Can someone look into this:

My first submission during the contest (using printf, WA on test 9): https://mirror.codeforces.com/contest/1362/submission/82550037

Post-contest (using cout, Accepted): https://mirror.codeforces.com/contest/1362/submission/82573015

Edit (Resolved): Dumb ios::sync_with_stdio issue, I honestly feel robbed.

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

    I got RE on Tc9 since my max global (maxn) value was 1e5, I kept overlooking the constraint till the contest got over. Later changing maxn, solution got accepted. lol!

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

this submission is similar to this submission.
Only difference is first solution uses log2 and second solution uses a while loop for finding perfect power of 2 less than n. But first got failed and second got passed. Why?

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

    Because log2() doesn't take long long or unsigned long long arguments it will make overflow in log2 function and wrong result will occur thus.

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

      But according to cplusplus.com the log2 function is overloaded and is handled by suitable integral type, so there is no possibility of overflow.

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

    It's probably floating point error.

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

Nice problems, a bit harsh, yet interesting.

Thank you for the contest!

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

Can anyone tell me why it is wrong to take the maximum of all previously assigned topics to reference blogs in problem Div2/D.

Because I have already sorted the blog in increasing order of topic. Like in the below code why the First one is wrong and the Second one is correct.

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

    The first code, given neighbors $$$\{1, 3\}$$$, looks like it will happily assign $$$val = 4$$$.
    Meanwhile, the correct answer is -1 ($$$2$$$ is missing).

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

      By neighbors $$$ $$${$$$ 1, 3 $$$}$$$ $$$ did you mean the topic assigned to neighbors? But as I have already sorted blogs in increasing order of topic so for the neighbour with topic value $$$3$$$ let call it $$$k$$$, $$$ans[k]$$$ would be false, hence $$$val$$$ should be $$$1$$$. I don't understand what I am missing.

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

        Huh? Every vertex has its own set of neighbors. Consider the case where vertex with value $$$3$$$ has a neighbor with value $$$2$$$, but vertex with value $$$4$$$ doesn't have a neighbor with value $$$2$$$.

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

1361B - Johnny and Grandmaster

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

Here's an unusual mistake: precision error because of catastrophic cancellation.

I got WA on test 230 in 1361D - Johnny and James (submission 82542917) and it took me quite some time to understand it. I compute the answer for $$$N = K$$$ first and then subtract the not-taken elements. The issue is that this creates a temporary answer of magnitude $$$C \cdot N^2$$$ (where $$$C$$$ is coordinates limit), while later I want to get something of magnitude $$$C \cdot K^2$$$ after a lot of subtractions. To give you a rough idea, this means subtracting two numbers around $$$10^{20}$$$ to get a result of $$$10^9$$$. This causes an error multiplied by $$$(\frac{N}{K})^2$$$, so around $$$10^{-5}$$$ instead of standard $$$10^{-15}$$$ that long doubles can handle, and hence WA. It's interesting that my solution would likely work if there was a constraint $$$K \geq 500$$$ or e.g. $$$N \leq 1000$$$.

It was very difficult to fix my solution to avoid subtraction of huge numbers but I managed to 82576893. Lesson is: don't subtract real values if you don't need to.

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

    Wow, so it does actually happen in this problem.

    In such case, something in the spirit of Kahan summation should help. Basically, we can keep track of the next-significant term in a second variable. And we only expect to subtract one exact term from the sum, right? Should be quite enough then.

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

    I originally wanted to subtract in D, but then I realised that it's not actually a trick that makes the problem much easier to solve, but slightly harder, because it's a less straightforward way to think about formulas.

    It's debug() << "easy pizi";.

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

Can someone slowly explain me what 2D is asking, please?

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

    You are given a network of blogs (vertices) along with their connections (edges). Each vertex can contain any of the n topics. However, each vertex contains only one topic. Now, you are also given an array that tells what topic each blog should contain. While assigning topics to the vertices, you follow this rule- among all the topics that the neighboring vertices contain, you fill the current vertex with the topic with the smallest number that is not present in neighboring vertices. You are asked to determine a way of assigning topics to each vertex so that you can reach the desired configuration. For the sample test:

    3 3 
1 2
2 3
3 1
2 1 3

    In this test, vertex 1 should have topic 2, vertex 2 should have topic 1 and vertex 3 should have topic 3. This can be achieved by first assigning a topic to vertex 2. Since none of its neighbors have any topic yet, it is assigned topic 1. After that, assign a topic to vertex 1. Since its neighbors have topics {1}, the smallest topic not present in this set is 2 and thus vertex 1 is assigned topic 2. Finally, while assigning topic to vertex 3, we see that its neighbors have topics {1, 2}. So, vertex 3 is assigned the topic 3. And so answer for this test case becomes

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

    see in short, the question means, you are given the graph and the expected colors for ith node in graph, now you have to find the order in which you will color the nodes.but you cannot chose any color as you want, lets say all nodes are currently colored 0, so if u chose ith node to color first, you must color it with mex of the neighbours( mex is minimum excluded number like in seq 0,1,2,4,5 the mex value is 3), hence when all neighbors are 0 you must color the node with 1., make the sequence of its neighbors and color it with that mex value. so follwing this rules if you could achieve the given colors for ith node, put the order in which you will color the node for possible answer, else put -1

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

In problem Div1B (Div2E), only last 2 lines of problem statement would perfectly describe the problem. Wouldn't have been nicer? a problem statement with 2 lines?

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

Problem should be easy to understand but hard to solve. But my idea is wrong on div2-D.

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

I've read the problem statement for Div2 D for nearly one hour and a half. However, I understand nothing.

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

Div 2D competes for the worst statement award with Kickstart'20 Round C 2nd question

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

can someone explain div 2 E

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

Among Johnny's numerous hobbies, there are two seemingly harmless ones: applying bitwise operations and sneaking into his dad's office. As it is usually the case with small children, Johnny is unaware that combining these two activities can get him in a lot of trouble.

What kind of small children Jonny is? I am confused.

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

Can anyone help me figure out test case 6 for div 2 -D My code is printing -1 instead of actual answer

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

    I also got WA on that test case during the contest, but in my approach, I utilized a BFS, and I forgot to marc the vertices, but after fixing that the solution was accepted. See my submission

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

Nice contest!

→ Reply