what is test 61 in DIV2 C/ DIV1 A ?

I tried similar solution. Could you please tell my mistake. Submission

can someone give counter case for pretest 7 of problem D, I tried similar to solution mentioned by others above. Submission

What was your mistake in pretest 7 of problem D ?

payed back more than what i got in last round.

Why 2-pointers is not in the tags for E2 ? submission . EDIT: Now 2-pointer is there.

I started writing down numbers from 1 to 21 and found following : Bob wins for 1,2,3,5,7,8,9,11,13,15,17,19,21 Alice wins for 4,6,10,12,14,16,18,20

For even n, if it's not power of 2, then there is some odd divisor say o>1. Hence n-o is odd and we know result of it . Example : n=22, then 22-11=11 and we know who wins if n is odd and less than 21.

Similar reason you can find for odd numbers > 21.

For even numbers with power of 2, It's always alternate i.e for 8 bob will win, for 16 Alice, for 32 Bob. Here also explain (just subtract divisors and see) in similar way.

Due to induction. For numbers > 9 and not power of 2, you can see that it if it's even then Alice will win else bob. If even number has odd factor, then we can subtract odd factor from it and resultant number will be odd and use answer of previous numbers.

Also in terms of number of solved, E and F seem to be of same difficulty.

How to solve F?

I thought of following approach but could not implement, could someone tell if how to implement if their solution was similar :

stories (short or big) in problems are good if they can somehow help in imagining. In A,B,C,D if problems were without stories then it would have been good.

explaining the sample test cases in bottom would have avoided lot of confusions.

You should have checked example ??? in test case .

which line you were confused in ?

It might not be always possible but can we have important rounds like TCO on weekends. SRM usually happen regularly so it's fine if they occur on working days.

+1. Frequency of codeforces contest has decreased compared to month back.

could someone provide counter case for this submission of problem c. Got 6 WA on this problem.

It does feels bad when i lose rating but i don't skip if i don't get any solution for 40 minutes (happened in this contest). As long as we don't cross our highest rating, any rating below it will be temporary.

You could have solved A later and maybe then you would have got the idea. I usually solve problems in order, but I was not sure of my solution to A (though it was right), then moved to B which again I failed to solve. I opened C1,C2 and was able to solve them fast. Then returned to A and then to B.

In A i sorted the elements first say for example 1 2 3 4 5 6 and arranged them like 1 6 2 5 3 4.

It was more about how fast you come to solution and not how fast you type. Code for first 4 tasks were short.

Thanks. Can any one provide intuition or proof why it will be correct (grouping similar characters together) ?

How to solve it ? I summed the position at which each character is occurring and then put those characters whose sum is lowest in last.

yes , tbh i found it easier than B. In C you just need to remove most negative element when overall sum becomes less than 0 . Let's hope it passes pretest .

every random logic passed first pretest on problem D but failed on second. What was story behind putting "ok You are epic!" in pretest 1 of D ?

misof thanks for contest.I think problem statement could have been made shorter.Avoiding terms like magic orb, a magic scroll and a magic twin blade and just simply using rock, paper and scissors would have shorten the statement.

Is there any idea behind using long problem statements in first problem ? I usually see this on topcoder.

it really sucks when your performance is ruined by a silly thing like this.

what made you think beforehand that you need to print "TIE" when none wins ? It means you didn't read the question properly which is itself silly.

many times people try to make hypothesis from samples(think in direction provided by samples) and some times it turns out to be the solution.

From today's problem A samples we can make hypothesis that answer would be one less than some power of 2. Also after seeing the samples of problem B2 i started to think in direction that Alice will win in most of the cases (though i messed up with corner cases).

yeah thanks :)

Fight hard till end. Other option would be still valid after contest

C was easier than both B1 and B2. Probably C should have been B .

Could some one please provide small counter test case to my submission of problem D. Test case 44 is very big. dp[i][j] means minimum answer to accommodate all 1's till position $$$i$$$ in such a way that they remain within $$$1$$$ and $$$j$$$.

UPD : I found the mistake. This was counter test case : 10 0 1 0 0 1 1 1 1 0 0

Why "otherwise" was not clear for you ?

Nice prove. thanks. Can you share your thought process for solving this ? Like how you approached this problem before coming to final solution ?

How to justify this solution i.e how to prove that difference in height won't exceed x ?

How to solve B and C ?

