Hello,

Suppose we have the permutation of size $$$N$$$ and the numbers in it are divided in two groups, one of size $$$a$$$ and one of size $$$b$$$ = $$$N-a$$$ (for simplicity, let's say the first $$$a$$$ numbers form the first group)

We also have an(empty) array of size $$$N$$$ also divided in two groups one of size $$$c$$$ and one of size $$$d$$$ = $$$N-c$$$ (also for simplicity, let's say the first $$$c$$$ cases form the first group)

If we were to divide the $$$N$$$ numbers(all permutations are equiprobable) in the empty array, I am looking for the expected number of numbers of group a that land in a position of group c.

Turns out this is $$$a*c/N$$$ (from the tutorial of Edu 57 F).

I tried to compute it in many ways and just ended up stuck with lots factorials, N choose Ks and the EV sum; sum of i * (probability that we get i numbers)

So I would very much appreciate any help regarding the intuition behind this and the ways of deriving such EV formulas.

Thank you :)

Hello

Here is the PDF statements page of the 2016 Benelux Algorithm Programming Contest (BAPC 16).

I reduced Problem H with some small observations to this problem:

Since I believe there isn't another(totally different) way to solve it and to keep this short, I won't explain how I got to that statement from Problem H.

Now this seems to me like a 100% greedy problem. But I ALWAYS get stuck in this same type of problems, I just can't find any way to distribute them. Maybe the small constraints on the number of primes should help?

The only algorithm I know in some similar cases to this is the Huffman Code and I don't think it can help here. (maybe some variant of it can?)

Can you help me solve this? Also it would be awesome if you would provide any help/links on some problems/tricks to help with such greedies!

Thank you :)

Hello,

I recently found out about Zachtronics.They are basically problem solving games!

You can find some gameplay here.

Those are not free(though they are cheap), and so I'm looking for any other game like them.

I found lots of types by googling; there are:

• ones that involve code(mostly javascript) to pass levels or defeat some kind of monsters
• those that are on the browser and just involve some mouse moving
• multiplayer ones; where you need to beat your opponent as fast as possible(mostly coding stuff too)
• downloadable ones where you have a character and move objects to solve levels

They all involve some kind of problem solving, and from what I read they are all fun!

So I'm looking for ones to play at the moment and I'm interested to find what you guys tried.

Thanks!

Hello!

When I need to stress-test a problem on trees, I usually find a random tree like this:

int n = random(1, 100);
for(int i = 2; i <= n; ++i){
    p = random(1,i - 1);
    addEdge(p, i), addEdge(i, p);
}

As in; to find a random tree of $$$N$$$ nodes, I just find a random sequence $$$P$$$(parents) of length $$$N-1$$$ with each $$$1<=Pi<=i-1$$$ for each $$$2<=i<=N$$$.

And it worked well, or so I believed at least.

But I remember watching an Errichto stream(I think it's the AtCoder DP contest one) where he showed how he stress tests and then said that the previous method only prints a specific kind of trees, and that he recommends using Prüfer Sequences. I kept thinking about why that's true but found no answer online.

Of course, Prüfer Sequences are clearly the best and most trusted choice since it's proved that any sequence represents a unique tree and that any tree can be represented by a sequence(more info here). And though it's not that complicated, I still don't want to keep writing it whenever I need to, unless there's an important difference between the two methods.

So if anyone would enlighten me on the difference if it exists, that would be great :D (It would be good if it's Errichto too xd)

Any other advices/tricks on stress-testing graphs or in general would be awesome!

Thankss ^^

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 A_i, picks the one with the biggest B_i value first.

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

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

Any help is appreciated.

Thanks!

Here is the problem.

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

n <  = 1e5 and a[i] <  = 2¹⁵ ( = 3, 2 * 10⁴).

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 <= 2¹⁵ to improve the complexity?

If r moves to the right more than 2¹⁵ 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 !

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.

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!