unfortunately no

I'm not sure if this is very correct but for these small cases:

2 2 2 4 4 4 4 : it is obvious what the answer will be equal for both

3 3 3 4 4 5 5 : here after one move from alice and bob the array will look like: 2 2 2 4 4 4 4

same as above so the contribution of even elements is always distributed equally.

merging can happen if the current player chooses an even x and there exists x-1 this is always bad for the current player as the count of x-1 will go up and it is then advantageous for the other player to play using x-1.

the other merging odd->even is good for the current player as they get the best extra share possible (provided they choose the odd term with max frequency because you get to choose this only once) and the merged terms are evenly distributed between the two afterwards.

I'm not sure if this cleared much here, if there is anything i missed do tell!

You have a big fat if statement before that second loop It ensures that the loop for j 0->n is not run everytime.

Hacked your submission i can go to bed peacefully now.

what if we don't check the unique minimum case? will it time fail directly?

and even if we do check it suppose there are 2 identical arrays(minimums) so leading to no unique element case. In this scenario isn't this method leading to a (mx*n) time algorithm? is that fine? (could you please explain how it runs fine?)

my similar solution also passed that didn't check for unique case but kept track of when a minimum array ends(since it gives more options) however i am not able to analyse the worst case complexity. During the contest i assumed it will exceed TL. 338529461

(k−1)^n−r⋅(m−k+1)^r⋅cnt[r]

isn't this line just the number of ways to create a mask with (n-r) places with < k and r places with >=k, cnt[r] times. So then how how are we accounting for the sum of the actual values left at last? What am i missing here?

A really stupid solution to problem D but i like it cause of the optimization from n^2 to n

so dp[i]= min attacks to clear i...n

now to calculate dp[i] in n time we can check for every j>i.

something like

1] h[i]+dp[i+1]

2] h[i]+h[i+1]-(i+1)+dp[i+2]

3] loop j over i+2->n and find the minimum of sum till j +dp[j+1] call this above; so dp[i]= h[i]+h[i+1]-(i+1)+ above

                ll above=1e18;
		ll so=0;
		for(int j=i+2;j<n;j++){
			so+=a[j];
			so--;
		 	above=min(above,so+dp[j+1]);
		}

but then it can be noticed that the value of above can only change at the current i if it does change so a simple check a[i+1]+dp[i+2]-1 will do this you can try to prove this greedily .

here: 335464375

Here

This is how i understand it: (after the Umnik video) You can convert it to a take not take dp and since a token can only be picked from positions greater than equal to where it resides it gives us the idea that we can start iterating from the back.

let dp[i][j] be the number of ways to pick j tokens from [i,n] tokens; now for the transitions if we dont choose the ith token then dp[i][j] is just dp[i+1][j] else we choose the ith token now there are (n+1-i) positions who could have chosen the ith token (remember that a particular token can only be picked up by a larger or equal position) and out of these (n+1-i), j-1 have already been used so that leaves (n+2-(i+j)) positions on the right that can choose this token.

Now this is where l[i] comes in because there can be multiple different arrays that pick the tokens in the same order and we have to count all of them!

for a position to be able to pick token i the value at that position should less than equal to i (remember the range [a[k],k] so there are i options for this left boundary thus for the take transition we get : dp[i][j] += dp[i+1][j-1]*(i)*(n+2-(i+j)).

hope it's clear : 327920799

Same it's just nPi right?

My Take / not take solution doesn't TLE though it is very slow.

if you want you can take a look here:SOLUTION

dp[x] means number of vertices needed to form x colorings now we are dealing in subtrees so there are 2 more options of coloring them entirely blue or yellow which don't exist in dp[x] so if we find the number of vertices which can be colored in x-2 ways we can do the other two colorings and get x

Goal: Proving this predictor wrong lol

This is the wrong blog to comment this on anyway the ratings should be here anytime now

Man's got the CF rhythm

i think the minimum path for the second will then just be 2* edges — dist(start-end) look at Jain's comment

lol

the size of the tuple is A+1 first element is a number from 1 to K and the next A are positions (from 1 to N) so out of N positions there are NcA choices and K ways to chose the number

note that the positions don't correspond to the chosen first number in the tuple here because we just want to find all the possible tuples.

also N is the number of rows calculated earlier so there are only N choices for the position

sorry:

they've considered a straight chain of 3 nodes in the explanation i think it should have been mentioned

NVM

suppose s[i]='1' then ans[i] stores the answer for all substrings ending at i now you can see that this value wont change a lot from ans[i-1] it only changes when adding the last element to a subset increases the majority and this increase is only by 1 so you just have to add this number of subsets to ans[i-1] to get ans[i].

so find all such subsets using the difference in count of 0 and 1

let pref[i] be count(1)-count(0) till i;

then at all previous places where pref[j] < pref[i] form the required answer; ordered set does it quickly

similarly you can derive it for when s[i]='0'

same here 323532905

i don't think this implementation is very difficult only the observation took some time

super fast editorial

i think the people who rated E high solved it using some crazy DP idea

but after applying "digits" twice x can be as large as 16!!

This submission fails on Test 6 can anyone help me with what is wrong? problem D

320150215

edit: i changed the max distance of a node from 1 to 1e18 from the previous 1e9 and it works

forgot to see that max(a[i])*l is atmost 2e9

You've done -4,-2,-1 instead of -8,-4,-2,-1

This was quite a non-standard task so there isn't any formal way of doing it.

Listing down ideas help like(this is what i thought of):

3 times "digits" and get a single digit number

division is not very useful

there are just 9 numbers what can multiplication do?

then you notice that multiplying by 9 keeps digits same(i thought of 11 and many other numbers too)!

this was sufficient for C1 then for C2 you realize multiply by 9 then "digits" twice will give 9 again so a 4 step solution!

this is how far i got in the contest(i did not participate but solved the problems separately) later is saw jiangly's code and saw the 999999999 thing and it did feel like a continuation of what i did for C1 and C2. Maybe i was just too lucky not going for the reduction by 8-4-2 path (it just didn't click then)