could you please elaborate on how to do this. I used two addition arrays of size $$$n$$$ to store answer for subarrays of size $$$i-2$$$ and $$$i-1$$$. This is because we need to have answer for subarray of size $$$i-2$$$ if we are going to calculate answer for subarray of size $$$i$$$.

I will be thankful if someone makes video editorial of E. Why everyone posts editorial of problems solved by 1000's of people.

How to solve C ? I solved using factorization in O(nsqrt(n)) but it seems lot of people have solved in some different way.

In problem C could someone help in justifying the second construction ? How to prove that it will always work ?

could anyone who solved problem D using segment tree tell their solution ?

you don't get bored from commenting in every blog ?

thanks VTifand for counter case.

thanks spookywooky.Yes it was that mistake. I corrected it.

Could someone please provide me counter case for my submission of problem D .Test case 3 is very long.

Monogon could you please help here why we are splitting when minimum to left of $$$i$$$ is greater than maximum of right to $$$i$$$. I understand that finding $$$2$$$ decreasing subsequence directly might not give optimal solution . So how we justify that splitting it like that will help us find the optimal solution ?

According to the editorial two subsequences will be unique if we split in that way. How to prove it ?

In problem DIV2 F (flip the cards) , could someone explain the intuition behind splitting the array into segments based on condition that minimum to left of $$$i$$$ is greater than maximum of right to $$$i$$$. I didn't get why we are doing this.

What i understood is that it's necessary we need to split [f(1),f(2),f(3),...,f(n)] into 2 decreasing subsequences (where one can also be empty). If we minimize length of one of the subsequence then number of flips would be minimized . But how we splitting is helping us here ?

Could some one please help in dynamic programming part of problem E ? How we are finding minimum number of vertices required to get time less than or equal to X ?

What are odd steps and even steps in problem F ?

UPD : Understood after reading this blog

How to solve C ?

Could you please explain why it was a bad problem ?

In DIV2 A and B, what arguments or justification you used while reaching to the solution ? Like what was your lane of thought .

I have taken arbitrary matrix , value xij can be 0 or 1 . Just we know some of those value (last three columns and x12) . How it's invalid ? I don't see any "loop" word in problem. If you mean two x41 , i corrected it , xij are just notation to denote a cell .

In Problem D Suppose we have $$$5*5$$$ matrix with values :

x11 x12 x13 x14 x15
x21 x22 x23 x24 x25
x31 x32 x33 x34 x35
x41 x42 x43 x44 x45
x51 x52 x53 x54 x55

Suppose last three columns have known values and suppose in first two column we know only the value of x12 . Thus total $$$3*5+1 = 16 = (5-1)^2$$$ values are known . Now except $$$x11$$$ how other values are induced ?

Procedure was correct,I unnecessary printer $$$0$$$ when $$$a=0$$$. Most people have similar solution .

We can prove that it won't over count .valid arrangement will have unique path (If we visualize the recursion as tree) reaching to it.

Thanks a lot Nots0fast ! . I thought that answer in that case would be 0 but it will be 1.

How to solve D ? I am getting WA in 5 cases . submission

My approach was to brute forces all possible arrangements . In each function call i traversed the matrix row wise and i called next function as soon as i can fill some 2*1,1*2 or 1*1 tile. Could someone please provide a counter case ?

Why time limit of problem D is 2 seconds ? should have been 4 seconds since it's tagged as brute force. I changed long long to int after contest and it passed in 1996 ms . I think it will fails system test . What was intended time complexity ? submission

I don't think blog should be downvoted . I don't see how problem setters are responsible for round being unrated . Infact it's sad for them too , their round having good problems got unrated.

largest $$$n$$$ value test case in problem with answer "NO" was $$$1572$$$ . $$$n$$$ in worst case could be $$$2*10^5$$$ . So at an average numbers are around $$$12.5$$$ distance apart (for worst case $$$n$$$) which increases difficulty of finding such sequence satisfying the constraint.

We can construct an increasing sequence such that each element is strictly greater than sum of previous numbers . But that will increase exponentially.

I did in similar way as you have mentioned (instead of dijkstra i used bfs since graph is tree).

You can put all data in matrix inside a vector and then sort the vector . Take pair having smallest distance , if they are already connected ignore them else they must have direct edge between them .

B was easier to solve and code compared to A in DIV 2

double has more number of bits to keep precision and thus more time required for input i think . Also it's bad idea to take integer type input as double because there can be loss of precision .

