Ask codeforces contest style now. I'm also not fan of it.

Fixed, I just copy old one, didn't notice that. Thanks.

That means I won't be able to solve most problems :(

I am really excited then!

Thanks, Alexey, you haven't lied! (Не обманул)

Your goal is blue not violet.

Congrats your dream becomes true after years :)

yeah,i bought some rating from chemthan

I hope you won't call it mathforces

you downvote you gray

good luck and have fun -_-

At the worst case, you need to solve everything in order to become purple or orange.

Usually, you need to consistently be among the first few hundred placed people in div2 in order to get purple.

For purple : A + B + C fast enough, Easy D fast

For orange : A + B + C + medium D fast enough, + easy E

at least 4

Subtask 1's solutions usually are simplified versions of Subtask 2 ones. Like you replace one advanced data structure from the harder subtask with a simpler data structure and then boom you get subtask 1. So don't mind solving easier subtasks because they probably give you hints on harder subtasks.

Focus on your rating instead of contributions

It means your rating goes from 1441 to 1431 -_-

Neir:Automata <3

Minimise sum of squared outdegrees, I guess.

Basically, any triple of vertices is either a cycle or there's one vertex with edges into the remaining two (while neither of them has edges to the other two, obviously). The number of triples with cycles is the total number of triples minus the number of such pairs of edges, which is $$$N(N-1)(N-2)/6 - \sum outdeg_i(outdeg_i-1)/2$$$.

Notice that because of $$$|A_i - A_{i-1}| = 1$$$ condition, consecutive numbers can't have the same parity and hence $$$|cnt(even) - cnt(odd)| \le 1$$$

Next step is to handle 2 more cases $$$\text{assuming 0-indexing}$$$:

N is odd: if $$$cnt(even) - cnt(odd) = 1$$$, fill even positions with 0s then 2s and odd positions with 1s then 3s and vice versa when $$$cnt(odd) - cnt(even) = 1$$$

N is even: try starting with both evens and odds

Check if the array satisfies the conditions and print if it does

Actually it can be solved in greedy approach.(in case nobody mentioned it before) the answer can start with either the smallest number or the second smallest number, try both of them. When filling a new digit $$$a_{i}$$$ , it could be either $$$a_{i-1}-1$$$ or $$$a_{i-1}+1$$$, try $$$a_{i-1}-1$$$ first, if you don't have more $$$a_{i-1}-1$$$ then try $$$a_{i-1}+1$$$, if you dont have it neither, then stop.

Hopefully you can understand it cuz my english is not good enough.

1.Take a deque. 2.insert 0 if a>0 or insert 1 if b>0 or insert 2 or 3 using the previous condition for each number. 3.Now you have a head and a tail in the deque. 4.Then you continue pushing the remaining element.if its absolute difference with the tail element is one then push the element in the back of the deque. If it cannot be pushed to the back check whether it can be pushed in front. 5.if you have a+b+c+d>0 and you dont have any opportunity to push a new element you can break and print no.Otherwise the answer will be Yes and print the deque.

Expected days ( x )= sum of p[i]*number_of_days_passed

x= (1-p[0])*(1+x) + p[0]*(1-p[1])*(2+x) + .... + p[0]*..p[n-2]*(1-p[n-1])*(n+x) + p[0]*p[1]*..*p[n-1]*n

solve the equation for x under modulo, p[i] being the probability ( after dividing by 100 )

The meme of your account photo is so compatible with the picture.

This problem too had almost the same idea. Too sad, I couldn't participate today :(

much much earlier one in CN Winter Camp 2007.

I implemented it by trying all possible values of first number. Then, if the last number is 2, always prioritize going to 3 over 1 and if the last number is 1, always prioritize going to 0 over 2.

My solution is like:

Try to see what the finally path look like: First it will be ...->odd->even->odd->..., i.e. alternating parity. Also 0 and 3 can not be adjacent. So just put 0 as early as possible and 3 as late as possible, and fill in the rest of the positions.

Upd: There are actually two cases. If you have a sequence starting with an odd number, you should put 3 as early as possible and 0 as late as possible; otherwise, it is just what I mentioned above. Sorry for the confusion.

I implemented it in a very simple way:

You must match 0 with 1, and so you do until you run out of 0 (otherwise it's impossible since you can't match the extra 0)

Now you have "a first block" that looks like [0101...0]

Do the same but for 3 and 2, you have "a second block" that looks like [323...3]

Now you must merge both blocks with "a third block" that looks like [121...2]

If you have an extra 1, you can plug it in into the first block. Same for an extra 2 but to the second block

So the solution ends up being

[extra 1][first block][third block][second block][extra 2]

I have very strange solution. Let's denote how many times x goes exactly before y as c(x, y). And assume path will go from s to t. So we have 4 equations: c(1, 0) — c(0, 1) = (t == 0) — (s == 0) c(0, 1) + c(2, 1) — c(1, 0) — c(1, 2) = (t == 1) — (s == 1) same for 2 & 3... and another 4: c(1, 0) + (s == 0) = a c(0, 1) + c(2, 1) + (s == 1) = b c(1, 2) + c(3, 2) + (s == 2) = c c(2, 3) + c(4, 3) + (s == 3) = d

For fixed s and t it is system of linear equations, take any 6 of them, solve with Gaussian elimination. So we know how many times we have each pair of elements adjacent, let's make c(x, y) edges from x to y in new graph. now we need Euler path in this graph if it exists. Check it with well known dfs in 10^5.

Now just try all 4 x 4 pairs for s and t

Say no to greedy solutions)

