spookywooky's blog

By spookywooky, history, 11 months ago, In English,

Hello,

I am trying to solve https://cses.fi/problemset/task/1163, but got some problem to understand it. It states that "There is a street of length x whose positions are numbered 0,1,…,n. " That should be "0, 1,..., x", not n, isn't it?

Then the example:

Input:
8 3
3 6 2

Output:
5 3 3

I think output should be 5, 3, 2, not 5, 3, 3. Since obviously the longest segment without a traffic light is 2, not 3.

0 1 2 3 4 5 6 7 8
    x x     x

Can somebody explain? A lot of people solved that problem, I think I am missing something. Thanks.

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

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

Found it by myself ;)

Two things one must notice:

There is an "implicit" traffic light after position 0. The length of the segment is calculated as without left bound, but including right bound.

So, the traffic lights are placed kind of "right of the positions". After adding the three lights, it looks like

0 1 2 3 4 5 6 7 8
 x   x x     x

The longest segment is the one "4,5,6", of length 3.

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

You are right, the task statement had a typo. This has now been fixed, thanks!

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

Can you please give me a hint on how to solve this problem? I am stuck in it.

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

    Hint: Think about the number of segments that could be affected after adding a new traffic light.

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

      Thanks for the hint man

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

        Hey, I am still not able to figure it out, can you share your approach?

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it
          Solution
          Code
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            Thank you :) Hey, If you know how to approach "Throwing dice"? https://cses.fi/problemset/task/1096

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

              it is an easy linear reccurence:
              $$$f(x) = \sum_{i=1}^{6} f(x-i)$$$ which can be solved by the matrix multiplication

            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it +1 Vote: I do not like it
              Solution
              Code
              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thank you very much! I did not know about the matrix multiplication part, it look's really cool.

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

                  it is written in his book, page 221