Thank you so much! Fixed =)

Also the second one where vovuh is the problemsetter, thank you

Actually, programmers often count from zero. Just a joke :)

Looks like you don't know the CF rules yet.

Just because it's unrated for you, doesn't mean you can't participate

Thank you for correction, it's fixed now

In fact, I think the difficulties were just about right, nice to have a bit more of a difficulty gradient than what we've seen before

div 2 is rated for > 1600 and the problem is pretty hard and not too easy and for div 3 is rated for under 1600 and the problem pretty easy not too hard (you can check the past contest and learn from it)

for full explanation -> http://codeforces.net/blog/entry/59228 Meow !

Div 2 Rated for -infinity < Rating < 2100.

Div 3 Rated for -inifity < Rating <1600

Div 2 got some problems easy, some medium and some hard.

But to help improve the newbies and others learn, CF invented Div3.

Div 3 will contains majorly problems of easy and few medium difficulty.

High Ratings to EveryOne !!

144 is a lot ...

Congratulations!!!

Yes

May be not.

As it's rated for only Div-3 ** trusted participants**. You must:

• take part in at least two rated rounds (and solve at least one problem in each of them),

• do not have a point of 1900 or higher in the rating.

N.B.: Read the blog properly.

It's an ICPC style contest. All problems have equal weightage.

you won't i bet

"If the problems in this round are too easy or too hard, then we will adjust the difficulties in the next Div. 3 rounds."

Also I think that's good. It differentiates contestants more, than everyone solving ABCDEF and rating only by solve times.

That's standard ACM rules. I think it's fine because it encourages people to write correct code rather than fast code :)

Well the numbers you print represent the coordinates

find lastest 0, 2, 5, 7 in given integer. then we know how many swaps we need to make 00, 25, 50, 75 at the end of integer.

but, you have to consider 0 being at the frontmost number of integer, which is a point i made a mistake.

For example, if we are considering how many swaps we need to make 25 at the end of integer, and if 2 is the frontmost number of integer (before swapping), and if k 0s continue behind 2, (i mean, 200000235234 has five 0s behind 2, k=5), you need to swap k times more. So you can just add k at the answer.

Solution for E: for each case of 00, 25, 50, 75: find the last digit of the case (_0 or _5) in the given string at the rightmost position and swap it to the end (ans += swap distance), then find the second last digit of the case (0_, 2_, 5_ or 7_) in the string at the rightmost position and swap it to the second-last position (ans += swap dist). Then try to swap starting zeroes (if any) with a non-zero digit (which must be at least third-last) (again: ans += swap distance). If the final string is a correct number then consider the 'ans' as a candidate for the shortest answer. Solution with regexes, Perl: 38862670.

Yup, but I kept getting WA

Yup, the maximum size of subset is either 1, 2 or 3 :)

Feels bad when you figure it out right after the contest (:

There are only 3 possible options:

1) Just choose any one to get a set of size 1.

2) Just choose any pair such that S = {x, x + 2^d} for some x in the array, and some d such that x + 2^d belongs to the array. It works trivially.

3) Choose, if possible, for any element x in the array, the set S = {x, x + 2^d, x + 2^d + 1} since it's the only choice to maximize the size (It's not possible to add another one with difference 2^{d+2} since 2^{d+2}-2^{d} is a multiple of 3 and also consider that it also shows that is not optimal to choose different d's as pairwise difference), remember that all those elements need to be in the array.

One can get all the information needed by mapping values to indices and just checking for a not null index in each try. Woof!

I just solved A & C.**T_T**。My B problem failed 8 times.

Every time you check in map you create a new entry, instead use .find(), it doesn't affect the map size.

Idk. I have passed with in 2.5s.

I got WA in same test case than sorted it and got AC till now

I thought it was simple dp?

I mean just dp without using any others data structures

for(int i = n-1; i>=0; --i)
	{
		if(i and s[i-1].find(s[i]) == std::string::npos){
			cout<<"NO";
			return 0;
		}
	}

I suppose last i is zero. And s[i-1] goes to -1.

C++ sort requires strict weak ordering. for more, https://stackoverflow.com/questions/32263560/errorinvalid-comparator-when-sorting-using-custom-comparison-function

23 was the first one with a 2 digit input (I was using python and got a runtime error when checking for the leading 0 afterwards).

Assume x < y < z satisfy that y - x = 2^a, z - y = 2^b and z - x = 2^c. Then 2^a + 2^b = 2^c. Notice that c > max(a, b), so 2^max(a, b) divides 2^c, and therefore it divides 2^a + 2^b, so it must also divide 2^min(a, b), implying that a = b.

