I guess one can actually prepare the same problems for both divisions, just with different variable/time/memory constraints for Div1 and Div2 participants. But this sounds more woe than fun :)

Yes, standard rated round

What is negative rating change?

5th actually, but nevertheless that was a progress =)

13th place = 3 problems :"D

Not this time ! Although Question B had tricky cases to deal. Overall, Questions were easy as compared to regular DIV2s. Happy coding.

You didn't give the contest!

"dum.....dum.....dum.....dum.....dum.....dum.....dum" is low frequency, whereas
"dumdumdumdumdumdumdum" is high frequency =)

that who gets the low rating?

Thanks , also to you

*wish

may your words come true.

If the rating change formula is correct you are telling an impossible event :( Anyway, wish the most of the user a satisfactory rating.

That means basic score for each problem is fixed before the contest (and it decreases during the contest linearly). Dynamic scoring means that basic score for each problem depends on number of accepted solutions.

Actually, I think static scoring simply means that it is not 'dynamic scoring' which is detailed in,

http://codeforces.net/blog/entry/4172

Basically, instead of scores decreasing from a fixed amount, the 'initial scores' themselves would depend on the number of contestants who have managed to solve the problem.

We don't see a lot of dynamic scoring competitions these days but they used to be relatively common about two years ago.

Yes, I know that feeling bro, just as much as I'm hating my cyan colour, good luck today :D

Take your time :D

Makes no difference to your life though ;)

Got hacked with 0 0 0 0 I think. I'm so silly!!!

how to solve it?
i did a long stupid algorithm

I didn't find a simple way to handle special cases and just used brute force to handle all the special case, hope there is no bug :D

I see you passed it,i had same problem,do you have any clue what the test could be ?

Why did I put "Impossible" for that? :(

Via 9fag.com?

aaaaaa?

It wasn't

translation: give me upvote!

Most likely it will be during the next Petrozavodsk Camp

Tasks were nice! (Translation 2 bits away from AC in E). Either way, tasks were really nice :P.

even I thought of that, my whole contest got wasted because of this ......

That is the first and only feeling I had after the end of today's contest.. Lets hope for the best

It takes the lastest submission in case you found bug(ssss), some godlike cases that may not be verified in pretests.

You get -50 points for every resubmission, and only the last submission is taken into account for testing.

your latest submission is considered.

school in august ? no wonder asians are smart haha :D

div2d had so many edge cases... The main can be solved purely using math. As for edge cases, there are (0,0,0,0) (0,1,0,0) (0,0,1,0) (X,0,0,0) (0,0,0,X) where X is a triangular number. You can deduce number of 0's and 1's in since a and d must be triangular, and a+b+c+d must be (n0+n1) choose 2, otherwise "Impossible". The last edge case is when a=0 or d=0, since there can be 1 or 0 of them. But if theres 0 then it reduce to X 0 0 0 and 0 0 0 X case Now you can say that when a=0 then n0=1 and d=0 means n1=1. Now prove that anything else left is always possible to build. :)

although I have stuck with the 3rd case, I can say my idea.

first, you can get number of ones and number of zeros in the string.

where:

1) No. of zeros * (No. of zeros — 1) / 2 = a00

2) No. of ones * (No. of ones — 1) / 2 = a11

You can check some validations using these numbers, a01 ans a11.

No to build your string.

ans = ""
cnt = 0 // number of "01"s 
while(No. of zeros and No. of ones) do 
  if(No. of zeros + cnt <= a01) 
    ans += "0",  cnt += No. of ones, No. of zeros -= 1;
  else ans  += "1", No. of ones -= 1;
end

then you should validate your string and you can do this in O(Length of strnig) by counting how many "01" and "10" subsequences and then check them with a01 and a10.

I implemented this idea but I couldn't to figure this tricky case "0 0 0 0"

sorry for bad English. :)

Let the number of 1's in the string be X.
Let the number of 0's in the string be Y.
Then,
1. the number of 11 subsequences = X choose 2
2. the number of 00 subsequences = Y choose 2
3. the number of 10 subsequences + 01 subsequences = X * Y (one of them is from 1's set other from 0's set)

