CF574

It will be fixed.

Generally,div.1 is harder than div.2

div.2 C=div.1 A

div.2 D=div.1 B ....

There are three divisions (the more digit the easier problems):

• div3 — usually for pupils
• div2 — students
• div1 — high-skilled students, engineers etc.

you're sorry that you can take place!!!!???? Hey everybody, I'm sorry that I'm alive lol :P

Absolutely yes!

And if you are lucky enough,you can even become an expert.

I think Summer informatics School like Codeforces Round 530 (Div. 2).

SIS is for russian ЛКШ. It's a summer training camp in Russia

Coordinator finds mistakes in problems statements

I agree that Educational Codeforces Round 68 had very strong pretests, which made hacking very difficult.

Oh, you are strong enough, and you won't be afraid of the strong pretests.

i will be master today....waiting for div1 vovuh (^.^)

Challenge accepted :)

SIS stands for summer computer school, so SIS team contest means team contest held in SIS.

Easy div1 :)

Just one more div2D and this would've been a beautiful round with 2 divisions.

rating count begins from 1500 , if you perform well ,you can directly reach blue after first round, else you would be green

Welcome to FairyForces :P

I didn't even understand the problem. Why the english is hard

Exactly .... B should have been A , A question is supposed to be cakewalk right and I wasn't able to understand what it was saying for the first 10 mins ....

Maybe there isn't too much difference if U think a lot about them:)

So it means we can reduce the problem to querying the number of different directions of the directed arrows in a certain range. Didn't figure out this until the last minute of the contest.

data structures

Link

Pretty much the same as https://discuss.codechef.com/t/chsqarr-editorial/12662

I think it is using trees, but I failed to pass it in time.

Argh, deque. The tutorial is everywhere, but it's not that hard to not figure out, so just blame myself.

Thanks abhayps! ;)

In fact only use Sparse Table can solve it. My submission http://codeforces.net/contest/1195/submission/57270378

Simply too costly, keep in mind that $$$n$$$ and $$$m$$$ may both reach $$$3000$$$.

-First i solved examples on paper, then recognized pattern. Result=summation(f(a[i],a[i])*n

My solution to D1 is:

1. Work out how many times each digit appears in each position.
2. Add the digits in each position.
3. Work out the total by adding these up multiplied by suitable powers of 10

I didn't get a solution for D2. I think the same process should work, but step 1 is more difficult.

For $$$f(x, a)$$$ and $$$f(x, b)$$$, if $$$a$$$ and $$$b$$$ have the same number of digits, the effect of $$$x$$$ on the answer is always the same. The same holds for $$$f(a, x)$$$ and $$$f(b, x)$$$. In addition, if $$$a$$$ has at least the same amount of digit as $$$x$$$, the effect of $$$x$$$ on answer is always the same. We only need to store the frequency of number of digits.

The contribution of $$$x$$$ would be like follows (take $$$x=1234567$$$):

$$$12345670 -> 123456070 -> 1234506070 -> ... -> 10203040506070$$$ if it is $$$f(x, a)$$$.

$$$1234567 -> 12345607 -> 123450607 -> ... -> 1020304050607$$$ if it is $$$f(a, x)$$$.

$$$a$$$ has number of digits $$$1 -> 2 -> ... -> numberOfDigitsOfx$$$.

To insert a zero between the digits, you can just use the *, /, % operators.

change int to long long

 vector<long long> a(n,0),b(n,0),dp1(n,0),dp2(n,0);

-I solved with Dynamic Programming. for (i=1;i<=n;i++) { dn1[i]=max(dn1[i-1],a[i]+dn2[i-1]); dn2[i]=max(dn2[i-1],b[i]+dn1[i-1]); } cout<<max(dn1[n],dn2[n])<<endl;

The main idea is DP. Let dp[i][0] be the best sum if we only take players up to position i and take the player in the top row at position i. dp[i][1] is defined similarly, except we take the player in the bottom row at position i. dp[i][2] is also similar, except we take no player in position i. We can then fill this dp table in O(N) time, as the transitions are relatively simple.

use dp. let dp[i][j] be the max sum u can take till column i and u choose jth row {0 , 1} in current column. now transition will be either from i-1 or from i-2 because no point in skipping 2 elements.

Thanks you guys, I will think how to do it with your tutoral. Hope me I will get accept :D

You can refer to my submission here. It is an easy application of dp

I think it's better to solve few harder problems, rather then wasting time implementing easy ones. I haven't liked it -_-

You can put $$$y = n - x$$$ which gives you $$$(x^2 + x)/2 + x - n = k$$$. It's quite simple to solve :)

I did it same way. If n>=1e9 then sqrt(n) gives not an accurate answer.

How i dealt with it:

int mysqrt(int b){
    int c = (int)sqrt(b);
    int r = max(0ll,c-10);
    int l = c+10;
    for (int i = r; i <= l; i++){
        if (i*i == b){
            return i;
        }
    }
    return c;
}

Any other non-math solution?) my solution: 57211560

