the didn't test the boundaries of the constraints thus causing many people to get time limit exceeded on the main system tests.

can you please elaborate more?

Maybe unpopular opinion but I think that weak pretests don't necessarily lower the quality of the round.

But the data of Problem D is so annoying!

попробуй pypy

.-. if you like I had a better O(n) solution: 117940985

Shitt!! These events are not equiprobable. I just multiplied by their probabilities and it ACed. Sadly I was debugging this for 1hr in the contest. Sorry for my silly question.

yup,,,,good job

your previous round was great

what happened this time?

Well, judging by Petr's comment the TL was not tight enough.

With some optimization i was able to pass systests.

Submission

Feel Free to hack ^_^

I think it was easier to solve D with greedy than other methods. I just figured the best indices for putting 1 and then greedily replaced some 1's with 0's in order to get the best solution. However, It would be quite interesting if someone can find a counter case for my solution. Here's my submission 117911118

PS: Its runtime was better than bitset solution :)

it is even funnier because test 127 was sunzh's hack (and it was the only hack to this problem during contest)

(I also failed on 127, same as the only second person from my room who passed pretests on D)

sharath101 why did you use bitset, as m < 61 we can use long long right? or is bitset faster then long long.

Hey did you find any test case please let me know if yes. Thanks in advance :)

C has a really nice solution, though you are right at the statements part lol.

Although you might have solved C in a few minutes.

Your CF Round #684 was infinitely times worse. Just stupid implementation crap. Except problem C all other problems were very good.

the problems a,b,c were trivial. just implementation. statement of c would have been unclear without picture but with picture and example it was clear. the idea of hosting div1+div2 is weird. obviously 1k+ people of 2100+ rating would beat all div2 participants. thats why people think not giving contest is better than competing in a contest with 1000+ offset rank

your opinion is wrong. i understood the statements, so you’re just making excuses for getting negative delta.

Try

1 
3 1000000000
010

$$$M$$$ can be upto $$$10^9$$$.

run loop till min(n,m):

the intuition of stack: since suppose we are at inner of some list, and if the current value is not able to further increase the inner list to we need to go just outer list, this gives an the intuition of stack.

at any time stack will look like this(it will tell the just previous of current list) ''
{ .
.
1.3.2
1.3
1
}

1. the first result will be "1" always(so first a1 will always be 1).
   

2. now see ai:
   

   2.1 first extract last no. in top of stack like(1.3.2) is 2 lets say it is temp.
   2.2 if(ai==3) or ai==temp+1, it means we can add list like 1.3.3, so just remove 1.3.2 from stack and push 1.3.3
   2.3 else if(ai==1) it means that we can't increase 1.3.2, but we can make like 1.3.2.1(think why it always works :) ) so just create 1.3.2.1 and push in stack
   2.3 else we need to go outer of current list so just pop(it will never become empty if solution exist)
   

My solution

Check is O(n), because a whole string is given to function (not a pointer). Try to change bool check(string s, int i) into bool check(string &s, int i).

You are doing a very trivial mistake.

