Hope to become pupil in this round

You have no need to wait . Just use magic to become specialist before this round .

BUT HOW YOU CAN AS YOU ARE A LEGENDARY GRANDMASTER BY THE WAY HOW YOU CHANGED YOUR POST FROM PUPIL TO LEGENDARY GRANDMASTER.

congrats on becoming LGM

No

wtf?

yeah lol what?

in problem, c is it necessary to reorder all the k elements or he can choose not to place some of the elements again.

1) Problems with test cases

2) Awful pretests

3) Long queue

Choose one.

I really did that, cooked dinner after solving D.

Looks like minimum cost max flow with binary search but is it normal to have these in Div 2 contest?

Edit: Reading above seems like I was trolling. But actually I had sketched something of that sort. Haha. Anyway, people have solved with a simple dp with binary search.

Well, it uses the trick from Aliens (from IOI 2016). You can read about it here

http://mirror.codeforces.com/profile/pisquare

chill bro :>>

i had the same doubt

Due to the process with which the decision is made, not all of those are equally likely. The first two happen with probability $$$\frac{1}{4}$$$, the last four with probability $$$\frac{1}{8}$$$ each.

1 1 1 and 1 1 2 and 1 2 1 and 1 2 2 have all 1/8 chance

2 1 1 and 2 1 2 have all 1/4 chance

X, Z all chosen independently but Y is not (depends on X)

P(X = 1) = P(X = 2) = 1 / 2

So P(X = 1 and Y = 1) = 1 / 2, P(X = 2 and Y = 1) = 1 / 2

Same doubt. Anyone can explain why 7/8?

Either you pick item 1 or item 2. Probability of picking item 1 is 1/2*1 (you pick student 2 ) + 1/2*1/2 (or you pick student one in the first step). Therefore probability of picking item 1 is 3/4. Probability of picking item 2 is therefore 1/4 (sigma has to be 1). Now if you pick item 1, probability of making a valid decision is 1, but if you pick item 2, probability of making valid decision is 1/2. Therefore P(pick item 1)*P(valid | item 1) + P(pick item 2)*P(valid | item 2) = 3/4 + 1/8 = 7/8

Because not all of them are equally probable. (1 1 1) has 1/2*1*1/2 chance of being chosen while (2 2 2) has 1/2*1/2*1/2.

That's not true Answer is 7/8

Model of calculations:

1) possibility to choose a person = 1 / n 2) possibility to choose a gift from a list = 1 / size_of_list; 3) possibility to choose a person who would like this gift = number of good kids / n; Lets sum everything i = 1, j = 1, 1/2 * 1/2 * 1/2 = 1/8 i = 1, j = 2, 1/2 * 1/2 * 1 = 1/4 i = 2, j = 1, 1/2 * 1 * 1 = 1/2 ans = 1/2 + 1/4 + 1/8 = 7/8

This is because all tuples are not equiprobable. Let you have 10 balls then probability of selecting each ball is 1/10. Now divide the ball into two groups of 8 and 2. Now first select a group then select a ball. Then half of the probability will be distributed among 1st group and half will be distributed among second group. If a ball is in group containing 8 then probability of selection 1/16 and for other group it's 1/4. This is how 5/6 become 7/8 here.

I think it can be solved using the observation that any good permutation is a one where $$$p_1=i$$$, and values of $$$p_j$$$ ($$$1\leq j\leq i$$$) are $$$\leq i$$$, $$$p_{i+1}=k$$$, and values of $$$p_m$$$ ($$$i+1\leq m\leq k$$$) are $$$\leq k$$$, and so on. Then we can use some greedy and dp to find the required permutation.

I finish impl just now.. find kth-lexi painful..

note good form is |i... | j...| k...|..., each region is cycle. with max be first.

first define f[n], total-derangement, i.e. p[i]!=i, but they're exactly one cycle.

r.relation $$$f[n] = (n-1)f[n-1] = (n-1)!$$$. which is circle-perm.

define dp[n][j], ways of good-perm. s.t. first j elements in a cycle with j is first. i.e. j,..., where ... part is f[j-1].

define g[n]: ways of good-perm of [n], i.e. $$$g[n]=\sum_{j=1}^n dp[n][j]$$$.

r.relation $$$dp[n][j] = f[j-1] * g[n-j]$$$.

for kth-lexi. first iter j, find satisfied dp[n][j]. then problem separate to j part, n-j part. where n-j part is original problem.

for j part, first of all, let $$$p[1]=j$$$, then for remain position, pick smallest x, don't violate total-derangement, and just satisfied lexi.

Magic changes the color, not the rating which predictor uses.

its working fine

You are trying to maintain the probability value of each event as fraction. Then you are adding all those values to compute final answer, overflowing can easily happen when you multiply numerators of fractions to bring them in common denominator form. (While adding fractions)

Instead of doing so, immediately convert the fraction into "numerator.(denominator)^-1" (inverse modulo of denominator) form.

and now the add the fractions in their "converted form", using appropriate modular arithmetic.

Seems F is easier than E...

1 1 1 and 1 1 2 and 1 2 1 and 1 2 2 have all 1/8 chance

2 1 1 and 2 1 2 have all 1/4 chance

X, Z all chosen independently but Y is not (depends on X)

P(X = 1) = P(X = 2) = 1 / 2

So P(X = 1 and Y = 1) = 1 / 2, P(X = 2 and Y = 1) = 1 / 2

