The best part is that this roughly translates to Om Namah Shivay because Namah literally means to bow. Omkar orz!

Why so much reverence to Omkar? I mean I am just curious. You people aren't even Hindus(ig).

qlf9 Omkar orz

As a participant, I must say please tell me something new.

Nope! I don't even know C++

You can just replace omkar with god. This is maybe not for spreading any religion, but instead it creates a humour(here). Also the link is a part of that joke, pointing that its their third contest(its like they created a third part of a kids movie)

At first it baffled me. But later I recognized that it lightened my mood.

.

Omkar is one of the problemsetter's name.

qlf9

You should be personally familiar with some problem setter, so (s)he could personally kick the s**t out of you if you leak some problems beforehand, spoiling the contest and efforts of many people )

fwilgi lw4

You are an example of a stupid racist !!!!!!

Just take it as a normal contest

Yeah they should ask you to create a website :)))

but when did he disrespected other religion,omkar is name of one of the problem setter and I am sure he said it all in sarcastic way

Ok snowflake

He wouldn't say that he created the world and human race, right?

you muslims are weird

Yes, True that. Only I would like to add-

. "Om" is considered to be the cosmic sound. It originates back when nothing existed and space was empty & quiet, the creation of universe brought with itself the vibrations of Om. And hence it was the first sound that ever originated.

. Proper chanting of "OM" has remedial effects on any mental or physical stress because "om" is considered to be made up of every possible frequencies of sound and when chanted, it tunes with the frequencies of self and provides relief.

No, it doesn't. The problem score means only the gap between difficulties of the problems. In average it's close to the truth, but now always :)

No. It is the maximum score you can get upon solving the problem. Difficulty is assigned to a problem after the contest is over, on the basis of ratings of participants who were successfully able to solve it.

Wrong submissions have penalties. You should consider checking on more test cases before submitting.

nah, i consider this problem to be on div2 b/easy c level

the fact that problem statement is written so bad makes this problem even harder

It wasn't that hard especially if you look at the constraints, which made it quite easy to implement.

supahotfire CM perf orz

For me A was harder than B and C. Actually I am not sure if A works. I implemented some brute force for both, A and B, without being able to see if then will TLE or not.

Yeah, you missed a small observation. Let's build array a based on array b from the beginning. So for every operation, we can add at most 2 elements into a. So for the current move, if the previous median is not equal to the new median then there cannot be an element in the array we build (a) whose value is in between the new median and the old median. Because if you add two unknown elements into array [1,2,3,4,5,6,7] then the median can be one of 3,4 and 5.

Not sure how this is supposed to work dp[j] = max(dp[j], j / i);

The ratio is arr[0][i]/arr[1][i], but not the mathmatical result of the division, but the fraction. So we need to divide both values by gcd(), and then count foreach position how much of them exist left of that position.

I don't think so, none of the powers of 2 modulo 1e9 + 7 has value equal to 0.

It was easy. Just needed to notice then ratio of D/K remains same as the total. After that its just binary search.

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int N = 2e5+2;
const ll mod = 1e9+7;



void run_case(){
	int n,i;
	cin >> n;
	string s;
	cin >> s;
	int cntD=0,cntK=0;
	map<double,vector<int>> m;
	for(i=0;i<n;i++){
		if(s[i]=='D')
			++cntD;
		else
			++cntK;
		m[((1.0*cntD)/cntK)].pb(i);
	}	
	cntD=0,cntK=0;
	for(i=0;i<n;i++){
		if(s[i]=='D')
			++cntD;
		else
			++cntK;
		double need = ((1.0*cntD)/cntK);
		int cnt = lower_bound(all(m[need]),i)-m[need].begin();
		cout<<cnt+1<<" ";

	}
	cout<<"\n";
}

 
int main(){
	fast;
	int tt;
	cin >> tt;
	while(tt--){
		run_case();
	}
	
	
}

Its a pretty common idea that has appeared a lot (especially at the start of this year on Codechef) — having a map storing some property which becomes the same (or similar) for all valid ranges then checking for each right end. So I don't think its that surprising that a lot of people solved it.

C was easier than B. I think we have to just maintain the simplified ratio of D and K we got till now.

Like 1:2 is same as 2:4 and which is same as 4:8 so, just divide D and K by gcd for that. As ratio of one part of the string must of equal to the ratio of complete prefix.

But i feel B more harder than C. Although there was not much difference.

BTW problem similar to B was also on HackerEarth Link

