Ryuma_7810's blog

By Ryuma_7810, history, 2 months ago,

Problem: https://mirror.codeforces.com/contest/1937/problem/B (Binary path)

int n;  cin>>n;
string s,t; cin>>s>>t;

int count=1;
string path= s[0] + t;
string min_str= path;

for(int i=1; i<n; i++)
{
path[i]= s[i];

if(path < min_str){
count=1;
min_str= path;
}
else if(path == min_str)
count++;

}

cout<<min_str<<endl;
cout<<count<<endl;


I have written this coder sample for the above problem, but it keeps on getting TLE on Test 4. I can't seem to understand it because the time complexity for this is O(n) and n<=2.10^5 Can you explain in which part of my code is there an issue ? I want to use this current approach.

• 0

By Ryuma_7810, history, 2 months ago,

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

• -9