Блог пользователя spookywooky

Автор spookywooky, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    spookywooky Can You Explain it in simple words.I am also stuck at this problem but not able to get it.Problem Statement is not clear.

    Thanks in Advance!

    PS-Why this post is getting downvoted?I have done nothing wrong.If asking a doubt is an offense to community then why a discuss section was made on Codeforces.This discuss section is made for discussing doubts and problems.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Which part is unclear? The statement or the solution?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I am not getting the statement! i think the output should be 5 3 2 and not 5 3 3

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          The traffic lights are placed between the numbered segments of the street, after the given number.

          In the testcase above there are 3 lights, at positions between 2 and 3, between 3 and 4, and between 6 and 7.

          So the longest segment without a traffic light is {4,5,6} of size 3.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            After adding 6 wouldn't be answer 4 Because we have 3 segments which do not contain traffic lights :

            0 1   
            
            1 2
            
            2 3
            

            and size is 4. I am sorry if its a dumb question but i can request if you can clarify this! spookywooky ?

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Nah, the numbers are not the spaces between the segments, the numbers are the segments.

              There is a segment 1, a segemnt 2 etc... We place the lights between the segments.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                You mean to say

                0 1 is segment 1
                
                1 2 is segment 2
                
                2 3 is segment 3
                

                and so on... spookywooky?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  light only belongs to the left segment

                  light on 1 means 1-1 and 2-n

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Thanks for the hint man

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          Solution
          Code
          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится +1 Проголосовать: не нравится
              Solution
              Code
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Hey, your solution is giving TLE for some Cases.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              O(N) will give TLE, he was explaining the basic idea, check the comment below it.