I don't think that C was 3k easy. Something else is going on.

segment tree is very indian

I thought of following approach but could not implement, could someone tell if how to implement if their solution was similar :

Yes, that is more or less what I did. Compress coordinates. Use a binary indexed tree to keep track of values that are fixed. All values from the input need to be fixed, and if values are repeating, it is enough to fix each value once. Values that are not fixed are either minus or plus infinity, and we keep track of the counts. So, iterate over the input array. The first value goes to the Fenwick tree directly.After that, for each value, check how many values so far were strictly larger (including values from BIT and plus infinities), strictly smaller (including values from BIT and minus infinities) and equal to the new intended median. If the value of the median was not fixed before, fix it. The remaining values (1 or 2 depending on whether we had to fix a new value in this iteration) become minus or plus infinity, depending which category is less numerous. After the assignment, check if the supposed median is actually a median.

Even I tried to do the same but got WA on Pretest 2. :(

118652416

The key observation is, that if we remove a prefix of given ratio, the remaining part has same ratio.

So foreach position, we need to find the number of positions left of it with same ratio.

Create a map<pair<int,int>,int> where the key is the ratio, seen as a pair of ints instead of a double. Iterate through the string and keep two counters, current numbers of D (currD) and current numbers of K (currK), for every position in the string call x=gcd(currD,currK) and add one to map[{currD/x,currK/x}] and thats the answer for that position. You are counting how many segments are with the same ratio than your current position.

**if A/B = C/D = E/F then A/B = C/D = E/F = ... = (A+B+E+...)/(C+D+F...) ** Thus a prefix can be divided into Components if The count ratio of D and K in all the partitions is same as that of Prefix . How to Store Fraction in Their Simplest Form : simple form of x/y is X/Y = (x/G)/(y/G) where G=__gcd(x,y) . We Can use map to store the position of Last index where the ratio was {X,Y} if the ratio at any index is i {a,b} the ans[i] = 1 + ans[pos[{a,b}]]; pos is a map.

Move along the array from left to right and for each prefix, find the ratio of D/K (rounded down to simplest form). Maintain a map to count the number of occurrences of this ratio and then the answer for index i is simply mp[ratio] + 1. It is always better to store the ratio as a pair of numerator and denominator to avoid division by 0.

Suppose when iterating from left to right, at index $$$i$$$, we have $$$cnt_D$$$ occurances of $$$D$$$ and $$$cnt_k$$$ occurances of $$$K$$$.

Now let us note that for a given string, if all the components have the same ratio $$$x:y$$$, then the total string will also have the ratio $$$x:y$$$. So it is sufficient to check for only this ratio.

Now the answer is just many prefixes till index $$$i$$$ has a ratio $$$x:y$$$ occurred. This works as if for some $$$j \lt i$$$ $$$x_{j}:y_{j}$$$ and $$$x_{i}:y_{i}$$$ have the same ratio, then $$$x_{i}-x_{j}:y_{i}-y_{j}$$$ must have the same ratio. So we can just count this using a map of pairs $$$(x, y)$$$

However we must also take care of the fact that $$$x:y$$$ and $$$kx:ky$$$ are the same ratio. To do so we can just reduce the ratio to its lowest form by dividing both terms by $$$gcd(numerator, denominator)$$$.

Code: 118610628

I didn't submit since I was too late, but my solution got the samples correct.

UPD: Idea got AC post-contest

So, basically, you fix each hash to be 0 or non-zero. Now, which elements in matrix are zero and which are non-zero. Now, suppose you fix the hash at position (i,j) in the matrix to be non-zero, then the value of (i,j) will be the manhattan distance to the nearest zero. My proof is quite tedious but try proving it by contradiction.

No

No, it won't.

You submitted, but got 'Compilation error'. It will affect your rating. Just look at rainboy's contests.

Whenever you add the two new integers, you have three options.

1. Add them to the left of the previous median. This results in shifting the median one to left.
2. Add them to the right of the previous median. This results in shifting the median one to the right.
3. Add one on either side. Same as previous median.

Try to think of the situation where the answer would be "NO".

Which element is removed? All the required elements are present.

if the given array contains negative elements then the answer is NO, otherwise just print from 0 to 100, it will always contain the given array

if (neg) { std::cout << "NO\n"; }

Exactly, I also understood the problem to be this, and could not come up with why it is not passing for about 1 hour.. before realizing that the ratio are compared in simplest form.