Recent actions

In problem F constraints were R, C ≤ 20, R + C ≤ 30. At the frist sight it seems that only R + C should matter, so one may think that if it is solvable at all then it is solvable also without constraint R, C ≤ 20, but after some time it can be seen why that can matter. Solution provided in editorial in fact works in O(C·2C), so it is fast for small values of C. My solution however works really fast if C is larger! For example, for R=20, C=10 it works ~2.4s and for R=10 and C=20 (if I change preprocessing from 25 to 15 steps) it works in 0.01s! So it seems that in fact merge of mine and original solution would lead to solution handling all possible cases with R+C<=30 and probably will handle even R+C as large as 35. However I would be reluctant to give any precise bound on running time of my algorithm, it uses some heuristics :P http://codeforces.com/contest/866/submission/31928336

EDIT: Uhh, I dug a little bit and it turned out that in fact running time of my algorithm is not increasing with R, for (R,C)=(1,20) my code runs significantly longer than on (10,20) and my code can't handle (R,C)=(1,29) which I claimed earlier it will handle in no time :(.

0

:'(

+8

So are there any updates about the T-shirts(tbh, I only care about this year's...). I hope there is still hope.

0

I got your solution but don't know how to compute remainder. can you plz explain or provide some source where I can learn it

0

Why don't tag this editorial to the announcement? It's really disturbing to find the hint for a difficult problem consuming a lot of time.

-33

I really liked your article , your article is very petrified me in the learning process and provide additional knowledge to me, maybe I can learn more from you, I will wait for your next article article. Thanks a lot for providing this much informative stuff is perfectly excellent. color switch

0
0

I drew it out and saw basically:

1 = 1 = 1 combo

2 = 1+1 or 2 = 2 combo

3 = 1+1+1 or 2+1 or 3 = 3 combo

4 = 1+1+1+1 or 2+2 or 2+1+1 or 4 = 4 combo

5 = 1+1+1+1+1 or 2+1+1+1 or 2+2+1 or 5 = 4 combo

6 = 1+1+1+1+1+1 or 2+1+1+1+1 or 2+2+1+1 or 2+2+2 or 6 = 5 combo

You see a pattern that for each combo amount, the number that makes the combo amount is floor(num/2)+2 (ex: floor(5/2) + 2 = 4). So you "reverse" this because they give you the combo amount, making it (combo-2)*2 (ex: (5-2)*2 = 6). This way, you can make the given combo amount made up of numbers 1, 2, and (a-2)*2.

0

Where are editorials of this round? I am looking for the editorial of 'Ordering Pizza'.

0

I just see that Problem Div 2B is so entusiactic. :D

0

Thanks !

+8

It has been available since yesterday: link. The announcement isn't updated.

0

please publish the editorial

+8

Got it. Thanks for the help!

-13

if you dont know telavshi tovs and you can come with us for seeing tovli without any top 500 whatg do you think? p.s subscribe my YT channel "qurdi baxbaxa" and iqurde with me

0

If you have two people that like pizza A more than B. Suppose that the first one likes A = 15 and B = 14 and the second one likes A = 5 and B = 1.

If you have to chose one of them to feed using pizza B (because you don't have pizza A anymore), which one you would you chose? It's easy to see that the first one is better because you would lose less than if you chose the second (15-14 < 5-1).

So if you have to change someone take the one whose difference between A and B is minimum.

0
0

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

0

"In each of these cases we do greedily calculate max pleasure and choose the largest between the two."

How do we do that? Pixar

0

Thanks, got it!
Do you see any way to tune this formula? Or idea "DP by completion time from level to level" is completely wrong?

+11

First, assume the expression is simple, and doesn't contain min operations. So, basically it'll be like dp00 = a + bX.

Of course this can be easily solved. But I want you to observe that in this special case, dp00 < Y.

Proof:

dp00 - R = b(Y - R)

0 ≤ b < 1

|dp00 - R| < |Y - R|,

hence if Y > R, dp00 < Y.

Try to generalize this proof to include min operations. If you couldn't, I can elaborate more.

0

How to prove that binary search can be applied to Div2D? I solved this problem but I can't prove it.

0

It have posted. Link: click here

+5

I accept that if we put X as the optimal answer R, then, indeed, dp00 will have the value of R after the recurrence. But how does one prove that by assigning X = Y such that Y > R won't make dp00 ≥ Y?

+10

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.

+15

The editorial is available since one hour, but the contest announcement hasn't been updated yet, so here's the link

0

[user:codeforces.com/profile/Pixar]helped me to understand.

0

Okay, it's clear to observe now. Thanks a lot :)

But did it came just from observation finding pattern or there's a theory that helped you which can be used for a different variation of this type of problem?

+20
+6

Can anyone explain div2 C?

0

has it editorial or analysis?

+10

Suppose we have to make k cents from a set of 1 cents and 2 cents. let k=1,then possible states are (1,0) (1 coin of 1 cent and 2 coin of 2 cent) i.e 1 way if k=2 then states are (2,0),(0,1)---2 ways if k=3 then states are (3,0),(1,1)---2 ways if k=4 then states are (4,0),(2,1),(0,2)--3 ways if k=5 then states are (5,0),(3,1),(1,2)-- 3 ways if k=6 then states are (6,0),(4,1),(2,2),(0,3) --4 ways so,there for k=n, there are (n/2)+1 ways. In the question,we are given ways and we have to find k. So,it will be 2*a-1 where a are given ways

0

No, it's still not clear to me. I've just started combinatorics from a few days ago. I know the basics. But I am not able to relate those with this. I can catch up only if you explain. Would you please? Thank you.

0
+1

can anybody explain me Reyna's solution in D/Div 1 ? 30879284

+1

Sure!
It's good that you've asked. I've read my comment again and I see that it's not good =)

Yesterday I have started with a Diophantine equation x1 + 2·x2 = k and came to a - 1. This equation just stuck in my head and was thinking that there is a small mental step to multichoose(n, k), but looks like I was wrong =)

