I've told him it personally.

haha, MikeMirzayanov is himself.

I'll try to implement it before the round. Stay tuned!

I've implemented it. You can check how it works on the ranklist of Codeforces Round 494 (Div. 3).

I am a simple man I see a "I am a simple man" reference I "upvote".

As awesome as TheOneYouWant.

no,it is his contest <3

no but MikeMirzayanov is father of codeforces

Try 317878994 The answer is 5, it worked for me :)

Let s1[l..r] be (number of elements > m) — (number of elements < m) and s2[l..r] be the number of occurences of m.

You can prove that in order for a range to be valid, 1-s2[l..r]<=s1[l..r]<=s2[l..r].

If you expand s1/2[l..r] into s1/2[0..r]-s1/2[0..l-1], the problem becomes 2D range sum queries with point updates.

I solved it by counting number of arrays having median>=m and subtracting from those, the count of arrays having median>=m+1.

To count number of arrays having median>=X, we can replace all elements < X by -1 and >=X by +1 and count the number of subarrays having a non-negative sum (and taking special case of when the length of the array is even, in that case the sum must be positive), both of which are kind of standard problems.

I counted the number of subarrays that don't have the median equal to m, and subtracted that from n*(n+1)/2. There are two cases:

1) L + ZEROS < R

2) L >= R + ZEROS

L: left part (< m), R: right part (>m), ZEROS = number of elements equal to m.

In the first case, I change the values <= m to -1, others to +1 and find subarrays with strictly positive sum.

In the second case, I change values < m to +1, others to -1, and find the subarrays with non-negative sum.

let's say a are numbers such that a%3==1 and b are numbers such that b%3==2

if count(a)==3 and count(b)==0 or count(b)==3 and count(a)==0 you have to split.

{ Edit : the complete approach is mentioned below }

Try 112, the answer is 1

It must be greedy then? I got to the same test using greedy approach.

Let dp[i]=answer for prefix of size i. We can see that dp is non-decreasing. And let sum[i] be the sum of prefix modulo 3, and x[i] be the last j then sum[j]=i. Then dp[i]=max(dp[i-1], 1 + dp[x[sum[i]]], sum[i] == 0)

I solved D on the fact that given a 3 digit number in which no digit is divisible by 3, there is at exactly 1 segment whose sum is divisible by 3.

D is just greedy

In D you can observe, that every (at least) 3-elements-long subsequence will have correct combination. I swapped all the numbers a for numbers a%3 and then started greedy algorithm. For every i have sum of elements (i), (i + i-1), (i + i-1 + i-2), but first I check, whether any of those numbers was taken previously. For example I store a sum from range (i) (just a single element) and then check if element indexed (i-1) was taken. If it was I don't check further, if it wasn't I can add that in my sum. If my sum%3 == 0, then I mark element i as taken and add +1 to the answer.

If I checked only one number, correct answer would only occur if it was == 0(mod 3). If I checked only two numbers, then I would have those combinations of modulo: (0, 0), (1, 0), (0, 1), (1, 1), (1, 2), (2, 1), (2, 2). As you can see only three of these are correct. If I checked three numbers then there would always occur at least one correct subsequence.

I solved D by dp

Overflow. Add more powers of 2 and it would work.

XD it's something like 112

If you are currently considering a particular number in the array, there are only log(n) other numbers which, if added to the number being considered, give a power of 2. So we can use hash maps to store numbers and so complexity is O(n*log(2*1e9))

I don't solve D because I wrote if (!(digit + temp.front()) % 3), notif (!((digit + temp.front()) % 3)) or simple if ((digit + temp.front()) % 3 == 0). And... I don't find the mistake.

hint: if x, y, z are integers, then at least one of x, y, z, x + y, y + z, and x + y + z is divisible by 3

Very straight away approach : Iterate over the array , if s[i] is divisible by 3 , increment counter and make num =0 , else store it in num . Each time check if num is divisible by 3 , and if its length crosses "3" , it** must** have already been divisible by 3 => Clear num and increase counter.

	while(slen>0 && s.equals(t)!=true)
		{
		    count+=2;
		    s=s.substring(1);
		    t=t.substring(1);
		    slen-=1;
		}

You create new string every time. It is rather suboptimal.

Do you even read that problem? They ask different thing to do. You waste my time.

Enumerate each number, enumerate the power of 2, and subtract the number by 2 power, to see if the result is in the original set.

There a only 31 powers of two which are less than 2e9, so you can brute-forces over those powers.

I had the same approach. Couldn't pass it

I too did the same . But there is no need to store segments of size more than 3 , as explained in above comments . So , its just wastage of memory....

Note that, in any sequence of numbers that satisfy the condition, m should be included. Also, in total we only care that the number of numbers greater than m minus the number of numbers less than m is 0 or 1. Now, just find for each indez the greater-lesser factor, separately, for indices before the value m and after the value m. Now, just compute using the condition

A counter case: 382845 The answer should be 3 but it prints 2.

0^2 ?

Look at this: http://codeforces.com/contest/1005/submission/40136032

Mp[y] will insert y in map with default value 0.While Mp.find(x) return iterator to the key x without inserting it. Try this

for(i = 0;i <  = 10000000: i +  + ){if(Mp[i] =  = 0){};}

And check the memory used.

I don't think you can clear a set/list while iterating through it. So if you remove s.clear() from line 39 (from the first submission you linked) and only clear it if p is set to 1 after the loop, it should work without crashing.

I have the same issue and after the contest I have submitted a a solution with unorderedmap and it is AC now while the solution with map failed in test 7 although it has passed this test before

Bro same happened to me.

Orz Akfun!

Akfun is our red_sun!

Orz Akfun!

Akfun is our red_sun!

Orz AKfun!

AKfun is our red_sun!

(human is fundamentally repeater

Orz AKfun!

AKfun is our red_sun!

Orz Akfun! Akfun is our red_sun!

There aren't so many cases: 1) one of the numbers x, y and z is divisible by 3. 2) all of them aren't divisible by 3 — the variants for the rests of division are: (x % 3 = 1, y % 3 = 2) or (x % 3 = 2, y % 3 = 1) — then (x + y) % 3 = 0.

Other cases: 111, 112, 221, 222. that's all.

It creates O(n²) test for Arrays.sort in Java. Only sorting of primitive arrays can be exploited — sorting Integer[] or Object[] is fine. All the complications are needed so that generator doesn't require O(n²) time itself.

For every element you need to find , whether there is another number which on summing gives a number of the form 2^d (i.e.,a number which is a power of 2 ) . So , first create an array which stores all the powers of 2 till 10^9 , then for every element , iterate over this array (powers of 2) and take the difference between both and check whether this difference exits in your original array excluding the current index (You can do this using a map/binary_search). If there is no such element increment your count value and finally print it !

In your solution the problem is with int t = log(i) / log(2). log() and power() works with double. Just remove this string and change to return i==pow(2,log(i) / log(2)). The type will be double and all will be OK.