GLAYS's blog

By GLAYS, 8 months ago, , Hello!

I'm trying to solve problem D.Greedy Game from the SPb SU and SPb AU Contest of Pertozavodsk Winter Training Camp 2016.

Here are the problem statements.

I already searched for any solutions on the internet, I only found this.

The problem with it is that it's in chinese, the translation isn't understandable and I couldn't understand the code.

So can you give me some hints?

What I found so far is that to find the maximal possible sum of values taken by the second player that he can guarantee regardless of the first player’s moves we just have to find the maximal possible sum of values that the second player can take if the first player, when confronted by many items of the same biggest value Ai, picks the one with the biggest Bi value first.

Since that would be the worst case for the second player.

Otherwise all of the approaches I've found are O(n2) ..

Any help is appreciated.

Thanks! By GLAYS, history, 14 months ago, , Here is the problem.

So basically you have an array of integers a[] of size n.

n <  = 1e5 and a[i] <  = 215 ( = 3, 2 * 104).

And you're given q <  = 5e4 queries of the form (x, l, r) for which the answer is the maximum value of x xor a[i] for l <  = i <  = r.

The editorial's solution is about persistent segment trees which I know nothing about.Before reading that I was trying to solve it using MO's algorithm + trie which has a complexity of O((n + q) * sqrt(n)) without counting the time to answer a query using the trie.Now q * sqrt(n) is fine but n * sqrt(n) is too much.Because n * sqrt(n) is caused by the movement of r to the right(which can reach n) I thought, is it possible to use the fact that all the numbers are <= 215 to improve the complexity?

If r moves to the right more than 215 times then at least one element is repeated right?

Is it possible to use this(or any other optimization) to get MO's algorithm to pass?

Here is my code.It passes 11 test cases out of 14 and the rest are getting TLE(actually it says segmentation fault but I think it's TLE).

Any other solution is welcome.

Thanks !

By GLAYS, 16 months ago, , Here is the problem statement.

First of all, I'm writing this because I didn't find the editorial for this round anywhere, or else I wouldn't have.

(I am counting on the fact that the expected average of ratings is the same as the expected sum of ratings divided by the number of ratings, so I'll be looking for the expected sum first.Correct me if I'm wrong.)

Here is my approach; there are two cases: (Let n = ceil(N/R)).

• N is divisible by R or Elly's rating is in the last N % R ratings.So for each time I take R ratings(n times), I add the sum of them multiplied by 1/R because there's 1/R probability that I'll have any of them in Elly's room, if I don't encounter Elly's rating. Else I just add Elly's rating.Then I just divide this sum by n and return the result.

• N isn't divisible by R and the last group of ratings we're going to take(N%R ratings) doesn't contain Elly's rating.There's p = (N % R)/R probability that we'll have n ratings in Elly's room, and q = 1-p probability that we'll only have n-1.So I calculate the expected averages in both cases and return avg1 * p + avg2 * q.

For avg1: there's 1/(N % R) probability that I'll take any rating in this last group.So I add their sum divided by N % R to the expected sum I already have(of the last N/R groups) and divide it by n. For avg2: I'm not going to add any other rating from this group so I just divide the sum I already have(from the previous groups) by n-1.

My solution fails on 3 of the 5 examples provided with the statement(+- 3 difference), specifically all the examples of the second case. Here is my code.

Can you help correct my reasoning or just propose another solution?

Thanks.

By GLAYS, history, 2 years ago, , Hello.

I'm stuck in this problem for a while now.(It reminded me with the "Berzerk" problem here)

To be honest; I never really understood this kind of problems nor did I ever understand why a solution is always possible(When the author says so).

When I think of it(or any similar problem) I always believe that it will go on forever..

Specially when the statement says; "If both the players play clever and cautious(or optimally)..

When I read the examples, an idea crossed my mind; the player will win if and only if he can get to the north-east,north-west,south-east,south-west cell of his opponent's.

However, I don't know whether that is the only possibility.

Please note that I don't need help with the first two subtasks which are: R=2 & C=2 and R <= 100 & C=1.

The real problem is with the other two subtasks: R,C <= 100 and R,C <= 1e9 ...

Any hints?

Thanks! 