can you please tell how much time do they take to update the rating? **__**

No need. We assume three conditions a,b,c.

When you get a number, just return (a+b+c)==1.

I ran digit DP three times to count the number of positive integers satisfying the 1st, 2nd, and 3rd conditions respectively.

Me too!

Hello! Apparently you need to solve it with a 6D prefix sum, so quite implementation heavy IMO.

Try with a deque , i solved it with deque.

you can try using two pointers.

It's actually extremely simple once you get the pattern. You don't need a prefix sum for it.

First of all notice that you shouldn't be checking the string from 'left to right' but actually from 'right to left.' That's because inversions at the beginning doesn't give any hint to the final positions of the number at those positions, since you don't know how many times you'll be inverting later on.

But if you start from the last characters of the string 'right to left', if there's an inversion you can immediately tell that N (last number) should be placed at the beginning of the number array. That's because number N is unaffected by any of the inversions before it and is only inverted by the last character. This is recursively true for number N — 1.

So you read the string from 'right to left' and interchange between right side and left side of the number array as you place the numbers from N to 1, and you'll get the answer in O(N) time.

You can check my solution here (it's very short and I didn't use anything complicated): https://atcoder.jp/contests/abc465/submissions/77213807

look at the alternating sum from the end like :

// i goes to k + 1 - i if we reverse prefix of length k (all 1-based)
// k are the points where s[k] == 'o'
// for index i all k's to its right affect it
// so just keep doing : [k3 + 1 - {k2 + 1 - (k1 + 1 - i)}], see the brackets .. [{()}]
// or, (k3+1) - (k2+1) + (k1+1) - i
// alt_sum = (k3+1) - (k2+1) + (k1+1) ... 

int alt_sum = 0, sign = 1;
for(int i = n; i >= 1; --i){
    if(s[i] == 'o'){
        alt_sum += sign * (i + 1);
        sign *= -1;
    }
    ans[alt_sum + sign * i] = i;
}

i have implemented using 2 pointers in the below way.

# Code:
n = int(input())
s = input()

res = [0]*n

l , r = 0 , n-1

cnt = 0
for i in range(n-1,-1,-1):
    cnt += (s[i] == 'o')
    if cnt % 2 == 1:
        res[l] = i+1
        l += 1
    else:
        res[r] = i+1
        r -= 1

for r in res:
    print(r,end=" ")

Maybe you can use a deque ,and exchange its head and tail with the char .Finally think about how to output it

I'm sorry about my bad English,if you can't understand ,just ask me:)

void solve(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int t=0,q=1;
	//t=0尾插 t=1头插
        //if t==0 push back the num, else push front the num
	deque<int > a;
	a.push_back(1);
	
	for(int i=1;i<n;i++){
		if(s[i]=='x'){
			if(!t)
			a.push_back(++q);
			else a.push_front(++q);
		}
		else{
			if(!t)
			a.push_back(++q);
			else a.push_front(++q);
			if(t)t=0;
			else t=1;
		}
	}
	if(t){
		int x=a.size();
		for(int i=x-1;i>=0;i--) cout<<a[i]<<" ";
	}
	else for(auto i:a) cout<<i<<" ";
}

Hey, the approach I took is, find the least common ancestor of X and Y. Bring down both values to 0 and check where they meet. special cases are when one number is itself included in other one.

My solution: https://atcoder.jp/contests/abc465/submissions/77223657

You need to observe that applying 1st operation after 2nd operation to $$$x$$$ will yield the same value $$$x$$$. So we have to apply 1st operation before 2nd one. Instead of applying 2nd operation to x, you can apply 1st operation to y. So LCA of operation 1 on x and y gives the answer.

start BFS from X and Y , on each step the next node is X/K and Y/K,

void solve() {
 ll x,y,k;cin>>x>>y>>k;
 using pll=pair<ll,ll>;
 priority_queue<pll,vector<pll>,greater<pll>>pq;
 pq.push({0ll,x});
 pq.push({0ll,y});
 map<ll,ll>mp;
 ll ans=-1;
 while(!pq.empty()){
    auto [step,num]=pq.top();
    pq.pop();

    if(mp.count(num)){
        ans=mp[num]+step;
        mp[num]=step;
        break;
    }
    mp[num]=step;
   if(num!=0) pq.push({step+1,num/k});
 }
 cout<<ans<<endl;
}