Then any three number subset satisfying the condition is an arithmetic progression. Therefore if w < x < y < z have all differences powers of two they must all be in arithmetic progression. This is impossible because then z - w = 3(x - w) and z - w isn't a power of two as it's divisible by 3.

assume there are four integers a<b<c<d satisfying the condition. let b-a=2^k, c-b=2^l.

c-a=2^k + 2^l must be a power of two, thus k=l.

c-b=2^k.

similary, d-c=2^k

then, d-a=3*2^k, must be a power of two, but is not.

So, 1<=m<=3

try proving with contradiction, what if n==4? (show that it cannot happen by using subtraction of bit pattern of numbers).

Suppose we already have the sequence a[1],a[2],...,a[k]. It is clear that it must be (a[k]-a[k-1]) = (a[k-2] — a[k-3]) = ... = (a[2] — a[1]) = 2^d, d > 0. Try it on 3 numbers, suppose we have a sequence a1,a2,a3 and a2 — a1 = 2^a, a3 — a2 = 2^b, with a <= b. Then a3 — a1 = 2^a + 2^b = 2^(b-a) * (2^a + 1), which is a power of two only in case when a = b. So the sequence should be like k,k+2^d,k+2^d+2^d and so on. Consider an example now with four numbers in sequence, a1,a2,a3 and a4. (a2 — a1) = (a3 — a2) = (a4 — a3) = 2 ^ d Then a4 — a1 = 3*2^d which is not power of 2. The same goes for m > 4.

50267 -> 52067 -> 25067 -> 20567 -> 20657 -> 20675

Damnn I too kept getting WA there. I couldn't come up with a test cases like this. The point is in 50267, you want to get the 5 to the right .In doing so your intermediate number is 05267 which has a leading 0 and thus isn't accepted. You need to do another swap — (0,1) which will make all the intermediate numbers not have the leading 0.

This reminds me of

This statement is false.

nice joke, expecting failed on test 11.

Um_nik not just you makes fun :)

because they know they will soon be hacked by reds or etc..

Or they would anyway fail the main tests

That's really strange..

I used printf("%lld", ~) and get AC

Well you not print any solution, look carefully~ Just try it to run locally

That wasn't your mistake — it's just a slightly confusing error message. Your code outputs 0 for that test (as 42 isn't a power of 2) without a second line which causes the error message seen.

While you reading the input get the sum of the numbers from the current array. Every time check if the current sum has been encountered before. Now traverse the array once more and map this value (sum — a[i]) with arrays index, and its position in the array. Check out the code: http://codeforces.net/contest/988/submission/38843860

For each set if elements, first calculate sum of entire set. Then calculate difference matrix by subtracting each element from sum. Use a global map(common for all the sets) for hashing and storing indexes, and check whether each difference element was obtained earlier or not. If yes, you have found common sum producing elements in the 2 sets!

Let A = C + 2^a, B = C + 2^b, A ≥ B.

According to the problem, A - B = 2^a - 2^b = 2^x should hold.

Divide each side by 2^b. The equation would be 2^a - b - 1 = 2^x - b.

1) If x - b = 0, then 2^a - b - 1 = 1 -> 2^a - b = 2 -> a - b = 1 -> a = b + 1

2) If x - b ≠ 0, contradiction since left side is odd and right side is even.

So there are at most 3 which is C, C + 2^a, C + 2^a + 1

IMHO, this kind of problem is little challenging for div3 but worthy at the same time.

Try submitting it using the C++17 Diagnostic compiler, it might help in debugging.

I had the exact same issue. The error is in the comparator.

One of the requirements for a comparator is that

If comp(a,b)==true then comp(b,a)==false

One way to fix it is to return false if a == b before you check if a is in b.

http://codeforces.net/blog/entry/59770?#comment-434966

For your case,

bool comp(string l, string r){
	return l.length() < r.length();
}

return l.length() <= r.length(); — is not right. return l.length() < r.length(); — is right.

Try sorting using a strict ordering, i.e, instead of sorting on the basis of '<=' sort on the basis of '<' or '>'.

More info: http://codeforces.net/blog/entry/59770?#comment-434986

O(40*n)

Nlog(10⁹)log(N) passes in time.

Click on any solution (from the standings, the status tab, etc), you should see a hacking option

You can navigate to a submission from the standings page, and you should see a button that says "hack it" above their solution.

You can only swap adjacent indices.

I think it's anti-hashmap test(I guess someone intentionally generated such test).

idiot