manish.17's blog

By manish.17, 7 months ago, In English

omg hi Codeforces!

ScarletS, flamestorm, fishy15, saarang, lookcook and I are glad to invite you to our Codeforces round, Codeforces Round #766 (Div. 2), which will be held on 15.01.2022 17:35 (Московское время). This round will be rated for participants with rating lower than 2100.

We would like to thank:

You will have 2 hours to work on (and solve!) 6 problems. There will be at most five hundred interactive problems in the round. Make sure to read this blog and familiarize yourself with these types of problems before the round! You are highly encouraged to read all the problems ;).

Good luck, and see you on the scoreboard!

UPD1: Thanks to the testers ak2006 for making video editorials for most of the problems, and namanbansal013 who will be streaming solutions after the round!

UPD2: The score distribution is $$$500-1250-1250-1750-2000-2750$$$.

UPD3: The editorial is available here.

UPD4: Congrats to the winners!

Div. 2:

  1. yxh_loves_lxr

  2. Alan_boyfriend

  3. proton1126

  4. raingirl

  5. yincheng01

Div. 1 + 2:

  1. neal

  2. qazswedx2

  3. hitonanode

  4. Bench0310

  5. m_99

We hope you enjoyed the round. Look forward to our next one!

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

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

As a problemsetter, each upvote on this comment equals one time I'll roast saarang

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

    Next time tell me the comment I need to write in the announcement.

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

      Good luck to everyone and I wish the experts become candidates

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

        Wish for the Candidate Masters also. Imagine bullying all of them with one comment. :(

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

          I want everyone to be legendary grandmasters:D Good luck to everyone in this contest.

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

As a tester, I was very useful!

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

looks like this one is skribbl bois round :catthink:

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

As a tester, I can guarantee this round will be very geniosity!!

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

$$$OMG$$$ ! What's the difference between $$$ indian $$$ $$$ round $$$ and other $$$rounds$$$ ?

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

    No more than 500 interactive tasks are guaranteed in the Indian rounds))

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

    Spoiler

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

As a tester, I believe the problems are great. Do make sure to read all the problems and I hope this contest turns out to be a good one for you :)

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

As a very big fan of both fishy15 and ScarletS, I know this contest will be as geniosity as they are.

»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it
Things to notice ;)
»
7 months ago, # |
Rev. 2   Vote: I like it +136 Vote: I do not like it

The only way I got ScarletS to do work for the contest

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

There are so many codeforces rounds these days! Thanks to the problem setters and hope every good luck.

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

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

Why srk is in the tags :)

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

How can all problem setters be from different countries! Quite Amazing

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

As a tester, I should probably think of something interesting to say :v

But I have no brain so give contrib pls :v

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

As a tester, each upvote on this comment equals one time I will save saarang from ScarletS's roasts. So if you like saarang do upvote. And also yeah, since we were paid to appreciate the contest, please do participate! The problems are quite luv.

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

    As a tester, I now feel my work has not paid off accurately in terms of contribution.

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

As a tester, please participate in this contest and give me contribution.

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

As a tester, I'm here to claim my contribution.

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

lookcook ORZZZZZZZZZZZZ

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

Not sure if I'm allowed to disclose this information, but hey, there will be at most 6 interactive problems in this round. Don't tell anyone though, keep this sacred knowledge as it is your competitive advantage!

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

    Just like the gender of your profile picture, I guess no-one knows for sure :P

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

      But the gender shouldn't matter right? I thought all genders were equal.

»
7 months ago, # |
Rev. 5   Vote: I like it +10 Vote: I do not like it

.

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

As a tester, hope you have a decent day.

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

There will be at least $$$-494$$$ non-interactive problems, as long as I did all the math correctly.

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

May the force be with us and that we solve all problems)

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

This round's editorial will probably be published earlier than #765

»
7 months ago, # |
  Vote: I like it -23 Vote: I do not like it

"There will be at most five hundred interactive problems in the round" why????????

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

Really excited for this one.

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

Is every problem in this contest interactive ?

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

As the official video editorialist for most of the problems, the problems are very interesting and I will try my best to explain the solutions in an intuitive and simple manner. The videos will be available on my YouTube channel after the contest ends. Don't forget to like the videos and subscribe to the channel if you find them useful.

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

