yesnomaybe's blog

Google kickstart Round D problem 4 — Locked Doors
By yesnomaybe, history, 4 years ago, In English

Hi,

Can someone please explain the approach for the following problem :

Problem Link : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff08/0000000000386d5c

There's an editorial blog as well, but am not quite able to understand the solution. Editorial Link : https://mirror.codeforces.com/blog/entry/80040

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

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Haven't been able to find the solution. Can someone please help?

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

Have you tried reading the official editorial(aka analysis)?

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

    Hey!

    Am sorry, is there an official editorial as well? I couldn't find it anywhere. Can you please share the link to it?

    P.S. Nvm, found it. It's right there. I will check it out.

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

    Hi,

    I don't seem to get it. I guess there are solutions without using cartesian tree. I tried reading some codes and get the idea, but not able to understand the approach exactly. Can someone please help?

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

The approach is binary search + RMQ.

I'll just give some hints. Before going to the K-th room, you'll open the (K-1)the door.

If you start at room C, then before opening the door X (assuming it is on the right of C) you must open all the doors between C and X, and you also must open all the doors on the left of C with strength less than the max of all doors between C and X.

Use this along with RMQ to find the number of doors that must be opened before opening an arbitrary door X. Now use this to binary search the (K-1)th door.

I did this using a sparsetable and the solution complexity was $$$O(N log^2 N)$$$. You can see my code from the ranklist for reference.

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

Might help: https://mirror.codeforces.com/blog/entry/80040#comment-662229

→ Reply