Assert the above conditions for solution to exist.
Now let the requuired string be B, and let us start from a string A and try to construct B from it, where A =
"11111.. (X times) 0000 (Y times) " — i.e., all 1's followed by 0's.
A has X * Y number of '10' subsequence and 0 number of '01' subsequences. Now, notice if we shift the last 1 (the Xth 1) one position right swapping it with the first 0
=> 1111..( X-1 times ) 01000.. (Y-1 times)
Now, A has X * Y — 1 number of '10' subsequences and 1 number of '01' subsequences.
Keep doing this sort of shifting, you'll eventually be able to arrive at a01 number of subsequences and a10 iff (a01 + a10 == X * Y).

Beware of corner cases like: "0 0 0 0"
"K 0 0 0"
"0 0 0 K" ...

Because partly the testing is conducted during the contest

Because the judge alternates between Div 1 and Div 2.

Isn't it ?

this problem is too difficult.

My O(n) got 1543ms, after my O(nlogn) got TLE on pretests. It's easy to underestimate constant factors.

I feel the same way lol.

Same here. :(

I solved 4 problems but got WA on 2 of them due to stupid corner cases. Pretests were weak. >_<

First, you should notice that a00 and a11 are triangular numbers(and it will give you the values of the number of 0's ans 1's, here you should be careful with a00 = 0, because there could be 0 or 1 zeros, the same for a11). Second, a10 + a01 must be equal to xy, and in fact (you can prove by induction on (x + y) that it's everything you need to construct an string with the conditions you want).

So first of all you have to find how many zeros and ones there will be in total. in order to do that you look at the number of 00 and 11. Say number of 00 is 3 that means that we have 3 zeros in our string because you can choose 3 combinations of size 2 from 3 zeros. So basically if you have n zeros in your string the number of 00 will be n*(n-1)/2 and the same goes with 1's. Though there is something we have to look at, which is when you have 0 of 00's. then maybe there is 1 0 but definitely not 2 because if it was to number of 00 would be 1. So it will be 1 if number of 01 or 10 is more than 0. and same goes for 11's. after you determine the number of 0's and 1's you do the following: you start putting 0's and 1's. if you put a 0 you decrease total 0's. if you put a 1 you decrease total 1's. and if you put a 0 that means you increased number of 01 by the amount of remaining 1's because you will place remaining 1's after that 0 and it will be number of reamining 1's times so same goes for 1's . an algorithm would look like this for that :

	while(zeros >0 || ones >0){
		if(b>=ones){
			printf("0");
			b-=ones;
			zeros--;
		}else if(c>=zeros){
			printf("1");
			c-=zeros;
			ones--;
		}
	}

and there are still some cases. if a,b,c,d=0 then you print 0 or 1. if a b c= 0 but d is not you print only 1's. and vise versa. and if a or d is not in the form of n*(n-1)/2 it is impossible as well.

Pretty sure you can, at least the start of them... (just go to the submission page 20134499 and scroll down)

Your solution for B fails for "0 1000000000 0 0". The testcase for C is too big for me to see.

on problem B a hacker saved me on case n=1 lol

Your profile picture seems appropriate for you :)

Look on the good side, you did not got a WA on main tests.

yes, it took me 20min to figure that out

use printf instead of cout. and in order to make it a little bit faster you can do this int size = s.size(); instead of looking at the size every time in the for loop.

String comparison is O(n), and you do it n times.

if (s < prev) {
	prev = s;
	ok = true;
}

s < prev inside loop, comparing strings is O(len)

String comparison

s.length() is calculated after every condition check...which makes your code square complexity....I made this mistake once

String comparison is costly time-wise, this line to be specific: s < prev. It should be replaced with s[i] < prev[i] as you don't need to compare the whole string everytime as you pass on each letter and can compare them individually.

Here is your code modified, it got accepted. 20135520

No it's not. In the killer testcase your code is comparing a very long string for each character it has, leading to a O(n²) behaviour.

just sort the data....now you need to visit n-1 points. So you have to check for 2 choices — either leave first point or the last point(in the sorted data set) which has 4 ways of doing so. Check my code — 20124041