Thank you for preparing this wonderful contest!

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

Wishing good luck to everyone :)

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

is there any penalty for wrong submission

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

    Ofc there will be as always -50 points for any wrong submission till accepted

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

      Siiuuuuuuu!

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

      Is 50 points deducted from overall score we got so far, before submitting the current problem or it is deducted from the scores assigned to the current problem we are trying to submit.

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

        It is deducted from current problem you are trying to submit and if you manage to get that problem accepted during the contest it will also reflect in your overall score as well

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

what does five hundred interactive problem means?

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

Good luck every body

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

"omg hi codeforces"

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

Score Distribution ?

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

I have done with bit manipulation . But I can't solve the questions related to it. Even easy questions. Even after practicing all A ans B questions. What should I do?

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

    Practice it by tag in codeforces.... After practice 50-60 questions (increase rating of questions as you feel confident in a particular rating let 1200 then increase it to 1300). You will be able to solve in contest too...

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

Hi

Can anyone suggest me something to reach expert

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

    Stop thinking about reaching expert :)

    Instead focus on solving problems harder than your current rating and solving problems of your current rating fast.

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

score distribution is interesting ...

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

There will be at most five hundred interactive problems in the round, which means all problems might be interactive. That's interesting!

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

I guess, the problem B is harder than usual ... may be , it is interactive ...

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

Hope people like me who gained negative rating changes in the last round can win back.

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

Wish everyone good luck and high rating!

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

saarang is a very good problemsetter. For the past 13 years, he trained under the master(not on codeforces) GoldFish(me) on how to write problems. It's showtime saarang, you can do it

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

I wish you all to get repeated TLE's and passed pretest but gets failed in system testing may your code gets skipped and you get a minimum of -100. all the worst X). Looks like mu curse worked now go and work hard the rating will go down or up cause of no not by my words.

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

Wow, the round has official video editorials. I appreciate the effort from authors and testers.

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

Best of luck guys ✌️ See you after the contest.

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

How to become a tester?

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

    This has been asked and answered too many times

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

Why is codeforces not working on wifi but working on mobile data . Was not able to participate in this contest due to this reason .

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

Are contests rated if you don't submit any problem after registering. I couldn't submit anything because of network issues so I'm wondering if I should participate at all.

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

    No if you don't submit any solutions you don't loose ratings or count as participant

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

Absolutely love the problem statement of E, it's from one of my favorite movies!

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

due to some complicated relationship history that we couldn't fit into the statement!

this. thankyou for not writing unnecessary statements which nobody cares about

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

This round was good one

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

If i get fst in Problem D, I will die.

»
7 months ago, # |
  Vote: I like it -16 Vote: I do not like it

BFSForces :D

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