I wonder if this solution is intended or not, I just went through all permutations of [0,1,2,3] and tried to find the answer if we use numbers in that order: https://codeforces.net/contest/1265/submission/66375662

It's alright to get stuck,you'll now solve the problems you were stuck on and won't get stuck in the future. :D

Implementation is probably the easiest skill to improve because it's literally just practice. You can look at other people's solutions to see if there is a cleaner high-level idea that you are missing (and a lot of these carry over to other implementation problems as well), but in general just doing a lot of implementation problems makes you much better at it.

For A the key observation is that you can substitute all ? by any of the three chars what is fitting there, ie simply check the previous and the next index.

C and D simply anoying. There is surely some greedy, but that kind of problem is just search for corner cases.

Wow!

yeah no, C D are not trial and error programming. Obvious greedy is obvious. Ain't the contest's fault if you don't know how to do greedy.

Div. 2 A and B were always intended as obstacles for starters. They were not intended to be complex for people who have already been blue.

C and D were greedy, yes, but you can easily prove their solutions. It was not even remotely hard to prove a greedy solution for C/D. Obvious greedy is obvious. If you don't like trial-and-error style of programming, then C can be solved with basic DSU, and, well, the math behind D can be easily proven with some analysis. I'm sure that such solutions wouldn't be too heavy in the implementation, and still satisfy what you called as "interesting".

Okay, let's admit that E is too easy for an average div.2 E — but the math behind it was a nice practice for everybody, and encourages blue/cyan competitors to try out probabilities problem. F was hard, yes, but it was intended as a challenge for the best (among blues, at least). Most div.2 F is often 2100+ — what did you expected? E 1500, F 1600, and you need to solve all 6 problems to be in top 1000?

Overall, the round does have some problems — E being a bit too easy, D's tricky 16th test case — but it was nowhere abysmal as you described. It's not the contest's fault when you sucks in the contest, and the contest wouldn't care either.

It was a useful subtask, but still not very interesting. It's just some DP(number of ways such that the i-th character is the d-th opening bracket) and DP(number of ways such that we have at least d closing brackets among the last i characters).

At least D2 offers "hmm, how do I solve this?" rather than "yeah I'll obviously do this".

For me it looks that they are trying to hack all greedy solutions now :)

It would be great if someone knows counter-testcase for greedy, just to stip waiting :D

Well, some heuristic solutions passed and some failed, classic

Irritating for me. Corner after corner

You iterate $$$\mathrm{i}$$$ from $$$\mathrm{1}$$$ to $$$\mathrm{n}$$$, update $$$\mathrm{left}$$$ (leftmost position of all previous iterations) and $$$\mathrm{right}$$$ (rightmost position of all previous iterations) with position of $$$\mathrm{i}$$$, and $$$\mathrm{i}$$$ is beautiful if $$$\mathrm{right-left+1=i}$$$

Make an array of pairs of (number,index) and sort this array by number. Now for each prefix (1-i) of this array, we only need to check if all indices of this prefix form a subarray in the original array. If they do, then answer for i is 1,else 0.

To check that, let S be the sum of the indices of prefix (1-i). And let M be minimum index in all these indices. Then (S- M*i) should be the sum of first i whole numbers (i.e sum(0-(i-1)) =(i*(i-1))/2.

Keep index of all numbers in map, now start with i=1 to i=m use a set and result string initially which is initially empty

for each m insert m in set, now take the first and last value from set, if this is equal to size of set then append '1' else append '0' to the result string

yes , you are right .

Sure. When you know the formula for expected value, the rest is fairly standard "compute function over interval". It also works for a more general version of this problem where $$$P_i$$$ can be updated too.

Probably, but that's a bit overkill for the problem. You really just need prefix computations of certain sums (in particular the product of the first i probabilities and then prefix sums on the product of the first i probabilities). Then you can answer any segment in log time by calculating the numerator and denominator independently and using modular inverse.

whaaaat?

There were sooo many WA16 and several WA6 as well, and until I checked all cases thoroughly I got WA...

You will improve don't worry :)

I couldn't finish impl it on time.

but this should work, if you can get E(i,j)=from ckpoint i to ckpoint j. in O(1). since each update just change adj-ckpoint.

you need to preprocess prefix sum of $$$P_i= p_1*..*p_i$$$, $$$S_i = \sum P_i$$$, $$$T_i = \sum P_i*i$$$

since $$$E(i,j) = j-i + [dT_{i-1,j-1} - (i-1)*dS_{i-1,j-1} - (dT_{i,j} - i*dS_{i,j})] / P_j$$$.

Can you explain the simple DP approach?

Expected number of $$$x$$$ is summation of all possible values of $$$x$$$, each multiplied by its probability of occurrence. If $$$x$$$ is a continuous (not discrete) variable the summation is converted to integration.

Check the blogs of Errichto. :)

take minimum gold, take silver until it"s greater than gold rest till n/2 is bronze. Also you can't take the contestants with minimum solve and can't divide contestant with equal solve between silver and bronze or bronze and no prize.

Be calm see my profile I have struggled more than you but still I have not become an expert this site is more challenging.

Keep calm. And solve problem after the contest.

No need for that though

From my point of view using a list does not give advantage in this problem. One hast to check the chars at position +1 and -1, both is a[i+-1], using a list or a string.

Why do you need it? You can look at the front and back for questions and find the answer from this.

So my B failed because of this dumb typo:

if (a + b == b + d)

I decided to look at the pretests and found that out of 17 pretests, 11 have no answer and the remaining 6 have an odd total numbers. Don't know if it's intentional or not ¯\_(ツ)_/¯

I think 0 is non-negative.