Do you understand how to get to a - 1?

+8

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

0

Thanks a lot sir :) Can you also give me some suggestions on how to start dp??

0

I've read the wikipedia. But "You can get any number of combinations by using the set of coins D = {1, 2}. ", it's still not clear to me. Can you please explain a little more? :(

+2

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

+1

if (p1%s + p2%s <= s) then we can make 1 pizza of remaining slices from both pizzas. So, we'll try both the cases. First add remaining slices of first pizza to second pizza starting from the slice whose difference between first and second pizza is lowest. Second is add remaining slices of second pizza to first pizza starting from the slice whose difference between second and first pizza is lowest. Then the maximum of above two cases is the answer.

0

Hey, Can you explain How you solved problem C ?

+7

When can we expect Editorials? Other's solutions too hard for me to grasp :/

+42

when will the editorial be out?

0

http://codeforces.com/contest/867/submission/30902968 plzz help, why i m getting runtime error on testcase 6?

+5

Hey Please Give me the approach to solve Ordering Pizza :(

How to solve Ordering Pizza Div-2(C) problem?

0

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

0

But still getting WA. :(

0

Thanks man, that's really helpful.

Welp, this made me realized I probably don't belong in codeforces contests until I practice more.

+11

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).

+7

For Div2 B / Div1 A, can someone explain tourist's code? 30874326

Why do we need to build max(1, 2(n-1)) using 1 and 2 coins to achieve n possible combinations?

Any insights would be appreciated c:

0

I think my solution implicitly uses this (which gives the choice of split at 38/22). It is very tight at the time limit, though.

0

Close to intended solution, however if you notice that the first R-1 rows and columns in the grid have zero area, you only need to meet-in-the-middle on the remaining 2*(C+1) moves.

+8

When will the editorial be posted ?

+22

First one to solve Problem C. Rank 1 for 5 minutes. Great feeling :D

0

you can submit now.

+70

Never in my life did I imagine my name will be in contest announcement. Thanks cerealguy

0
Created or updated the text
+6

When will we be able to submit?

0

Yes... I thought the hardest problem in the memsql cup should be unsolvable (like 457F). So I skipped this one during the contest.

However, I think this one is much easier than E and F for me :(

0

how you predict rating ?

-49

sorry but i was stupid, and problemsetters were not stupid.

0

WA on test case 60 on C. Disappointing!

+9

I should delete the extension and let you tell me :p

+5

He'll now get +108 as he got FST on C

0

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

+33

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.

-17

So this problem is only about knowledge. Once, you know, just write and get it. Not much thinking.

0

actually his rank can be better

+9

So that's why he will get more than +170 as his rank must get better because of people getting FST, assuming that his all 3 solutions passed.

0

Actually there is an extension available for chrome that predicts the exact rating change. It said he'll get 170 ratings before system testing started

+8

more than 170

0

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

+18

Just start the system test already. I can't wait to see whether I become blue or not

+3

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.

0

came after 1 hours to see standings! still pending system testing!

0
0

Your idea looks better =)

+28

The answer is the constant term of series

.

Let M = max ci. 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 .

+36

When will system test start?

+3

How to solve Div1 E, F, G? I tried to solve G using matrix powers, but my solution is too slow.

0

I actually tried to shoot the mosquito with a cannon," I used binary search and then coin change to fix the number of ways".

+3

most of the time it takes more than an hour anyway

+3

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.

+15

Split all the people into 2 groups: A, B.
A = { people who prefer pizza A}
B = { people who prefer pizza B}

S(A) — the number of pizza slices needed for group A.
S(B) — the number of pizza slices needed for group B.

Now the best thing to do is to feed group A with pizza A and to feed group B with pizza of type B.
We can do that almost always.

Some pizzas of type A will be completely eaten by group A, but there may be needed some more pizza slices to feed the group A, but these slices do not form a complete pizza.

Consider the remainders of pizza slices:
R(A) = S(A) mod S — pizza slices needed for group A, without forming a complete pizza.
R(B) = S(B) mod S — pizza slices needed for group B, without forming a complete pizza.

If R(A) = 0 or R(B) = 0 or R(A) + R(B) > S, we can buy new pizzas of correct type and give them to corresponding groups. So in that case everyone will get the pizza slices from pizza that he wants.

There is only one case when we need to feed some people from group A with pizza of type B (or the other way around). This is when R(A) > 0 and R(B) > 0 and R(A) + R(B) ≤ S. In this case we need to buy only one more pizza and we check two cases: 1. This pizza is of type A, 2. This pizza is of type B. In each of these cases we do greedily calculate max pleasure and choose the largest between the two.

+2

you could have used 2 * a — 1 and not have to worry about the case of 1.

0

Oh, I missed the case of 1 :(.

0

According to my idea, I sorted all elements of array a and then start taking them one by one.

In each iteration, my idea was to find the maximum value in the array from pos + 1 to n where pos is the actual position of that element in array a.

0

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

+5

I maintain prefix sum in a segment tree. I find leftmost index such that no point to its right has prefix-sum 0, using binary search on segment tree. When I buy a stock, I do +1 range update and when I sell a stock I do -1 range update.

+61

Tonight, I'll dream of a pizza containing 100000 slices :D

0

Okay, I am being able to relate my idea with this idea.

Can you tell what will be the best choice for an edge then such that it can be taken into count?

0

No Hacks this time !! :)

0

can u explain your solution please

0

I didn't solve the problem, but I've started thinking in the direction of graphs.

When we choose to take some number ai, we need to find a pair for this number aj, such that j > i and aj > ai. The weight of the edge (ai, aj) is wij = aj - ai. When we choose an edge (ai, aj) that excludes all the edges which come into aj.

0

sorry i dont understand how are u choosing the range for valid stock. I understand that it will be some suffix of array but how to find where does that suffix starts?

0
0

Nice!

Thanks a lot.