July 18- Problem Discussion

general
,
101

you can see fermets little theorem for mod-1 query

102

Problem: NSA

My Solution: https://www.codechef.com/viewsolution/19173471

This problem requires a strict time complexity for complete AC solution.
I have used 2 2D arrays(S and G) of size 26*(10^5) and 1 1D array(freq) of size 26.

In the arrray S,I traversed the string from the start and stored the frequency of all the characters which have come before the ith character into the ith column of the array.

In the arrray G,I traversed the string from the last and stored the frequency of all the characters which have come after the ith character into the ith column of the array.

Both of these operations has complexity of order 26*(length of string).

For calculation of Y in initial configuration of string I have summed up all the freq stored in the array G for ith column and jth row such that j>s[i]. (This is equal to number of pairs <si,sj> such that si<sj and i<j).

Now coming to modification part, I have checked all 26 combinations for every character in the string and calculated the difference which a particular change makes.
If the new Y + X is less than min value, the min value is updated.
Complexity for this is order of 26 * 26 * (length of string).

Finally,the min value gives the solution.

1 Like
103

I have one question here how come one reaches to the conclusion that they have to use this way to proceed for the answer. I mean what’s the intution behind the solution?

104

See it is a multi-step process. When you start solving a problem, generally you can’t think of the best way in just one look. First you think of a simple way which can solve the problem mostly that is Brute Force and then as per the constraints you modify your approach. Some times it is possible and some times it isn’t and you have to think of another approach.

In this ques- For the first try I used 2D arrays of n * n and also my complexity was of order n^2 and thus it didn’t give complete AC soln.

105

This is the beauty of Competitive Programming, many a times the answer is simple but to reach the answer within the constraints is what requires thinking.

106

@ritam777 : Actually that isn’t an assumption

The observation in step 2 is that only one of the vector can have side
greater than k/2

Let’s call p(i) as probability of loosing if we give ith vector a magnitude
greater than k/2

All I am saying is due to symmetry, p(1) = p(2) = … = p(n)

Thus we can compute p(1) (which I have done above) and the probability of winning will thus be [ 1 - n * p(1) ]

1 Like
107

Can you please explain your function-

bool bad(int a,int b,int c) {
  // use deterministic comuputation with long long if sufficient
  return (long double)(B[c]-B[a])*(M[a]-M[b])<(long double)(B[b]-B[a])*(M[a]-M[c]);
}
1 Like