Ryuma_7810's blog

How to solve this question ? Here n<=10^5 and k<=10^14
By Ryuma_7810, history, 2 months ago, In English

I have been unable to solve the question in this image. the most concerning part is k can be as large as 10^14 which doesn't give much options how to traverse and apply the logic. Please provide me a good approach to solve this

There are n participants numbered from 1 to n where the ith participant has potentioal denoted by potential[i]. The potential ofd each player is distinct. Initially, all players stand in a queue in order from the 1st to the nth player. In each game, the first 2 participants of the queue compete and the participant with a higher potentioal wins the game. After each game, the winner remains at the beginnning of the queue and plays with the next person of the queue and the losing player goes to the end of the queue. The game continues until a player wins k consecutive wins.

Given the potential of the participants and the deciding factor k, find the potential of the winning player. Example: n=4 and potential=[3,2,1,4] and j=2 the output= 3 (1st player)

1<=n<=10^5 (n= number of players) 2<=k<=10^14 1<=potential[i]<=n

  • Vote: I like it
  • -9
  • Vote: I do not like it

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

Auto comment: topic has been updated by Ryuma_7810 (previous revision, new revision, compare).

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think you just need to iterate once over the players making the simulation (without getting them back in queue if they lose) of what happens and if you satisfy k before traversing the whole participants you get your answer (Just keep the number of times the current player has won and if it equals k thats the winner), otherwise the winner will be the player with the highest potential. (I can't see the image)

If you have source I'd like to see it btw.

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

    sorry, I was unable to provide the image, but I have described the problem statement in my blog entry along with the constraints

    → Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

you just simulate the process if until a player wins k consecutive games if you reach a player with max potential then that will be ans as this player will never loose and always be at the front. can you provide the problem link?

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

    it was from an online assesment, so I don't have the problem link. But thanks for the suggestion

    → Reply