too easy C, D but hard B.

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

    Bruh...what the hell wwas B ???....I was tired of it

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

      Same. was tired of it but at last noticed the trick. Just find the distance of the furthest cell for every cell and sort it

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

        wtf !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! I am worthless...

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

        oh it's faster than bfs, wish i knew it sooner

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

        After a point I just didn't cared about WA and facepalmed the hand out of my face after figuring out that corners are the place she will always prefer :'(

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

          The way you said that sounds creepy...lol

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

E is a literal bruteforce right? Just need to calculate for layers ascending for each value in that layer/floor? I got TLE 8 and suspect it's just because I didn't map the coordinates in graph to some integer value, but rather stuck with maps :P

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

    Your solution looks mostly correct on first glance, but you can solve this problem without needing maps and implementation is fairly clean.

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

    What did you change to prevent getting TLE in test 8? My submission looks $$$nlog(n)$$$. Not sure why I am getting TLE in test 8.

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

      I removed repeating values, actually it was Len who did it. Just compare my last contest submission and last submission.

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

        Wow, this trick works magically. But why, even if I don't do it, it still should be order nlog(n).

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

          Suppose all ladders share an end point $$$v$$$. If you don't exclude the repeating values, you end up traversing edges of $$$v$$$ $$$k$$$ times. So the total runtime ends up being $$$k^2$$$ instead.

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

please any hint to solve D

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

I truly crave the day in which I will see actually interesting div2 starter problems which are not based solely on one basic observation and a lot of cringy implementation. This day will obviously never come, because the current trend for coordinators is, apparently, to review problems the harder they are. Whatever, at least D and E had some really cute ideas.

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

    It's funny how you say that because I found D and E quite boring. However, it does not mean that they are bad problems, I just saw similar ideas before. I think that you will continue finding A-C boring, much like I find A-E boring, because they are not in your interesting interval (c) Um_nik

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

Problem D: Link

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

I can't be the only one who misread problem A as to color the row and column and not the cell intially.

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

    https://imgur.com/a/KyW9gkN

    Literally spent 7-8 mins after that Yes answer to my question , thinking i need to colour both row & column, only to figure out.. that i was correct all along. I still don't understand how it can be cell(s) [Yes.] then. :(

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

      I think this is a very poorly formulated question, hence the misunderstanding. Like, I don't understand your English at all, and setters were probably confused as well.

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

How to solve E? I feel like it is some sort of convex hull stuff and I'd be kind of sad if it was something much simpler...

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

    If I'm correct (TLE test 8), there are at most 2K+M vertices you need to store the value for in order to solve the problem. Simply go layer by layer (from bottom to the top) and calculate the minimum path for every vertex present in the current layer (it is either reachable by using ladders or from some of the reachable 'neighbors'). So it's just a simple DP on each layer with the complexity of O(2K+M) but there's an extra log factor needed to compress the vertices (integer pairs) into some integer form.

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

      Won't it make the solution O(n*(k+m))? If so, both n and k,m can go upto 10^5, and would cause TLE.

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

        No, because you just consider rooms that belong to some ladder and the first floor completely. There are at most 2*K ladder vertices and M floor ones, so it ends up being just (2*K+M).

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

          Why do we need all floor vertices?? 2*k ladder vertices and (1,1) should work??

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

            Yes floor vertices are unnecessary, my implementation for this uses the 2k ladder endpoints, (1, 1), and (n, m).

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

            Because some ladders may start from vertices on floor other than (1,1). I guess your implementation may be different if it doesn't rely on this fact.

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

      Hmmm it's true that there are O(k) nodes (or something like that), but is it really that simple as visiting each node's neighbours? I thought of this case, where algorithms similar to yours would have at least O(k^2) complexity: here. Each green line is a ladder and there would be O(k) ladders with a[i] equal to some level l and another O(k) ladders with c[i] equal to some l.

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

      I think your solutions gets TLE because there might be multiple ladders starting from same point, and your code considers everything multiple times resulting in O(k^2) complexity (Only leaving unique will fix this).

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

        I traverse each vertex three times per layer, so I don't think it's the issue, I've posted the code above so you can check it.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          for(int j:v[i]){
          	if(!dist.count({i,j}))continue;
          		for(auto k:g[{i,j}]){
          

          I meant these lines, for example if all ladders will start from (1, n) and go to (n, 1), (n, 2), ..., (n, n), these for loops will work in n^2 (Or maybe I didn't understand it fully).

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

            I traverse every ladder exactly once, so I don't know why that should be an issue. And it's not some sort of recursive function, so I still see no problem with it.

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

                Thanks so much, I guess I didn't understand your initial comment. It's a dumb mistake on my end though :(

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

    let's say you calculated all the minimum values at which you can end up in some points after climbind some stairs until level X (i.e. you calculated $$$minhit$$$ for every cell $$$c[i] <= X$$$), and now you want to calculate where these values can go from this level upwards (using some ladders on level $$$X$$$). Then, we can observe that if we were to plot $$$min(abs(i — d[i]) * x[i] + minhit[i]$$$, for every $$$i$$$ with $$$c[i] = K$$$), then every $$$i$$$ (with $$$c[i] = X$$$) is assigned EXACTLY one segment on the number line (where it is a maximum value).

    After sorting each of these points by $$$d[i]$$$, we can do some stack like thinking to determine which values will actually be visible (and we by doing so the points will then be conveniently sorted again by $$$d[i]$$$). Then, we could check for each stair that begins on that level what is the cell from which it derives it's minimum (with two pointer logic).

    Time complexity: O(KlogK + N) (more or less)

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

Great Contest. Balanced. Loved problem D. Thankyou!

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

code

my approach for C:

  1. if any node has degree more than 2-> -1
  2. start dfs from leaf node and assigning edge alternate 2 and 3 as weight is this approach correct?

please point out what I did wrong

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

    you are specially for checking size ==3,check for size >2

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

      I am checking whether degree of any node becomes 3 while taking input itself ,so it should not be a problem right. Even if in the end degree of node is >3 flag would have become false

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    if(!flag){
        cout<<-1<<endl;
        return;
    }
    ...
    for(int i=0; i<=n+1; i++){
        adj[i].clear();
        vis[i]=false;
    }
    mp.clear();
    edge.clear();
    

    You not clearing graph if flag become false, so next testcase become incorrect

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

      Thanks man... I kept staring for 1.5 hours but was not able to figure that out

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

Can anyone explain logic behind problem C? my idea was if there exist any node connected with more than 2 edges then answer is -1 otherwise we can use 2 and 5 to assign weights in appropriate manner. i am getting WA on pretest 2. Can anyone help??

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

    This is a correct logic as far as I understand it.

    If tree is a line then you simply assign 2, 5, 2, 5 ...

    If it's not a line it's impossible.

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

      oh thanks! i think there must be something to do with my implementation, let me revisit it.

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

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

    Seems like problem setters of this round are die hard fans of srk.

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

first to be the first AC in D :) cool : L

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

    How can you D that quickly, and then fail on B? (No offence, but for nearly all of us B<<< D)

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

    Can you please explain your approach pls ?

    Ok Ok i got that...amazing approach.

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

Multisource bfs in B ?

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

    Not needed.

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

    We can simply calculate maximum distance for every vertex ...and then store it in a multiset..

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

      Oh stupid me! My intention was to calculate the same. Only if I spoke "calculate maximum distance for every vertex" to myself in simple english, I would avoid have saved my 10-12 minutes

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

        oof that's such a cool idea. I'm so annoyed for writing BFS xD

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

    i used bfs in my solution , i couldn't think of any greedy idea during the contest

    here it is 142893044

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

Interesting and balanced problems. Very nice round!

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

WoW, I fucked myself in this contest.

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

    Same here, though the problems were noice, especially B with the manhattan distance observation

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

I was tricked into submitting late by mean testcases in D and E, bad experience.

First I was annoyed by lengthy problem statements, then by myself because not commited but solved A to E anyway, then submitted and beeing annoyed because D and E where wrong.

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

Not Bad

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

Cool contest. How to solve E? I thought about Dijkstra's, but that seems too slow. I'm not sure if plain DP with memoization would work (and only visiting states in which we have an in-ladder or out-ladder)?

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

    Yep, only visit the "important" rooms in the building + dp works. Dijkstra is more annoying to do because of the negative weight edges but it can be done if you do it right.

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

.

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

My stupid ass thought for a whole 15 min that 1 is a prime number and was trying to figure out why assigning 1 to each edge in C would not work....FML

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

Notforces!

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

What's wrong with my submission 142866521 ? I see similar logic in others submissions, there must be an implementation problem somewhere, but i cant find it.

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

    The start of your BFS function always starts at a weight of 3, so if vertex 1 is not a leaf, then both of its adjacent edges will have a weight of 3 and thus the path containing both those edges will have weight 6. You can fix this by either starting each edge with different weights or finding a leaf and BFSing from there

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

      Oh, yeah, I got it. Thank you very much! :)

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

nice problem B, so lucky i have been practicing BFS recently :))

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

