i am new here so plz help me how does knowing the score pattern help..?

this can never happen because rating change depends on rank of participant

and E is an easy E

It seems that Div2 contests are becoming easy!

The last contest had 2 problems with score 1750 but both were very easy. Let's just wait for the problems.

Maybe you win this contest like Bell-sama in the last contest ;)

No badges for those who use these kinds of names for innocent variables.

Did you output "\n"?

The test file must be closed with '\n'

And look at the number of successful hacks!!!

Сделаем решето Эратосфена,при этом когда во 2 цикле делает isPrime[j]=false подсчитываем степень i в факторизации j (за logn) и прибавим это к счетчику простых делителей числа haveDivisors[j]. Предподсчитаем массив частичных сумм на массиве haveDivisors. Тогда ответ — это ps[b]-ps[a]

Ответ на задачу — сумма количества делителей всех чисел от b+1 до a. Собственно, алгоритм: сначала вычисляем заранее количество делителей для всех чисел, считаем частичные суммы и отвечаем на запросы за O(1)

Its a maxflow problem. Make a 2*N + 2 vertices , 2 copies of each node and 1 source and 1 sink. Now you can find out the respective edges required to make the graph (think about it a little bit, if u know max flow , else u can read about it), that part is only left. Then find the max flow from source to sink and print it.

I got hacked in D cause I used cin cout for input. Though I am pissed, I must say, that was a clever hack!

you should've used scanf and printf instead of cin and cout I guess..

For B:

5

1 1 1 1 1

B:

5
1 1 1 1 1

D: very long input and output

Well, I hacked D's that should obviously TLE, so the maximum tests weren't included in pretests. For B, there were a lot of incorrect solutions that had Passed Pretests.

also i hacked 1 ppl using this test:

3

3 3 3

Many did a brute force on D and didn't pre-calculate the values .

I've made 6 hacks with following test:

10

3 3 3 3 3 3 3 3 3 3

Most solutions used if(a[i] > 1) instead of while(a[i] > 1)

Also, there was a case of 3000 times of 3000, which may cause overflow on some solutions, but I haven't tried that

Валидатор ругался, что нет переноса в конце второй строки.

В конце нужно добавить Enter.

перевод строки в конце есть? или может лишний пробел в конце.

перевод строки в конце надо ставить в этом тесте

At the end need to add Enter.

I don't know, is my solution correct, but I did it in such way:

1) Let's calc the Eratosphen Sieve and take all prime divisors for every number in [1..5*10^6]

2) For each number let's divide it while we can, by all prime numbers, that we calculated.

So, it works about 2,9 sec

you just need to count sum of prime factors for each number,and then answer is d[a]-d[b](it't easy to show),for this precalculation you just need sieve of eratosthenes and for each prime p and number k; while (k | d) increase d[k],k=k/d

You don't need to find the number of prime factors per se in this problem or even calculate prime numbers per se.

What I did in D was to calculate for each number the lowest number that divides it (it will be a prime). You can do it with a Sieve of Eratostenes by assigning to each number the first number that divides it and ignore other divisors.

Knowing the smallest divisor for each number you can use a O(n) dynamic programming solution where:

numDivisors[i] == 1 + numDivisors[i / smallestDivisor[i] ].

You are basically dividing the number by it's smallest divisor and then adding the already calculated result for the remaining number.

Then you calculate the accumulated number of divisors from 1 to 5 000 000 and then for each query you can calculate the result by subtracting accum[a] — accum[b] since a!/b! is the same as (b+1)*(b+2)*...*a

The highest complexity of the algorithm will be the either the sieve calculation or the number of queries.

Edit: Code

Max-Flow

Hack at least improve your understanding of other contestant code, and also finding a bug in their program. It really helps me creating some corner test case.

Preprocessing is the key. Just count the amount of divisors for all the numbers in range 5000000, then create an array, i-th element of it contains a sum of divisors for all the elements in range (1..n) and then use it to calculate the answer — Arr[n]-Arr[k]

Answer was obviously phi(A)-phi(B) where we define phi(N) as number of all prime factors of N . (Ex- phi(12)=3 as 2*2*3). to compute phi(N) we could precompute using Sieve .

I guess you'll have to wait and see?

i too used cout,cin!!

http://mirror.codeforces.com/blog/entry/18031?#comment-229104

http://mirror.codeforces.com/blog/entry/18031?#comment-229101

yes,cout<<endl is tooooooooo slow,also may cout<<"\n" will pass :)

i guess yes. my solution was hacked. i changed all to int's and scanf printf. if you used int, it may pass easily.

I don't see anything bad in it. For example, I knew that my solution is incorrect before end of contests and had chance to resubmit...

It depends on the OS of the checking server. If it is linux than %lld is okay, but codeforces is using windows — so the right way is %I64d

because each test case contains number of games!

Fast IO ?

I don't understand your solution exactly. I solved it using Legendre's formula. (Although I don't know if it worked yet)

n = 3 1 1 2 2 3

These are valid test cases. If you are talking about hacking, u need to put a newline at the end.

У меня тоже такое было во время контеста.

mine passed in 1090sec with printf and scanf

always use scanf/printf when you have to input/output greater than 10^6 numbers. Learned the lesson in hard way.

use C++11, and write cin.tie(nullptr); 11225307

The problem is that you didn't use cin.tie(NULL). http://mirror.codeforces.com/contest/546/submission/11225554

Why? You should realize that the amount of input is huge, and it's going to take a while to read it using cin. Imo, it's only your fault. Using scanf and printf saves you a very big amount of time. I've learned it when I was upsolving. The solution, which used cin, got TL. But then I used scanf and the result was 140ms out of 1000. From that moment I'm using scanf and printf.

UPD: The submissions are: 10834692 and 10834765

Strongly agree!

You must also use cout << '\n', instead of cout << endl, it is significantly faster

My solution passed in 608 ms using Java.

Probably your algorithm can be improved.

Here's my approach: http://mirror.codeforces.com/blog/entry/18031?#comment-229101

And code: http://mirror.codeforces.com/contest/546/submission/11220819

cin is getting accepted . You had to write ios_base::sync_with_stdio(0) ; cin.tie(0) ; to get AC .

You solved 3 problem I see, your problem D has a TLE .

Lol, yes.

I'm curious is it possible at all to solve it in Python?

already)

Click here to the editorial :)

I guess people do know that! Just that they do not benchmark which input is too large for cin and cout to not work! Most of the times cin inputs upto 1000000 run fine on codeforces! Anyways apart from that the problems were good!!

I wonder, was this intended from the beginning. (Specifically, did Zlobober know about this?) This does not conform to the problem authors' guidelines that large tests should be included in pretests.

It's ok that you test for large inputs in easier problems but I doubt that is appropriate for a 1500 mark problem.

Don't get me wrong, I got AC. I am just curious.

fast output :D

your code 11229232

many people has this problem.using ll inplace of int & cin or cout inplace of scanf & printf caused TLE. It's not good...

http://mirror.codeforces.com/blog/entry/18034

I think it should be 3. The numbers will be 1 2 5 6 7