Balanced Round with good and Interesting problems !!

Can we use ternary search to solve F?

For E maybe the linear solution is find largest i such that prefix_sum[i-1]<v[i]. Then everyone from that index till last can win.

In D, isn't the worst-case time complexity of given solution O(n^2)? Then how will it not give TLE?

In Problem G Once we change x = x — full_spins*s

How we can be sure that new x will be less than max(pref) and we will be able to find it using lower_bound?

I overlooked the constraints in problem D and ended up with an efficient solution of nlogn. :)

Here are some video solutions to all of the problems, and a bit of hype around being 1st

Linear solution(after sorting) for E:

Sort players by tokens in ascending order. The player $$$i$$$ can win if $$$a_1+\dots + a_i\ge a_{i+1}$$$ and player $$$i+1$$$ can win(player $$$n$$$ can always win). So we can calculate the prefix sum and iterate from player with max tokens to player with min tokens and this gives us the linear solution.

code: 107566237

Recursion Solution for D was very elegant, I wasted a lot of time on coming up with an iterative Solution :(
My Iterative solution for anyone interested.

#include "bits/stdc++.h"
using namespace std ;
void solve(){		
	int n;cin>>n ;
	vector<int>a(n),right(n,-1),left(n,-1) ,idx(n),dp(n);
	for(int i=0;i<n;i++)
		cin >>a[i],--a[i],idx[a[i]]=i ;
	for(int i=n-2;~i;--i){
		int rt=n-1  ;
		auto upd=[&](vector<int>&A){
			A[rt]=(A[rt]==-1?i:A[rt] ) ;
			rt=A[rt] ; 
		}  ;
		while(rt^i){
			upd(idx[i]<idx[rt]?left:right); 
                        dp[i]++ ;
                }
	}
	for(int i=0;i<n;i++)
		cout<<dp[a[i]]<<" " ;
	cout<<'\n';
}
int main(){	
	int TC ;
	cin>>TC  ;
	while(TC--)
		solve() ;
}

Editorial has mentioned nlogn solution for problem F. but my O(nlogn) solution got TLE on test case 5 :( Link: https://codeforces.com/contest/1490/submission/107615964

Can problem G be solved if the drive only stopped when the sum was exactly $$$x$$$?

I misread the problem statement and while trying to solve it and I got some interesting observations (until I realized my mistake) but I'm not sure they make a solution that always works.

I noticed that for each query we need to get something like $$$k*sum + pref = x$$$, being $$$sum$$$ the sum of all the elements of the array, $$$pref$$$ any prefix of the array (even an empty one), $$$x$$$ the number in each query, and $$$k \geq 0$$$. So we can rewrite it as $$$k = \frac{x-pref}{sum}$$$ and since $$$k$$$ has to be an integer, then $$$x-pref$$$ has to be divisible by $$$sum$$$, i.e. $$$x-pref \equiv 0 \pmod{sum}$$$, so $$$x \equiv pref \pmod{sum}$$$. Knowing this, I can store and sort all the prefixes of the array by having them $$$\mathrm{mod}\ sum$$$, while also keeping the original numbers (for example, by storing the prefix sum in a separate array and the corresponding indices in the sorted array, with pairs of numbers, so then I know both the original value and the index to calculate the number of movements).

Then when answering queries, I only need to get $$$x \pmod{sum}$$$ and find it in the sorted prefix array I calculated before, with binary search, for example. If I can't find it, then it's impossible. Otherwise I can calculate the number of movements retrieving the original value of the prefix I found, and the answer would be I think $$$\lfloor{}\frac{x-pref}{sum}{}\rfloor{}n + prefInd$$$ being $$$prefInd$$$ the index of the chosen prefix. Note that I would have to be careful if $$$x \equiv 0 \pmod{sum}$$$, which in that case we don't sum any prefix index, and even subtract $$$1$$$ from the previous expression as we are looking for the amount of movements (we didn't do this before when having a prefix since if we have the array 0-indexed, we were already considering one movement more from the end back to the start of the array).

Something to note is that I may not have to store all the prefixes from the original array, as they can be both positive and negative. This means I can end up choosing a negative prefix while $$$sum$$$ was positive. To explain this better, let's look at how I'm supposedly getting $$$k$$$. I said $$$k = \frac{x-pref}{sum}$$$. $$$x$$$ is always a positive integer (given by the constraints of the problem), while both $$$sum$$$ and $$$pref$$$ can either be positive or negative. $$$k$$$ has to be non-negative (obviously, we can't make a negative amount of full turns with the drive), so we need to consider some cases:

• If $$$sum < 0$$$, then I would have to keep all $$$pref \geq x$$$ so that $$$k$$$ is not negative.
• If $$$sum > 0$$$, then I would keep all $$$pref \leq x$$$, because of the same reason.
• If $$$sum = 0$$$, then we would only reach our goal if some $$$pref = x$$$ exists, because after each full turn is practically a reset back to the start, and if there is no such $$$pref$$$, the drive will keep spinning indefinitely.

And I think by processing the queries offline from lower to greater $$$x$$$ (we can sort them beforehand), and also using some data structure like a set to add and erase the prefixes, sorted by $$$\mathrm{mod}\ sum$$$, while keeping up with the cases mentioned, it's possible to do it efficiently.

Please correct me if I'm wrong, as it's quite probable that I messed up when thinking of this and it's everything wrong. But I thought it was an interesting problem to think of, which derived from a silly mistake in my part.

Can Someone please explain how is the first optimization in F working, i.e. how are there there are no more than sqrt(n) unique values of C, thanks in advance.

P.S.: I tried to write sqrt(n) in the fashion shown on the Katex website, but didn't see the symbol in the preview, so if someone could help me with that too, it would be great. Thanks in Advance

For G, the number of spins should be ceil instead of floor?

For problem F, just curious, what is the binary search approach? Any explanation or code will be helpful..

In problem F, complexity of my code is O(nlogn) which is fine according to constraints but it is giving TLE in system testing can anyone please find out the problem. solution link

Can someone explain how to get the formula for the number of full spins in problem G.

.

.

Could anyone please help me as to why my submission gets a TLE for D? I have implemented the same idea during contest. I tried several times to debug but I couldn't :/ I can see that it's because there are 1e6 operations involved at max, there needs to be some optimisation to prevent TLE. But I don't know what exactly to do. My submission: 107614061

1490D - Permutation Transformation can be solve in $$$O(n)$$$ time and space complexity using Cartesian tree 107689365

Problem F — Equalize the Array

"you can consider only unique values of C (there are no more than O(n*√n)), and get a solution in O(n*√n)"

I used this approach mentioned in the editorial during the contest and get a TLE in test case 12.

Here is my submission:107609642

Will someone please attach this editorial to the contest itself? I think my color grants me the power to do so, but haven't tried and don't want to risk making a mess on a public round.

For problem 1490C — Sum of Cubes : In the Editorial's code there is precomputation of the cubes upto 10^9. It means this loop is going to iterate that 10^9 times , then it is supposed to give TLE. Since we are allowed to have only 10*8 operation per sec as per the standards of OJ. Please suggest if I am wrong.

There is a small bug in the editorial for 1490G - Old Floppy Drive . The formula

needs to be changed to

So that in the first member you have amount of full cycles multiplied by the total sum during the cycle.

for Problem G: for testcase

1

2 2

2 0

1 2

according to me ans should be:[-1 0]

but the query is giving: [0 0]

can someone help me understand where i am going wrong. here is my code:

I have a 'problem' with task F.

I use map to count number of occurences of a given number. When i use unordered_map<int,int> I get TLE on test 12( > 2sec). https://codeforces.com/contest/1490/submission/107876739

When I change to map<int,int> my solution takes < 200ms. This means, that unordered_map<int,int> in this case is at least 10 times slower. Why is it so? My previous experience (including performance tests) was, that for unordered_map is not slower than map, especially, if the number of elements is large (as probably in test case 12, where the sequence seems to be arithmetic). https://codeforces.com/contest/1490/submission/107876786

Test case 12: 1 200000 53201 106402 159603 212804 266005 319206 372407 425608 478809 532010 585211 638412 691613 744814 798015 851216 904417 957618 1010819 1064020 ...

Edit: I could have read previous comments before posting this, sorry. Problem solved.

Really liked this contest!

Problem G.

In the full spin calculating step, Why do we have to (x — max(pref[0..n])) before / sum?

Because the pointer could not reach the max(pref[0..n]) at the end, and we will substract more than necessary. The full spin could less than the answer.

Please help me, thank you.

In problem F(equalise the array) i am getting wrong answer at test case 20. I have tried a lot of test cases but i am not able to figure out the problem. Can someone please help me with this. This is my submission 109139946.

Your code here...
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long double lld;
#define FOR(i,l,u) for(lli i=l;i<=u;i++)

void solve()
{
    
lli t;cin>>t;
while(t--)
{
    lli n;cin>>n;
    lli A[n];
    FOR(i,0,n-1)
    {
        cin>>A[i];
    }
    unordered_map<lli,lli> count;
    FOR(i,0,n-1)
    {
        count[A[i]]++;
    }
    vector<lli> C;
    for(auto x: count)
    {
        C.push_back(x.second);
    }
    sort(C.begin(),C.end());
    lli greater_than_or_equal_to_count,mini = n,size=C.size() ;
    for(lli i=0;i<size;i++)
    {
        greater_than_or_equal_to_count = size-i;
        mini = min(mini,n-(greater_than_or_equal_to_count*C[i]));
    }
    cout<<mini<<"\n";
    
}
    
}
int main()
{
    solve();
}

Why am I getting TLE? Isn't it O(nlogn) algorithm?

Is it necessary to use unordered_set instead of set in problem C ??

We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!We Want Div4!!

wee my first ever comment on Codeforces , I don't know if someone will ever reply in the problem 1490F - Equalize the Array my 228090314 got a TLE but has the same logic with galen_colin except that he added ++m[(a[i] + 88) ^ 910591789]; , I did m[a[i]]++; when dealing with the map I don't understand why adding 88 XOR that big number and why does this fix the TLE problem , thank you guys