wow very fast editorial! nice

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

anyone else got mle in question 3 in system test?

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

Problem D is equal to this leetcode1819.(The problem is in Chinese)

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

Stupid Question, Ignore. :facepalm:

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

    dijkstra doesn't work for negative edges and is intended to TLE.

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

    Hello fellow same-surname, testcase 4 was an anti-Dijkstra testcase (regular Dijkstra doesn't work with negative edges).

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

      Thanks for your reply. Can you elaborate what the test case was. I do understand Djikstra won't work with negative edges but still find it hard to visualise in this instance.

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

        Here is a simple sketch I made of 1 layer of the counterexample.

        diagram of countercase

        Specifically, what is happening here is that we will processes the lower left corner with a distance of 0. After this, the next shortest is the upper left corner with a distance of -2, and then the upper right corner with a distance of 1. Finally, the lower right corner will be processed with a distance of $$$x$$$.

        There are 2 possibilities for implementations of Dijkstra that happen now. In the first one, a node is processed only if it is not marked as visited in some array. In this case, the upper right corner will have a distance of 1 marked even though the correct distance is 0.

        In another implementation of Dijkstra, a node is processed when it is at the top of the priority queue and the distance in the queue matches the distance stored in some array. In this case, the node would be processed once at a distance of 1 and then again at a distance of 0. If we make $$$x$$$ large enough and chain multiple of these layers together, then each layer will have to be processed multiple times which leads to an exponential solution.

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

      Nvm

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

Is there an actual right solution for E using graphs? I passed pretests with Bellman-Ford(Dijkstra doesn't work well with negative edge weights), but I got FST(here's my solution: Goodbye Candidate Master)

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

    Dijkstra's algorithm works if you construct a DAG and process the states in the order of (row, cost); because the cost in the same row only increases (142887300). Though if you have a DAG, it's easier (and faster) to find the longest path in a DAG using DP (142881726).

    To construct a DAG, create two nodes for each cell; the first one can go up or to the left, and the second one can go up or to the right.

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

What are the odds that you rewatch a Bollywood classic in the evening and open a problem statement and see that is about a scene that you were watching literally minutes ago. Good choice of story :)

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

    I wasted around ~5 mins remembering the last scene when SRK jumps after reading that line.

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