Look, the probability that we choose the three $$$(2, 1, 2)$$$ is not equal to the probability that we choose the three $$$(1, 1, 2)$$$.

How the answer is counted:

• the probability that we choose $$$(1, 1, 1)$$$ is $$$\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$$$ , and this is correct;
• the probability that we choose $$$(1, 1, 2)$$$ is $$$\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$$$ , and this is correct;
• the probability that we choose $$$(1, 2, 1)$$$ is $$$\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$$$ , and this is correct;
• the probability that we choose $$$(1, 2, 2)$$$ is $$$\frac{1}{2} \cdot \frac{1}{2} \cdot \frac{1}{2} = \frac{1}{8}$$$ , and this is not correct;
• the probability that we choose $$$(2, 1, 1)$$$ is $$$\frac{1}{2} \cdot \frac{1}{1} \cdot \frac{1}{2} = \frac{1}{4}$$$ , and this is correct;
• the probability that we choose $$$(2, 1, 2)$$$ is $$$\frac{1}{2} \cdot \frac{1}{1} \cdot \frac{1}{2} = \frac{1}{4}$$$ , and this is correct;

We just summarize all the correct options and get the answer. It is equal to $$$\frac{7}{8}$$$.

I definitely agree with that

Well, it seems that it's my fault. I greatly overestimated the difficulty of D — it is very simple in coding, but I expected that a lot of people would make wrong assumptions such that all outcomes are equiprobable, so the concept of probability would make this problem much more difficult than simply coding it. It turns out that I was wrong.

As others have mentioned, the solution relies on a technique known as Aliens' Trick. This is essentially a DP optimization for problems where we want to perform $$$K$$$ operations, each with some "value" (in this case, the value of an operation would be the number of characters we convert from lowercase to uppercase, assuming we're trying to minimize the number of lowercase letters, or the other way around). There's a natural $$$O(NK)$$$ solution, of course, but Aliens' Trick allows us to optimize this to $$$O(N \log X)$$$, where $$$X$$$ is a value related to the precision of the solution.

The trick is fairly simple: essentially, rather than trying to compute the best we can do with $$$K$$$ operations, we assign some "cost" to each operation and attempt to maximize the number of uppercase letters in the final string minus the cost times the number of operations, while allowing ourselves to use any number of operations. In other words, each operation decreases our score by a certain cost. In this problem, we can easily determine the best solution given a fixed cost in $$$O(N)$$$ using some fairly simple DP. The trick, then, is that we can binary search for the greatest possible cost that will make us use at most $$$K$$$ operations. Then, we can reconstruct the answer using that cost, solving the problem.

Thus, for this problem, we split into two cases--in the first case, we try to convert as many letters as possible to uppercase, and in the second, we try to convert the letters to lowercase. The two cases can be handled identically. Within each case, we binary search for the cost of setting a substring of length $$$L$$$ to uppercase/lowercase, keeping track of how many operations we use for each cost (using the aforementioned $$$O(N)$$$ DP). Then, we can find the cost that ensures that we use $$$K$$$ operations: if a certain cost encourages us to use too many operations, we should try a higher cost, and vise versa. This lets us reconstruct the answer in either case, and we can simply print the better of the two results.

This reduction has removed some (potentially useful) restrictions on the input. Notice that all n of the segments have the same length, so the value of two adjacent segments differs by 0, 1, or -1 only. I don't know that you have to abuse this restriction to solve the problem, but it exists and isn't in your simplification.

Thanks for explaining. I just posted a comment asking why. :)

1
5 2
4 5 1 3 2
1 3

Answer should be 10. Your code outputs 6. Once you take out the 1, you still need to take out the 4 and 5 again before you take out the 3.

I see no really mathy problem.

Okay, I figured out that this is because of a peculiar reason in Java that I encountered first time, and maybe will helpful to others, so putting it here. I had Integer (not ints) values in the array, and I was using the comparison !=. This works fine for numbers in the range between -128 to 127 because Java is handling it separately (see this). However for numbers outside of that range, it treats it differently. When I used the equals method instead, the same code passed.

Kind of annoying, for 1.5 hours, I was trying to see what is wrong in my approach, including things like misinterpreting the problem etc. For example, I had implemented another approach which was giving even lesser results and so on..

If a > b + c + 1 or b > a + c + 1 or c > a + b + 1 then its impossible. In the other case, it's always possible to construct it like 1 2 3 1 2 3 .. 1 2 3 2 3 2 3 2 3 ( 1 is the biggest 2 is the second and 3 is min) and if there is 1 left we can place it between 2 and 3 in the triples.

If the max count among the counts of b, r, and g is $$$mx$$$, the 2 minimums are $$$mn_1$$$ and $$$mn_2$$$, then we obviously can't make a valid configuration if $$$mn_1+mn_2 \lt mx-1$$$ (we will definitely have 2 of the max color adjacent to each other). But what is the proof that we can always find a valid configuration if $$$mn_1+mn_2 \gt mx-1$$$? Consider the case when $$$mn_1=mn_2=mx$$$, assuming without loss of generality that the max color is r, you can obtain a valid configuration of the form rgbrgb...rgb, and for every $$$mn_1$$$ and $$$mn_2$$$ values where $$$mx-1 \lt mn_1+mn_2 \lt 2*mx$$$ you can always remove an instance of b or g without making two r's be adjacent to each other.

Its because of the following declaration

int item[100005];

Here, you declare an array of 10⁵ whereas a_i,j can be 10⁶ as given in the constraints