subarray which is either strictly increasing or strictly decreasing .For example take array 2 4 6 5 3 8 7 4 3 . Here 2 4 6 , 8 7 4 3 are some of the monotone segments . 8 7 4 3 is longest monotone segment.

More number of people would have solved Div2 D/ Div1 B if clear problem statement was made in starting itself .

How ?

Providing the explanation in problem D before hand would have saved a lot of time and maybe that could have been utilized in writing better solution.

I am not sure if this correct approach , I think answer will be always $$$1$$$ or $$$0$$$ .Answer will be $$$1$$$ only when there exist some index $$$i$$$ such that array is decreasing in both right and left direction of index $$$i$$$ and size of the maximum decreasing sub array in both directions are equal,even and maximum in the whole array.

Update this approach is correct : 109629126

separate the x axis and y axis values and take the absolute values only . After that sort both x-axis and y-axis arrays . Now we can pair same index values in both arrays .

So that modified Dijkstra is minimum spanning tree problem in this case which i mentioned in my first comment.

In the blog it's mentioned "Dijkstra" , if we follow the Dijkstra algorithm won't be the path 1->4 will chosen because total length is 2 , whereas in path 1->2->3->4 total length is 3 ?

But if we use prims algorithm , edges 1->2,2->3,3->4 will be chosen because that is the minimum spanning tree in this case . Also that is the solution to the problem posted in blog .

Dijkstra won't work directly here . Take following undirected graph , n=4 , m=4 and edges,weight = {1,2,1},{2,3,1},{3,4,1},{1,4,2} . Dijkstra would give the path 1->4 because it's length is 2 whereas path for solution will be 1->2->3->4 because maximum edge length here is 1.

So we can use prim's algorithms which is just slightly different from Dijkstra. Following is proof why prim's algorithm will find out solution to your problem (You need to read prims algorithm first to understand the proof) :

Suppose we need to reach from node $$$1$$$ to node $$$n$$$ . Suppose prims algorithm provides path say $$$A$$$ and we argue there exist another path $$$B$$$ in which maximum weight edge has less value compared to that in $$$A$$$.

But then if you see prims algorithm then all weights which are smaller will be chosen first i.e all edges in path $$$B$$$ will be chosen before the maximum weight edge in path $$$A$$$.Hence contradiction .

It's not sad . If everyone gets positive rating then it won't remain fun and competitive.

Could someone please tell why my submission in problem D giving TLE , I have used same idea as given in editorial . 109312305 .

Edit : I figured out , i was making mistake in calculating the sieve.

Thanks for reminding bitmask idea, I brute forced using recursive functions which was more messy to code.

What you are saying is necessary but not sufficient.

For example take (in binary) u = 001001001 and v = 010000011 , clearly v>u and number of bits in v is equal to number of bits in u , but you cannot reach v from u.

We can reach v only if number of bits occurred till position $$$i$$$ in v is less than or equal to number of bits occurred till position $$$i$$$ in u and v>=u (sufficient condition).

One of the way we can approach the proof is that we can shift the bits of u any distance toward left but above condition must hold because whenever we add the subset it increases the u and shifts it's bits toward left by one and may cause some of bits disappear because of adding (they become carry).

00001100011 + 00000000011 = 00001100110 . Here we can see first two bits shifted toward left by distance 1.

00001100011 + 00000000001 = 00001100100 , here we can see that second bit shifted toward 3rd position and first bit disappeared .

I didn't solved but i thought in following way : We can calculate the size of tree and if it's equal to some Fibonacci number $$$F_{n+2} = F_{n+1} + F_n$$$ then one it's sub tree must have size either $$$F_{n+1}$$$ or $$$F_n$$$ . Thus we can divide the problem into that subtree and original tree with that subtree removed.

Since Fibonacci series is exponential , i think it will take $$$nlogn$$$ or $$$n(logn)^2$$$ depending on how fast we find that subtree.

Also wouldn't solution fail (because horizontal and vertical were swapped) if it follows original statement ? I guess problem statement was made bit different after testing round.

Thanks , I probably over killed.

If there exists index $$$i$$$ such that a[i]>a[i-1] then answer will exist else not .

