Yup, this one.

D had nothing to do with the elements' range.

D was fun to solve. I saw a tougher version of E somewhere else, maybe in a previous CF contest.

Smart way to earn a CNIL T-shirt and thanks for the link

There's a neat observation here that you missed.

So, in general, it takes you pow(2, K) operations to take you from pow(2, K) to pow(2, K-1).

And any number is nothing but the summation of powers of 2.

So, for 13 which is 1101 it'll take you Ans(1) + Ans(4) + Ans(8) operations to reach 0 :)

Use a multiset or a priority queue. Insert and removeMin are straightforward now.

For getMin, keep on removing the smallest element and keep on incrementing the count until the removed element is smaller than the getMin output given.

If now, the multiset is empty or the smallest element in it is greater than the getMin output given increase count by 1 (it accounts for adding the getMin output given by an insert operation).

I guess people are making fake ids just to hack those submissions afterwards. Deliberately a stupid if case is added to be hacked afterwards XD.

89940459

The hacked guy likes 78788 a lot I guess. One more of his solutions from another contest using his fake id Noob_is_back got hacked. See this 87193319 and you'll find 78788 again in the code. The hackers are still grey :)

Yes

Yup, I verified on my local machine. This code actually outputs YES.

AlFlen Can you please have a look at this.

Would this work for F?.

First, co-ordinate compress the segments. After that, sort these by ending indices. Maintain a dp array where dp[i] = size of optimal subset where all segments have ending indices <= i. Consider the Kth segment to be the last segment included in our optimal subset and it's starting and ending indices to be L and R respectively.

Loop through the points from R->0 on the co-ordinate axis, then, dp[R] = max(dp[R], number of segments inside range [L,R] + dp[L-1]);

The maximum of dp[i] would be our answer. I think this is the same idea as the editorial, couldn't understand that one exactly, so came up with this.

Note: The kth segment is considered to be inside [L,R].

.....where ai is the (index) number of (the) subsequence, the i-th character of s belongs to.

Even if it wasn't clear to you, it was kinda obvious :)

Cheating and still Cyan :) Stop cheating, you'll love it when you next become Expert.

Yup, The deciding parameter for the series is actually the second number i.e, sum + i*i.

I get it now. Thanks.

Dsxv, could you please clear this for me.

q.push({(cur*10 + i)%mod , sum + i*i}) ;

Won't taking mod here change the number itself. It'll yield the wrong number when used further, right?

For instance, for x=1, we get the first 15 numbers as this:

Compile it with: g++ filename.txt -o a

Execute and redirect the output with: ./a > output.txt

DeadlyCritic, In this problem, ans_v needs to be stored modulo M. But, particularly in this task, M can be any integer in the range [2,10⁹]. It would've been trivial if M would've been any prime integer, but how do you calculate the inverse of dp_v+1 now?

UPD: I understand it now. Thanks.

For anyone who'd like to see how exactly prefix products help us here can view this submission.

V-Subtree submission

I take sufficient time for Problem A. The objective is not to mess up at the beginning even if it consumes 5-10 mins. Don't let anxiety build-up at the very start. I usually solve Bs fast.

Moving on to Cs and Ds. For them, I discard lengthy cumbersome solutions that come to my mind. I take 10-15 mins more for Ds especially to arrive at an elegant solution. This does 2 things for me.

1. I gain confidence after I find an elegant solution to a tricky problem.
2. It saves me from long unnecessary sessions of bug fixing most of the time and at least for me, I don't even look at Es after that.
3. Switch between problems. Many of us(including me) don't do this. But it helps a lot.

For someone at your level of competency, ignoring Es and Fs is not what you want.

Can you help me out. Nothing happens when I fill in my codeforces handle and press Enter.

I tried it and got a warning. Thanks for this :)

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

Yeah, I framed the sentence incorrectly. Maybe I shoud rephrase it.

Yes, I mentioned that on being empty it returns an unsigned 0. No doubt, it returns an unsigned int always.

Updating the topic. A better way indeed!

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

While removing a[i], a[i+1] and a[j] shouldn't we check if dp[i+2][j-1] == j-i-2. That is, all elements from [i+2,j-1] should get removed if we want to club i,i+1 and j together.

Moreover, while considering dp[i][j], we should iterate over intervals of length 3,

[k,k+2] for k>=i && k+2<=j signifying that we try to remove them first.

Please, can anybody confirm the correctness of these two claims?

You don't have to worry about them. Also, what sense does it make to give your blog a MiFaFaOvO VS tourist title?

I ran and got AC with your code by replacing a=a+b with a+=b. The runtime difference is strikingly large. The AC submission ran for just 124ms

Good sorting techniques are O(nlogn). There's no sorting technique with a complexity of O(logn).

You sort all the numbers for every iteration of the for loop so your complexity turns out to be O(n*nlogn).

Use heaps to do what you intend to do. Sorting for every iteration will time out here.

Here's my Stackoverflow answer for this. See here... You may add 26 more nodes to incorporate capital English characters as well...

You may use fenwick trees. Initialize the fenwick tree array, say fen with 0s. Keep on updating the tree with 1s for each index of query no. i in the given array for 1<=i<=q.

To check if a smaller number appears between two ends, say l and r, compute diff = fen[r]-fen[l]. If diff > 0, you have a smaller number in between.

This is pretty much the idea.

Interested! Add me.

If n would have been small the problem could have been easily solved by linear regression in O(n) instead of finding a pattern. Just maintain a boolean array arr to donate winning or losing at that index. arr[0] = false i.e. loose arr[1]=true arr[2]=true

for i = 3 to n 
if arr[i-1] and arr[i-2] and arr[i-k] are true, then only arr[i]=false otherwise its true;

just output arr[n] now.

Thanks for the explanation! I get it now

I think one person cannot be in more than one component as if he's in more than one component those components cannot be disjoint as he'll be friends with people from both components. I'm still not very clear about problem C. Can somebody explain the solution once.