manish.17's blog

Codeforces Round #766 (Div. 2)
By manish.17, 3 years 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 Jan/15/2022 17:35 (Moscow time). 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. wk___tzc

  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

Comments Comments (178)
| Write comment?
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

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

      Good luck to everyone and I wish the experts become candidates

      → Reply
      • »
        »
        »
        »
        3 years 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. :(

        → Reply
        • »
          »
          »
          »
          »
          3 years 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.

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

As a tester, I was very useful!

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

looks like this one is skribbl bois round :catthink:

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

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

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

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

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

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

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

    Spoiler

    → Reply
»
3 years 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 :)

→ Reply
»
3 years 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.

→ Reply
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it
Things to notice ;)
→ Reply
»
3 years 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
→ Reply
»
3 years ago, # |
  Vote: I like it +99 Vote: I do not like it

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

Why srk is in the tags :)

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

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

→ Reply
»
3 years 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

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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.

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

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

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

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

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

lookcook ORZZZZZZZZZZZZ

→ Reply
»
3 years 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!

→ Reply
  • »
    »
    3 years 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

    → Reply
    • »
      »
      »
      3 years 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.

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

.

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

As a tester, hope you have a decent day.

→ Reply
»
3 years 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.

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

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

→ Reply
»
3 years 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????????

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

Really excited for this one.

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

fishy15 ORZ

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

Is every problem in this contest interactive ?

→ Reply
»
3 years 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.

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

Thank you for preparing this wonderful contest!

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

Wishing good luck to everyone :)

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

is there any penalty for wrong submission

→ Reply
  • »
    »
    3 years 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

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
      • »
        »
        »
        »
        3 years 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

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

"omg hi codeforces"

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

Score Distribution ?

→ Reply
»
3 years 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?

→ Reply
  • »
    »
    3 years 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...

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

Hi

Can anyone suggest me something to reach expert

→ Reply
  • »
    »
    3 years 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.

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

score distribution is interesting ...

→ Reply
»
3 years 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!

→ Reply
»
3 years 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.

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

Wish everyone good luck and high rating!

→ Reply
»
3 years 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.

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

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

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

How to become a tester?

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

    This has been asked and answered too many times

    → Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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

    → Reply
»
3 years 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!

→ Reply
»
3 years 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

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

This round was good one

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

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

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

too easy C, D but hard B.

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

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

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
      • »
        »
        »
        »
        3 years 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 :'(

        → Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

    → Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
      • »
        »
        »
        »
        3 years 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).

        → Reply
        • »
          »
          »
          »
          »
          3 years 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.

          → Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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

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

Problem D: Link

Code
→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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. :(

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
»
3 years 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...

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
      • »
        »
        »
        »
        3 years 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).

        → Reply
        • »
          »
          »
          »
          »
          3 years 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??

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years 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).

            → Reply
          • »
            »
            »
            »
            »
            »
            3 years 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.

            → Reply
    • »
      »
      »
      3 years 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.

      → Reply
    • »
      »
      »
      3 years 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).

      → Reply
      • »
        »
        »
        »
        3 years 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.

        → Reply
        • »
          »
          »
          »
          »
          3 years 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).

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years 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.

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

              fixed:)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years 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 :(

                → Reply
  • »
    »
    3 years 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).

    Drawing

    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)

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

Great Contest. Balanced. Loved problem D. Thankyou!

→ Reply
»
3 years 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

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

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

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
  • »
    »
    3 years 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

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
»
3 years 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??

→ Reply
  • »
    »
    3 years 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.

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

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

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

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

Multisource bfs in B ?

→ Reply
  • »
    »
    3 years 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..

    → Reply
    • »
      »
      »
      3 years 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

      → Reply
      • »
        »
        »
        »
        3 years 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

        → Reply
  • »
    »
    3 years 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

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

Interesting and balanced problems. Very nice round!

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

WoW, I fucked myself in this contest.

→ Reply
  • »
    »
    3 years 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

    → Reply
»
3 years 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.

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

Not Bad

→ Reply
»
3 years 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)?

→ Reply
  • »
    »
    3 years 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.

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

.

→ Reply
»
3 years 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

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

Notforces!

→ Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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

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

wow very fast editorial! nice

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

anyone else got mle in question 3 in system test?

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

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

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

Stupid Question, Ignore. :facepalm:

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

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

    → Reply
  • »
    »
    3 years 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).

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
      • »
        »
        »
        »
        3 years 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.

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

      Nvm

      → Reply
»
3 years 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)

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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 :)

→ Reply
  • »
    »
    3 years 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.

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

after how much time our rating will be changed?

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

As a contestant, I want to clear my contribution

→ Reply
»
3 years 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 .

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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.

→ Reply
  • »
    »
    3 years 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).

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
    • »
      »
      »
      3 years 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).

      → Reply
»
3 years 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.

→ Reply
»
3 years 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

→ Reply
»
3 years 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!

→ Reply
  • »
    »
    3 years 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 ...

    → Reply
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

    → Reply
    • »
      »
      »
      3 years 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.

      → Reply
»
3 years 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.

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

E had me like "Helikopter Helikopter".

→ Reply