These two statements don't seem exclusive to me. It doesn't say the round is open to all div1 and div2 participants.

what about offline round?

Yes. It is rated.

rated

Dude you made history.

This is the first time i've seen "Is this rated"/"Is it rated" get upvotes

"Take Risks In your life"-Swami vivekanada

Sorry if it was unclear, only those who placed in top 500 in Round 1 can win a t-shirt. They will be registered in Div. 1 automatically.

I called up MemSQL and they said there is. Consider this resolved. :)

We will have enough room for everyone to plug in their laptops.

Don't forget your chargers, this round will be longer than regular CF rounds!

Div 1, read KAN's comment above.

because they placed top 500 in the first round of memsql

Petr

Both of them are legends, but tourist, i mean come on...

good timing for you is a bad timing for others. http://codeforces.net/blog/entry/54744?#comment-387598

You are in top-500 of Round 1, so you should compete in Round 2, which is a div1 contest.

really ? I passed the problem without any problem . i had a first try compile too which is an strange thing for me .

I solved it greedily

Greedy.First construct an best solution without caring if you will require an extra pizza.After that try removing slices which minimise loss for 2 cases(one less pizza for type1 and type2).

Can we solve it with maximum matching?

Here's what I did for Div 2 E (without segment trees): Have two sets(multisets) of unsold and sold items respectively. Every day, when you encounter a new price, you may choose to do one of the following: 1. sell the smallest element in unsold. 2. insert the smallest element in sold to the unsold set, and replace it with the new price in sold set for better profit, or 3. insert this new price in the unsold set(when both cases bring negative profits.) This has overall time complexity O(nlogn). submission

Can you provide some resouce for learning treap datastructure? TIA.

C: My solution is to fix answer by binary search!

D: I passed pretest using segment tree (greedy approach).

I did a simple greedy that passed but no proof

It is like that http://codeforces.net/problemset/problem/391/F3 but different a bit.

It is like searching for "max-cost matching" with edges of weights c_i-c_j (where i > j) in complete graph. However, I don't know how to do it effectively enough...

I passed pretests using this. I always choose the lowest available stock. Then buy the highest possible "valid" stock. To check valid, I maintain prefix sums in segment tree, then I execute a range max query on some suffix of the array to find the selling point.

UPD: Got AC. :D
Code

I have pretest passed with this greedy algorithm: https://ideone.com/HPBkr4
I iterate from the last object to the first, and push to the priorityqueue all the items with a flag if it was sold to a item with higher price (and greedily adding this difference). If this item appears at the top of the pq it means that if I bought it at Y and sold at X, and now I'm buying at Z with Z < Y < X, then I can change it to buying Z and selling at X, and being able to sell at Y when I encounter another item.

i too tried using seg tree + greedy ...but it TLE'd on test 3

Can we at least look at other people solutions?

onsite finalists need to have some rest and talk before they will be ready for the results revealing

no we do not

systest already please

My friend forgot to sort an array and he failed at test 7 too.

If a = 1, just print 1 1 1, else if we have only 2 and 1 denominations, answer for some n will be n / 2 + 1 (can be easily proved), so for some a we print 2 * (a — 1) 2 1 2

You can get any number of combinations by using the set of coins D = {1, 2}.

We can use the formula for Combinations With Repetition to calculate the number of combinations.

can u explain your solution please

Fn * Pn + Sn * (1 — Pn)

The above one doesn't calculate the expected time ending at some 'X' second . If fn is chosen you complete earlier than 'X' by Sn — Fn seconds. Later this propagates wrongly for Fn case.

The answer is the constant term of series

.

Let M = max c_i. So the answer is

.

Subtract the remainder from the numerator, and substitute x=0. You can get the constant term of the quotient.

You can find the remainder using polynomial division only. So the time complexity is .

My solution to F (which hopefully will sneak under TL and ML):

First, don't end the game when one person eats R raw eggs. Then if one person ever gets at least R+1 total raw eggs, that person is guaranteed to lose. Therefore we can only consider the cases when each person eats exactly R raw eggs and C cooked eggs, and we want to minimize |# scenarios in which A wins — # scenarios in which B wins|, out of a total of (R+C choose R)^2 total scenarios.

Now look at a sequence of A and B as path on an (R+C) by (R+C) grid. The number of scenarios in which A wins is the area under this path (grid segments will have length not 1 but (x choose r-1) ). We can use dp with a map to keep a list of which areas under the path are possible at each points in the grid, as well as how many paths attain that area.

Finally, we need to use a meet-in-the-middle to speed this up. For me, the best choice for "middle" in the case where R = 10 and C = 20 was the first 38 turns vs last 22 turns.

To speed this up, I also precalculated the optimal difference for each R,C and hardcoded this into my program.

E: first, let's try all possibilities for which of the positions have "carry" when the subtraction happens. Now we know for each position the difference between the numbers. The sum of all those differences must be zero (this cuts down the number of possibilities from 2**13 to C(13, 6)).

Now let's look at the cycles of the permutation of the digits. Each cycle must have at least one zero digit (otherwise we can decrease all digits to get a smaller number). So we can assume that we have just one big cycle, since they can be joined using the zeros.

Now we need to build this big cycle. Let's build it starting with its zero, and then each next digit is given by the current digit plus the difference in the current position (which we already know from the first paragraph). So we can do dynamic programming where the state is the set of positions we have already placed, and which remembers the smallest number formed by digits in those positions. In order to find the next digit to be placed, we just sum the differences of the already placed positions.

Overall running time is around C(13,6)*14*2**14 which is 400 million.

You will get 170 ratings if all 3 of your solutions pass system test.

I got wrong answer on C whyyyy :(( #still_not_expert

you can submit now.

can u pls explain your solution, basically when p1 % s + p2 % s <= s in your code?? tia

It have posted. Link: click here

Each number has a certain number of twos. These twos can be made either of the coin value 2 or two coins value 1. So each time you increase by two, you are increasing the result by one possibility. Therefore it's 2(n — 1).

First try to allot everyone the slices they prefer (max(a[i], b[i]), ignoring the restriction of buying minimum number of pizzas.

To fit into the restriction of buying minimum number of pizzas, you will have to give some participants slices they do not prefer. To minimize this 'regret', you will want to disappoint the people with least (a[i] — b[i] or b[i] — a[i]) values. In case of a tie, you want to disappoint the one who eats less slices (s[i].

Create two groups, people who prefer pizza of type 'A' over 'B' (a[i] > b[i]) and others (a[i] <= b[i]). Let's call these groups group-1 and group-2. Try to disappoint participants from one group by storing pairs of (a[i] — b[i], s[i]) (eg for group-1) for both groups.

Sort these vectors of pairs and greedily disappoint participants of both groups independently. Your final answer is (max_happiness_ignoring_restriction - min_regret_of_the_two_possibilities)

You can look at my solution for details 30902595