multiply by 999999999

then the sum of digits will be for sure 81;

so then digits and add n-81

It's actually quite interesting if there is a very a neat proof maybe Hosen_ba could help!

thank you so much for the explanation!

You check the entire string s for every query In the worst case if the queries aren't subsequences then the entire original string will be traversed q times with makes it around 5e11 somthing.

I failed on sys test too.

And to improve it I guess we could traverse the original string using the next character array we've build rather than traversing every element

on day 2 he makes 2 bets say he makes the following bets

2-a bus 2-b bridge

these are for the transportations of day 3 atleast one of them will be correct on day 3 he makes one bet with one person for the happenings of day 4 and 5

lets say he makes a bets saying day 4 has bus transportation with they person of day 3 then he will make a bet of bridge with the 2 people from day 2 for the transportation of day 4.

so atleast one person is sure to clear day 4 bet in the worst case it will be the person from day 3.

now on day 4 he can make 2 bets so lets consider day 5 now we know that the guy from day 3 has made it to day 5(or else someone from day has already cleared the required on day 4)

if he makes a bet of bus on day 5 with the person from day 3 he will make a bet of bridge with the two people from day 4.

so if its a bus on day 5 the bet with person from day 3 was correct and we are done or else in the worst case its a bridge and the two people from day 4 clear day5 and enter day6

now there are 2 people and a single day so he can make two different bets for that day and win

The run-time is 1999 milliseconds

i think if we use unordered map and only process for numbers less than n it will still work though i am not certain about how collisions work in unordered map

Sadly

Has there always been a penalty for wrong submission on test 1?

There is no standard logic to solve this it is a simple but tricky observation drop the ball outside of the box-limits and it will hit the ground for sure! Thus guaranteeing victory in every round. If you print any number within limits of the box the simulation is then random and it could end up any way, mostly a loss.

Thank you for the explanation!! I understand it now

Right I just assumed it to be log(n) didn't give the continuous division by 2 a lot of thought. Thank you so much for pointing it out.

Auto comment: topic has been updated by jobin491 (previous revision, new revision, compare).

for maximizing you have to use the first operation first irrespective of parity if first operations have been exhausted switch to operation 2. if x is even it is pretty obvious to use the first operation. if x is odd if you use op1 x-> x/2 but if you would have used op2 it would have been x/2 +1 however if you have remaining op1's

(x/2+1)/2 is result of op2 and then op1

(x/2)/2 +1 is the result of op1 and and then op2

i.e. (x/4 +1/2) vs (x/4 +1) thus clearly using op1 first is advantageous for maximization.

For each circle do this: go from y=0 to y=r[i] and for each y calculate the maximum and minimum x that lies within this circle (this takes logn time as i used sqrt ig) and ding this for n circles each inner loop runs r[0]+r[1]+...r[n] times which is m.

Same with mine, can someone tell me if there is a proof for this approach or was i just lucky 310070577

sure say L=38; then the value is a[1]^...a[19] and we know that a[16]=a[17],a[18]=[19]; thus such pairs are cancelled out in case you arrive at an odd number and the answer is XOR of the first n elements in the case where L/2 is even the answer is XOR of first n elements and a[L/2] we continue this to find a[L/2]

yeahh WA on pretest 4 gives the hint that some edge case has been missed lol

well notice that an adjacent pair (even,odd) will have the same value this was the main idea ig cuz then they cancel out each other so just have to look at the first n elements and how many times are they included in the formation of the l-th element i checked this by continuously dividing by 2 until i reach either an odd element or <=n;

missed l<=n for D1 got 5 WA's cuz of that -___-

Aahh got confused with the timing..

as honest as bro could get

Are you sure that works fine for negative numbers say A[i]= -4 and k= 3 according to your ceil function it will be 0 but it should be 1.

or maybe i am wrong

can you help me with F i used multiset to see how many times a index is being worked on (i stored l and r values in different multisets and found the number of elements less than x using lower bound and upper bound) fails on hidden test:(

https://mirror.codeforces.com/contest/1791/submission/282704498

i think yes

When will the ratings be out?