Whenever you are calling check function a new string is created for the check function which takes O(size of string) time for copying all elements from original string.`   
So there are 3 things you can do.  
=> use & while defining check function.   
=> define the string globally.    
=> check only when needed.  

So i made this change in your code and it is Accepted. Submission:117923870

Found the answer in ecnerwala's solution: the states F(mask, x) are always visited in increasing order of x for the same mask, so we can just iterate over mask after each quest and check if "x" should be increased to visit appropriate F() states.

round was bad. most people solved only A, B and C, because D was hard

I'm not sure whether it has to do with English...

Anyway, in C I just skipped all the gibberish and figured out the true statement from the picture and examples. Not the first I had to do this

1) 1 sec 2) It might be because the compiler recognizes that the a and b variables don't do anything, or it sees the for loop and concludes that the only thing that the for loop does is change the variable a to the value 10.

For anyone else having problem here is explanation I can understand from yash_daga in the announcement post:

"Randomised solution for D:

Randomly take a friend and assume it to be the part of the final subset now compare all other friends with this subset and use submask dp in the end to find maximum size subset. I took 25 random friends."

I think it's roughly equals to (number of CF users hit by meteorite fall) / (number of meteorite falls)

For each participant, they rolled a 10^6 sided dice using random.org. If it came up as a 1, then they used their advanced space technology to locate the contestant and hit them with a meteorite.

https://math.stackexchange.com/questions/497101/showing-that-rm-ex-sum-k-0-infty-pxk-for-a-discrete-random-variabl

I think this answers your question. Note that P(X > 0) = 1; and then P(X > k) is the probability that there are k lights on and we haven't stopped (there will be at least one light more, so X > k). This formula is true for continuous case (with integrals)

I think some of the formulas in the editorial have off-by-one errors, as I had slightly different formulas when upsolving. In any case, I can try to explain the idea.

First, we can rephrase $$$\text{E[lights turned on at the end]}$$$ as $$$\text{E[number of turns the machine works for before breaking]}$$$, and split that into $$$\text{E[number of turns the machine works for and is one turn away from breaking]} + 1$$$. Now we want to count the aforementioned quantity.

We can count more generally the number of states the machine can be in, such that no subarray of size $$$k$$$ has more than one light turned on. Say the machine has worked for $$$p$$$ turns, meaning it has $$$p$$$ on lights. In order for the $$$k$$$ condition to not be violated, there must be at least $$$k - 1$$$ off lights in between on lights. We can think of this as a stars and bars problem: our $$$p$$$ lights function as bars separating the remaining $$$n - p$$$ off lights into $$$p + 1$$$ groups, where the middle $$$p - 1$$$ groups must each have at least $$$k - 1$$$ off lights. If we start by putting $$$k - 1$$$ off lights into each of the middle groups, then we are left with $$$n - p - (k - 1) \cdot (p - 1)$$$ off lights to distribute into $$$p + 1$$$ groups, where groups may be non-empty. Applying stars and bars (specifically theorem two in the link above) gives us $$$\binom{n - (k - 1) \cdot (p - 1)}{p}$$$.

Now, not all of these states can lead to the machine breaking in the next turn. But each state contributes some amount to the answer. The machine starts at the state of $$$n$$$ off lights, then each turn it moves to another state by turning on some light, until it breaks. So the number of turns the machine works for is the number of states on the path it takes. Each state thus contributes $$$+1$$$ to the answer for the probability that it is on a path. The probability that a state with $$$p$$$ on lights is visited is $$$\frac{p!}{n \cdot (n - 1) \cdot (n - 2) \cdot \dots \cdot (n - p + 1)}$$$. Editorial says $$$n - p - 1$$$ but I believe that's a typo. This comes from the fact that we can pick any of the $$$p$$$ lights first, then any of the $$$p - 1$$$ lights second, and so on. Similar logic is applied to the denominator.

So our final answer is thus $$$1 + \sum_{p=1}^n \binom{n - (k - 1) \cdot (p - 1)}{p} \cdot \frac{p!}{n \cdot (n - 1) \cdot (n - 2) \cdot \dots \cdot (n - p + 1)}$$$.

Let $$$X$$$ be the random variable denoting the number of lights turned on when the $$$\textbf{process terminates}$$$. Now, let us try to figure out the value of $$$P(X \geq d)$$$. It is easy to see that for $$$d \geq 2$$$ , the value of $$$P(X \geq d)$$$ is nothing but probability of arriving at sequence of $$$(d-1)$$$ elements such that each pair of adjacent elements are $$$k$$$ apart. And that $$$P(X \geq 1) = 1$$$. Now, once this is done we can write
$$$E(X) = P(X \geq 1) + P(X \geq 2) + \dots + P(X \geq n)$$$ as $$$X$$$ is discrete random variable.

Hacked with a generator I stole from someone else :P

That's true for Prob. D as well :(

I'm guessing you did that. If so, that is the reason why you are green

I support you that writing the bruteforce here is a totally acceptable way and it is not necessarily a sign of being green. Actually I got lucky and managed to find a solution manually, but I was questioning the validity of such method while doing so thinking of coding bruteforce

I can tell you why. Because some hackers will observe your code and make a set of data according to your random process. To avoid that, I recommend you to use a unique random seed or just srand((unsigned)time(0)*time(0));. Wish you good luck.

Let us take an array of just 2 elements, say {a, b}. Think of it this way. We can convert it to {-a, -b} in 6 moves. How?

Look carefully at these operations:

(I will be denoting the first element as x and second as y, because their values will be changing)

x = x + y; now we have {a + b, b}

y = y — x; {a + b, -a}

x = x + y; {b, -a}

So we can see that these 3 operations got us from {a, b} to {b, -a}. It is clear enough now, that applying these 3 operations again on some {x, y} will get us from {x, y} to {y, -x}, i.e. {-a, -b}.

I hope it was clear. If it wasn't, please let me know!

Here's the simulation for the first pair ($$$a_1$$$, $$$a_2$$$). Similarly we apply the same six operations to the rest of the pairs . The number of actions is $$$n / 2$$$ pairs * $$$6$$$ operations $$$ = n * 3 $$$.

All you needed to know was SOS DP

hacked

The problem ratings are unknown before the contest, and are calculated after the constest on a basis of how much people solved them.

So we can consider the problemsetters try to choose them best balanced as possible, but sometimes the results are not exactly like expected.