I could get addicted...

Which would be kind of a good thing, if you asked me!

With a few more problemsetters, why not??

It would be awesome <3 <3

That would be great. Everyday codeforces.

Решения будут тестироваться на претестах, но писать будет "Полное решение", если решение пройдет на претестах

Будет тестироваться на всех тестах, заготовленных авторами. Учитывая их качество, их и претестами то зачастую сложно назвать.

Решения будут тестироваться только на претестах во время контеста

You will have one point less

Yes!I like it too.

Ok.

Take it.

1 downvote for you to beat worse XD

I'll be the rank 0 of this contest.

ppc_qjd will beat you.

was not C digit dp? but it had too many cases to cover, ultimately I left it after wasting an hour :(

If you observe then you'll notice that:

let, x=max(n,m).
if k<x then there's no way.
if n,m both are odd then, ans=k when x is odd, else ans=k-2.
if n,m both are even then, ans=k when x is even, else ans=k-2.
if either one of n,m is odd and another is even then, ans=k-1.

You can add

std::ios::sync_with_stdio(0);
std::cin.tie(0);

to optimize your program.

And one Div2's D is another Div2's B XD

#define this_is_so_sad_alexa_play_despacito_2 ios_base::sync_with_stdio(0); cin.tie(0);

you're my new idol

No. not sum(length of segments) but number of integer points on the line

Thanks for the link. It helped me a lot. Have you solved any similar problem? Please share if you have.

F: a number is elegent only if it is not a perfect power. It can be counted with inclusion-exclusion principle

G: build a reachability graph from each source to sink. Now, take all non-empty and non-full subsets of sources. If number of elements in any subset is equal to number of sinks reachable from any of the sources from these subset, then it is possible to build a scc containing only these sources and sinks and not any other. So, answer in this case is no. Otherwise answer is yes.

beside the type of the problem (Number Theory) i couldn't find any similarity between both problem.

If destination is (x,y), you can first go from (0,0) to the destination in min(abs(x),abs(y)) diagonal steps then max(abs(x),abs(y))-min(abs(x),abs(y)) straight steps, if this is > k, then the answer is -1. If the straight steps count is s, there are 2 cases for it:

1) it is even, so you can use it all as diagonals, then let the remaining steps to reach k is rem, if rem is even you can use them also as diagonals, and if it is odd: if it is 1 you can break one of the previous diagonals into 2 straight steps and you are done. But if it is >= 3, you can use rem-2 as diagonals and the remaining 2 as straight steps.

2) it is odd, you can use s-1 as diagonals and the remaining 1 as straight. if rem is even you use them all as diagonals. And if it is odd, you can change your last step to be diagonal, and use rem-1 as diagonals and the last 1 as straight.

Imagine the K steps as 2 arrays: X[] and Y[] consisting of -1, 0 and 1 only. The i-th step is represnted by (X[i],Y[i]). A step is diagonal if it doesn't have a 0 in it. Let initially X[] and Y[] be full of 0. We are sure we have n ones in X[] and m ones in Y[]. Since we want diagonal moves we can change an even number of zeroes in X[] and an even number of zeros in Y[] to 1 and -1 and the we will still arrive at (n, m). It can be seen that there are only 4 cases to consider, depending on the parities of (k — n) and (k — m).

You are not the first and will be not the last to fail a problem due to slow input/output.

If slow output is allowed, then it will be much harder to distinguish n*lg^2(n) from n^2 for example.

Don't worry, we didn't have any doubt in each problems originality as well :D

You cannot sort the array, it will change the order of the sum of subarrays and the answer to your test case is 1.

Ans should be 1

A will be converted to [39]

and B also to [39]

there is no other possible way.

As you cannot change the order of elements in the array

that's all !

i think i have to sort the elements, i don't no why i did this assumption T_T

anyway, thanks guys.

This is educational Round,The purpose of the education problem is only to expose the participants to specific algorithms or topics,so having the same idea is just fine,originality isn't a specific requirement but ofcourse it's always better to have original problems

Floating-point types are not magic types that can represent every numbers — no matter how big they are — 100% correctly. double can only hold up to around 15 digits, and afterwards they will have errors.

Double can't accurately store such large numbers, meaning 10¹⁸ - 1 when converted to double becomes 10¹⁸ (as i think double always rounds up. Correct me if I'm wrong) and , but the answer is .

He maybe stores problem solutions!

I submit A about 3 min after contest start. But the connection of the Internet is break and I don't notice it immediately until I submit B...

Above is what thing happen during contest (>__<)

I made one look at B tests and decided to skip hacking this problem.

Digit DP

use combinatorics. I dont understand what idea with DP. We calculate answer for some x from 1 to x. Then answer is calc(r)-calc(l-1). For calculate answer we look digits of number x from left to right and try put digits from 0 to d[i] — 1 (there d[i] digit of number on position i) because we want build another number with same prefix until position i-1 and in this case if we put digits less than d[i] to position i then our
"new number" will be less than number x and we can put any digits to remain part after we add to answer for every "putted" digit C(n,m)...

Doubles become inaccurate after about 15 digits. If you wanted to use doubles you can use BigDecimal in Java for more precision!

it is awesome,why my solution used long get wr(http://mirror.codeforces.com/contest/1036/submission/42622516 ),but you get right

Your new submission was checked only on original test cases ( they do not include the hack test cases used by people to hack other's codes) that is why your new submission got accepted

average case of unordered_map is O(1). But, worst case is O(n). On the other hand, map gurantees O(logn) everytime.

Here is my solution using digit DP 42675923, it may help you. There are quite a lot of cases to take care of.

The main idea is that for each interval [L, R] the answer is F(R) - F(L - 1). Where F(x) equals the number of classy integers from 0 to x.

How to you calculate F(x)? Just using Dynamic Programming.

For a number x, the DP looks something like this:

dp[i][j][k][0] = number of integers less than x that are i digits long, end in j and they have k digits bigger than 0.

dp[i][j][k][1] = number of integers equal to x that are i digits long, end in j and they have k digits bigger than 0.

j is going to be between 0..9 and k in the range from 0..3, because a classy number contains no more than 3 non-zero digits.

Binary search.

double is not enough to store 18 digits without errors.

Someone said that this round should go unrated, is it true?
Click here!
Or the system test just start very late?

No, because A (first point on line) will not be equal B (second point in line), this is mentioned in the problem statement.

I don't get it :D

Or you overdid it somehow.

I solved it with bruteforce and some math observations :D

Even I used code snippet for E from code book of One of my friend And skipping someone's code for a question in which we just need to print ceil(k / n) is unfair.

I dealt with that using something like map<pair<int, int>, set<int>>.

The pair<int, int> is the point's coordinates, while the set<int> stores the IDs of the lines which include that point.

So, to get the count of the lines one point is part of, I'll get the size of the set mapped into that point's coordinates pair.

This should be a lesson for you. Be careful next time.

Actually, the issues with Ideone has been warned in the Codeforces rules (if I remembered correctly), so in technical views, this isn't something too unfair.

A Div2C problem become problem F in an Educational Round

Is that Grape's D2C is too difficult or Educational's problem F is too easy? :thinking:

Actually, funnily enough, our problem was inspired by another problem but that one came from project euler)