RedSnowstorm's blog

By RedSnowstorm, history, 5 years ago, In English

So sorry if I'm not using this feature properly, I was struggling with a problem and thought this would be a good place to ask for help. So here's the problem:

There are N light bulbs. Initially, all of them are turned off. You are given M switches with which you can switch the light bulbs on and off. The i-th switch will switch all the light bulbs in the subsequence starting at A[i] and ending at B[i] (All the turned off light bulbs are switched on and all the switched on ones are turned off).

You are also given a number X. Your job is to end with the light bulbs from 1 to X on, and all the ones from X+1 to N off, using the minimum number of switches possible.

Output the minimum number of switches to achieve the goal. If it is not possible to achieve the goal, output -1.

The input file are the numbers N M X followed by M (the number of switches) lines in which the i th line is A[i] and B[i] (the parameters for the switches)

N<=100 000 M<=200 000 example: IN OUT 5 3 4 3 1 3 3 4 3 3

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

»
5 years ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

Let's define dist[i] as the minimum number of switch presses to have all the lamps from 1 to i ON and the others OFF.

If we have a switch (a[i] , b[i]) =>

  1. dist[a[i] — 1] = min(dist[a[i]-1] , dist[b[i]] + 1) because we can turn the lamps from a[i] to b[i] off

  2. dist[[b[i] ] = min(dist[b[i]] , dist[a[i]-1] + 1) , we can extend our interval by turning the lamps on

Since it would be too much trouble to compute dist[i] we can solve an equivalent problem : given a graph with edges (a[i]-1)->(b[i]) compute the distance from node 0 to node x. Transforming a recurrence relationship into a graph is actually quite a common problem.

If someone is interested in the problem : https://www.infoarena.ro/problema/pcb (this site is in romanian , I couldn't find the problem in english)

EDIT: I see that I got a lot of downvotes , I am not telling you not to downvote me , but if you really want to downvote please tell me what did I do wrong so as to improve my answers and also be able to help more people.