after how much time our rating will be changed?

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

As a contestant, I want to clear my contribution

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

Can someone please point out, why I am getting TLE on test 8 in problem E? I am going layer by layer and using prefix and suffix max to get the answer of a layer. According to me, this is not more than roughly $$$O(nlog(n))$$$. link to 142887592 .

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

    There are repeated rooms on floors, so you might be using multiple ladders from the same room at a floor, multiple number of times. I had the same error. Remove Duplicates from your vectors before taking pref_max suf_max.

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

Fun round! But for 1627F - Not Splitting, how did that "subarray" vs "subsequence" mix-up manage to get through all that testing and coordination?

I know the statement gave a definition of "subarray" (which matches the conventional definition of "subsequence", not "subarray"), so technically the statement was correct, but those definitions should be skippable by experienced contestants. Problems shouldn't re-define common terms.

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

    Sorry, the statement said "subsequence" during testing and coordination but during the translation (which happened a few hours before the contest), a translator decided to update the English statement to say subarray instead of subsequence and we didn't notice. Hopefully this didn't affect anyone's performance too much (and hopefully you could also tell what we meant by the image and the first sample).

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

      Ah, I see. I was solving the subarray version until I saw the clarification! But it still had a few observations in common.

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

      Maybe it should be a policy that all changes to statements notify authors with a diff (or maybe even require authors' approval to be accepted).

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

Very nice contest, but I feel like B and D should have been swapped.

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

Thank you very much for this nice roud :))

Here are my thoughts:

A
B
C
D
E
F

But to be fair, the round was really good and I enjoyed it a lot! I hope to see more of your rounds in the future :D

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

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

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

    When I checked your profile and saw : Headquarters — Rating 1772, I thought you were using magic to become headquarters ...

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

I think my D is hackable.

For each X, I am not considering the gcd of all the multiples of X. Instead, I am just considering the gcd of the smallest multiple of X with all other multiples of X and checking if there is any instance where gcd == X.

Do I loose my rating if somebody hacks my solution now? xD

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

    You are iterating backwards and marking the elements as present while you move, so it's still correct as the newly added elements are being considered in the further steps. We can prove that taking smallest multiple as the first element always works.

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

      This gives me a sigh of relief. I was also wondering if the way I have implemented is actually making it work. Lemme try to prove it formally. Thanks for reassuring.

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

I thought the round is good(Even if I just solved 3 problems during contest), but D and E is very fun.

Thank you for giving us a perfect contest. Looking forward to your future contests.

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

Problem C is easier than B lmao.

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

E had me like "Helikopter Helikopter".

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

can anyone help me please?

Why am i getting exit code 1?

https://codeforces.cc/contest/1627/submission/149194354