ll x = (sqrt(9 + 8*(k + n)) - 3)/2;
ll y  =  n - x ;
solve for x it is easy not for y, and obtain y as n - x;
happy coding:)

x^2 + 3x -2(n + k) = 0

its positive root will solve the problem. and it is a guarantee that it has only one positive root. so the answer will be unique. let its positive root is x, then answer will be (x * (x + 1)) / 2 -k.

I think that you forgot f（45，45）=4455 also makes sense.

f(12,12) = 1122 | f(12,33) = 1323 | f(12,45) = 1425 | f(33,12) = 3132 | f(33,33) = 3333 | f(33,45) = 3435 | f(45,12) = 4152 | f(45,33) = 4353 | f(45,45) = 4455

Sum these up, you'll get 26730.

Hope this explains :)

f(a[0],a[0]) + f(a[0],a[1]) + f(a[0],a[2]) + f(a[1],a[0]) + f(a[1],a[1]) + f(a[1],a[2]) + f(a[2],a[0]) + f(a[2],a[1]) + f(a[2],a[2])

last correct submission is considered.

The problem E.aka TLE :D

In my case, O(nmlogn) was accepted by 500ms. I used efficient segment tree. I saw your solution, it was O(nmlog(nm)) and set/map have much overheads.

I had the same problem. After dozens of attempts to push O(n*m*log(2)), I decided to write something else. And finally, i wrote solution with sparse table. In my implementation queries were with fixed size, so i could answer them with O(1) time. But anyway Sparse table uses O(n*m*log(m)) precalc, but this is much faster then segment tree or other structure.

deleting the comment lines and thinking that it will be missed out from the codeforces users :D:

MikeMirzayanov Please look into this.

Both from Hangzhou, China. Coincidence? I don't think so ...

???

I think I don't give this guy my code.

Anyway,I find the similar problem of this round's E

Might he use my code by the similar problem.

So Why [user:ljc2002]not skipped?

Observe that for each digit of each number, you can predict what position it would occupy in the functional output. For ex., if the numbers are 22 34 then f(22,34) = 2324 and f(34,22) = 3242. So, the ith digit in, say, x would be the 2*ith or the (2*i + 1)th digit in the functional output. So, simply iterate over the 10's expansion of each number and add to an ans variable the value that each digit in the expansion would occupy in the output.

To complete the example above, you'd have s=(4*(10^0)+4*(10^1))+(3*(10^0)+3*(10^1)) from 34 for each number it is going to be paired with. Each number will be paired with n numbers (including itself), so, you'd have ans+=(n*s) for 34. Proceed similarly for each number in the input array.

My submission: http://codeforces.net/contest/1195/submission/57225770

3

12 33 45

you need to calculate element's sum of this

f(12,12) f(12,33) f(12,45)

f(33,12) f(33,33) f(33,45)

f(45,12) f(45,33) f(45,45)

calculated values of functions:

1122 | 1323 | 1415
1122 | 3333 | 3435
4152 | 4353 | 4455

you can present as

1020+102 | 1020+303 | 1020 + 405
3030+102 | 3030+303 | 3030 + 405
4050+102 | 4050+303 | 4050 + 405

you can see that sum of this equals to

(1020*n + 102*n) + (3030*n + 303*n) + (4050*n + 405*n)

where n=3

or just:

f(a1,a1)*n + f(a2,a2)*n + f(a3,a3)*n

Just store frequency of each type of drink and for any type of drink having frequency more than zero, say having frequency f, (f — f%2)/2, sets of that drink(decrease frequency by f — f%2), decrease the drink set count(originally ceil(n/2)) and after doing it for all present type of drinks, we have at max 1 drink of a particular type , so say K(not question's K) drinks are still required(Since all remaining drinks are having frequency 1) then choose to add minimum of (K, remaining sets) to the final answer, and finally that would be the answer I THINK!!!!

Try debugging your code through 'Custom invocation' feature of Codeforces.

Overflow. The right side is calculated first. (int)*(int) -> overflow.