2ndSequence's blog

Can you give me a corner case?
By 2ndSequence, history, 4 years ago, In English

Greeting,

I tried to solve this problem a year ago and i couldn't understand what's wrong with my submission and when i tried to solve it again now i couldn't get that edge case by my self again.

Can anyone tell me what's wrong with trying every possible segment with length k?

And i really tried the last submission was from 2019.

or maybe i didn't understand the problem correctly?

My submission. Thanks for your time.

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

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

Hello,

I think the main problem with your submission is you are doing the greedy method and always assuming that making the first k elements the ones in the period is the correct method. However, there might exist better methods that require less changes.

I can't come up with a corner case on the spot, but this is how your solution is flawed.

Hope this helps.

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

    Thanks a lot for paying attention but i don't think so,

    i tried this

    6 2

    1 1 2 2 2 2

    and the output was 2 which should be correct?

    if i considered only the first k items the answer should be 4?

    i know my code is a bit confusing but i couldn't think of another way to do it but there is i — ptr and i may be wrong.

    But thank you!! :)

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

      Maybe it isn't what I thought, but based on what I saw in your program, that is what I deduced. Also looking that your submission it seems that your solution overshot (gave an answer bigger than the correct one) in test 22 and that is in line with my perception.

      Honestly, if you haven't been able to do a problem for so long, I would recommend that you read the editorial. It isn't helpful to be stuck on a problem for so long, as contests would not give you time to solve it.

      Hope this helps.

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

Your code will give the wrong answer on test case given below

9 3

2 2 1 2 1 2 1 2 2

as your code is checking for all the subarray of length k in the array itself but here in this test case to get the correct answer you need a check for one more array of length 3 i.e. 2 2 2 but this array is not the subarray of the above array in the given test case so you are missing checking this that why you are getting the wrong answer and whenever there is such type of test case your code will give wrong output. Hope this test case and explanation will help you.

→ Reply