You should try asking in comment section of problem (though i don't know how fast they reply).

In problem Sed Max , I solved by finding left maximum and right maximum for each index (so that i can traverse through second maximum faster) , I break from the loop when i found second maximum greater or equal to a[i].

It passed (submission) the test cases , but how to prove that it won't be quadratic in worse case ? Also i noticed that answer is always around $$$O(n)$$$ .

How to implement the simulation for calculating our score ? I thought of few AI algorithms but to move on better state it is required to calculate the score of current and new state.

I implemented the solution in editorial in following way (I will the prove it's complexity) :

We can notice that we can make atmost two changes to the first array so that it becomes original array and all array differ from it in atmost $$$2$$$ positions.

Now we compare first array to all other arrays and we find another array such that it differs in more than $$$2$$$ positions then we must modify atleast one position in first array . Number of ways we can modify one position in first array is $$$4$$$ in worst case because as editorial says , the case with more than $$$4$$$ difference will not have answer.

After the modification in first array , we again compare it with all other arrays and if we find some array differing in more than $$$2$$$ positions we must again modify it in one position. We will consider all possibility and maximum possibilities here will be also $$$4$$$.

Thus it's like calling compare function recursively after modification , also in particular recursive function , we won't compare further once we found array with difference greater than $$$2$$$.

Number of times we will call this recursive function is atmost $$$3$$$ because we can make atmost $$$2$$$ changes.

So suppose in first function call in worst case we found the last array which differs in greater than $$$2$$$ position then number of operations in first function call would be $$$O(n*m)$$$.

Number of operations related to second function call will be $$$O(4*n*m)$$$ because previous function will call this function atmost $$$4$$$ times.

Number of operations related to third function call will be $$$O(4*(4*n*m))$$$ because number of times previous function will call this function will $$$16$$$.

Thus total operations will be $$$O(21*n*m)$$$. The key point which saves time complexity from being $$$O((n*m)^2)$$$ is that in particular instance of function call , we don't compare with further arrays once we find the array which differs in greater than $$$2$$$ positions with first array.

submission related to above reasoning.

Respect for Antontrygub ,Due to his coordination work he cannot participate in so many rated rounds.

some people have used randomized solution for problem E . Could someone please explain how to solve problem E using that.

Doubt in problem E editorial :

We can ignore each other array that differ with the first array in no more than 2 positions

Take following input : n=3 m=3 , 1 2 3 , 4 5 6 , 3 3 7

We can see that 3 5 3 will work .

Now if input was : n=4 m=3 , 1 2 3 , 4 5 6 , 3 3 7 , 1 3 7

Then according to editorial 3 5 3 should work as answer because we ignore the 4th array . But then 3 5 3 differs from fourth array at 3 positions.

actually this problem is also in C++ . I submitted by using ceil function and converting denominator to floating point by multiplying with 1.0 but it gave WA mostly due to precision issue.

we can do $$$(num+den-1)/den$$$ for ceil.

Notice the condition : $$$1≤p_1 \lt p_2 \lt … \lt p_m≤n$$$ .

yeah website is working faster without any errors while opening the problem or submitting. Good work CodeChef !

But i think number of participants are less compared to cook-off and lunchtime (people in all 3 divisions combined).

can you please tell why number of different sequences $$$A$$$ such that $$$A_i \lt =x$$$ is $$$x^n - (x-1)^n$$$ . Shouldn't it be just $$$x^n$$$.

C was easy than B but solution of B was on internet so lot of people solved it very quickly .

It was one of the worst problemset that I have ever seen.

If you had participated in last ABC , you will appreciate this round. This contest is for beginners so easy problems does make sense.

value of $$$x$$$ in that case will be not $$$1$$$ , it will be always $$$x$$$ . for $$$x = 5 , m = 7$$$ answer will be $$$1$$$ , for $$$x = 5 , m = 4$$$ answer will be $$$0$$$.

Thus if $$$x$$$ has length $$$1$$$ , it will remain always $$$x$$$ for any base . Hence if $$$M \gt =x$$$ answer will be $$$0$$$ else answer will be $$$1$$$.

first i tried to handle the overflow with signed long long but result can have undefined in that case.

Later i fixed that , but for case where $$$x$$$ has length equal to 1, i wrote :

if(SZ(s)==1)
{
	n = stoi(s);

	if(n>=val)  //It should have been n<=val
	 ans=1;
}

were most solutions failing in D due to overflow / precision issues ? I thought we can binary search but gave wrong answer in 13 cases even after handling the overflow. submission

UPD : it worked after handling the case where x has length 1 . I handled the case but incorrectly , probably overflow took away all the focus.

unordered map worst case complexity is $$$O(n*n)$$$ whereas for map it's $$$O(logn)$$$. This is because unordered map is based on hashing where multiple numbers can be hashed to same value forming large chains giving worse case search complexity $$$O(n)$$$.