I have nothing to say this time, so meet yet another Div. 3 round :)

<almost-copy-pasted-part>

Hello! Codeforces Round #560 (Div. 3) will start at May/14/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**.

Remember that only the *trusted participants of the third division* will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a *trusted participants of the third division*, 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.

**Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.**

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

**UPD**: I also would like to thank nhho, chenjb and ksun48 for testing the round.

**UPD2**: I also would like to thank my friend Adilbek adedalic Dalabaev for valuable suggestions about the contest and testing it!

**UPD3**: Editorial is published!

**UPD4**:

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | nuoyanli | 7 | 368 |

2 | Vaseline_Warrior | 7 | 437 |

3 | adimiclaus15 | 7 | 446 |

4 | 1716638489 | 7 | 604 |

5 | leo990629 | 6 | 335 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | Java | 68:-2 |

2 | figdan | 63:-13 |

3 | makjn10 | 44:-1 |

4 | csts.21 | 40 |

5 | yashi2552 | 27 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | Tokisaki-Kurumi | 0:03 |

B | CoolAttacks | 0:03 |

C | igniubi | 0:08 |

D | foool | 0:13 |

E | maverick_10 | 0:15 |

F1 | cunt | 0:27 |

F2 | cunt | 0:26 |

Isn't the 12-hour hacking phase an overkill? I mean because most of the hacks are done within the first 6 hours or so.

Of course not, the hacking phase starts at 0:35 in Hong Kong, but I'm a lazy guy who wakes up at 12:00 everyday XD.

do you now one time in edu contest i submit a code that shoud get TLE but after hours nobody hacked me

so i said to one of my freinds that my code is wrong after that he hacked me :\ the cool thing is that i submit that code with another handle and it got AC ;\

Waiting for a hackforces!!! :D

I have nothing to say this time, ...I also would like to say that participants who will submit ...Just kidding :)

Honestly, I understood the meaning of your joke only a couple of minutes after downvoting your comment XD XD XD

Hope there are no server issues this time .. xD

The third category is good for people whose level is poor because it easier more than the second category

More

< copy-pasted-part >< /copy-pasted-part >?Vovuh's Division 3 Rounds are usually balanced and contain interesting problems, I hope this contest lives up to that standard as well! Good Luck To All Participants!

@Java

I agree! A was especially interesting. ;)

Woah, are you the real ben shapiro.

I am not, what the moo? Are you high on geniosity?

Aren't you the guy that destroys people with facts and logic?

fine

If there is a server issue just try the baby sites, they work well. It saved a lot of time for me in the last contest.

was my best contest ever..solved 5/7 . please dont hack me .

How did u solve D?(I've got WA on 32nd testcase and I am mad).

come on!

So, are we allowed to discuss problems during 12 hour phase?

ofc, you can't submit anymore

Since the solutions are visible discussions should not be a problem.

Yes.

Yes

почему ты игноришь серых?

Hi MikeMirzayanov I tried to hack my friend submission and get "Unexpected verdict" as a verdict for my hack how ever my friend submission should take RunTimeError as verdict of my hack test "I try that on Custom Invocation" my hack id is 558494 on problem D Is It a Bug in hacking system or what? Thanks

Can anybody explain E,please?

Greedy. First you have to calculate appearance of each $$$a_{i}$$$ and multiply it with $$$a_{i}$$$. Then sort both of arrays and reverse $$$a$$$ (or $$$b$$$). Answer is $$$\sum\limits_{1 \le i \le n} a_{i}*b_{i}$$$

Think in fixed values, the array $$$a$$$ and how many times the number $$$a[i]$$$ (0 index base) appears in the sum expression, so you can create an new array $$$staticval$$$. Note that $$$staticval[i]=a[i]*(n-i)*(i+1)$$$ for each $$$0 \leq i \leq n-1 $$$, then you arrangue the $$$b[i]$$$ values as you need (sorting $$$b$$$ and $$$staticval$$$), note that $$$staticval$$$ array have values less than $$$10^{18}$$$, so you always can obtain the answer.

Hey. What is the problem in my solution? Here is the code: Code.

I sorted a in ascending and b i descending order and Multiplied corresponding elements . Sorted back the product in order of corresponding elements of array a. Finally I printed the summation(f(l,r)) for 1<=l<=r<=n in O(n). Please explain :)

You should You should make the {a [i] * (n — i) * (i + 1)} * b [i] minimum, rather than {a[i]*b[i]}*(i+1)*(n-i)

So you should make tmp[i]=a[i]*(n-i)*(i +1).sort the b array

So the answer should be ∑tmp[i]*b[i]

Assume that you have the optimal array as C. So we have to find the minimum of \sum_{i = 1}^n(i)*(n-i+1)*a_i*c_i (This is because the i'th element will occur when l can be anything from 1 to i and r can be anything from i to n so i'th element will occur in i*(n-1+i) number of times). So we can rearrange b_i to form C. So to get the total minimum sort the modified A array where a_i = a_i * i * (n-i+1). and array B. And then for the minimum multiply a_i & b_{i-1}. Here is the code for this.

In D what is input when ans is -1 ?

for example: 1 2 2 8

We can't have 1 2 2 8 as test case because 1.all factors given are distinct 2.1 or the actual x is not given in the factors list

You may Consider Sample case where factors are: 2 3 4

first number = t. second number = n

Sorry, I misunderstood.

but they have said it will contain all factor , so what will be the answer

I don't think that's a valid input array. I think it's more along the lines of 4 8.

The answer to this is -1 because whatever number is divisible by 4 and 8 must also be divisible by 2, yet 2 is not in the input array.

i am confused. if all factor has given except 1 and x then 2 should be in input. please clear it to me.

Yes, that's why the answer is -1, because the input data is contradictory.

How to construct array in Problem E such a*b is minimized?

I tried by first taking frequency of each element in final answer which for each index i came out as i*(n-i+1). This is increasing and then decreasing sequence. So for final array, we can take smallest b value at middle position and distribute b by moving from the center of array a. But this approach seems incorrect since it gets wrong on given first test case itself.

How to construct the array so that final sum is minimized?

multiply a[i] with its query frequency, sort the two arrays in reverse order of each others then calculate sum of a[i]*b[i]

And be careful with overflows!

Thanks ! Was multiplying a[i] with its frequency at last.

why do we multiply a[i] with its query frequency ?

-i constructed mul[i] array as the freguency of each element times a[i], mul[i]=a[i]*(n-i)*(i+1) {my i starts from 0}; -then sorted mul[], and b[] -reverse b[] -k=(k+b[i]*mul[i])%M

Thanks ! Was multiplying a[i] with its frequency at last.

Assume that you have the optimal array as C. So we have to find the minimum of \sum_{i = 1}^n(i)*(n-i+1)*a_i*c_i. So we can rearrange b_i to form C. So to get the total minimum sort the modified A array where a_i = a_i * i * (n-i+1). and array B. And then for the minimum multiply a_i & b_{i-1}. Here is the code for this.

I dont feel like having anything learned from these problems. Its just understanding difficult language and fiddling with indexes. Not the fun stuff.

What is wrong in my code guys? Can you help me? Its about problem E: https://codeforces.com/contest/1165/submission/54136675

a[i]*b[i] can overflow,can do (a[i]%mod)*(b[i]%mod)

Why? Its impossible in my view! a[i] is already % mod, and b[i] max value is 10 in the power of 6, so max value is 10 in the power of 16!!!

You are right. Your mistake is modding array $$$a$$$.

Does it matter if a take %mod of a and not taking of b?

a[i] = (((n-i+1LL)*i)*a[i])%mod;

When u mod $$$a_{i}$$$, sorting goes wrong.

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa thank you

You are welcome

Thanks...Such a minute observation...Finally able to solve it after reading this comment...

you don't mod after you multiply with the frequency

It's my first codeforces contest. Can anyone please explain to me what is this hacking period?

You search for bugs in codes of other people

http://codeforces.com/help#q3

During hacking phase, you may read other's code and find bugs in them (maybe their code fails in some test case, likely corner cases or something similar).

If you successfully find a test case in which their code may fail, you get some points and the latter loses his/her because of wrong verdict (Hacked in this case).

On the contrary, if their code runs successfully providing correct output on your provided test case, you will face an unsuccessful hacking attempt and lose your points.

what's the approach to solve C please?

Start in the first position anf, greedly, start checkin if s[i]==s[i+1], if its equal, erase s[i] and chande the odd positions to even positions, this is the answer if the string is even, otherwise, erase the last position

Any proof?

@Alphatrance

It is required if you have elements starting from odd position, say xxxxy, that next element must be different. So its gauranteed to delete one of the above 4 possible x. Even if you delete first 3 x, you have last x, come into original position in the new string, as you would have deleted the last 3 x.

Also, If you move from left to right, deleting, you gaurantee that that prefix will always be a good string, irrespective of what happens in the next part.

Thus the greedy approach follows.

Suppose that i is the least position at string s that s[i]==s[i+1] and i is odd. If you dont erase it, or the next element, you will never change the parity of the positions <= to i and you will never erase them, so you have to erase all the positins from the beggining with the conditions of the problem.

for every odd index, if(str[i]==str[i+1]) just remove str[i]

after that, if str.size() is odd then remove last index

I had the following strange issue when sorting in Java:

In both problem B and E, I got TLE when using

`Arrays.sort`

but AC when using`Collections.sort`

. Has anyone else encountered this problem?I have encountered it too. I didn't try Collections.sort(). I'm getting mad. Just can't understand why Arrays.sort() gives time limit exceeded verdict.

Arrays.sort() uses the quicksort algorithm, whose worst-case running time is O(n*n). The other day one of my solutions for a Div.3 problem was hacked because someone created a counter test on Java's sort method, from this time on I coded a custom mergesort function with guaranteed O(n log n) performance.

Ah, cheers, you're absolutely right (see this article). However, I don't think you have to code your own sorting algorithm since, apparently, the worst-case time is O(n log n) when sorting objects.

Well, it's just 30 lines of code that I copy-paste, and more often I sort primitive types (in problem E, where I used mergesort, I sorted an array of longs).

That's a good point. Alternatively, one could use

`Long`

instead of`long`

.Well, the overhead is rather high when you have big input data, it's faster to simply mergesort and forget about it :)

In contests like Google Code Jam, it's much less of a problem, since the TLs are on the order of 15s, enough to make an unoptimized solution fail, but high enough to allow slight low-level inefficiency like the one you mentioned (Long vs long). And no one tries to come up with a corner case for Arrays.sort()

I am pissed off ! I don't know why a nlogn code shows tle (using sort) in java then I submitted in python it's get accepted. even in next problem I m getting tle...uh

in the first time I encountered the same problem (TLE). Then I used TreeSet instead of Arrays/ArrayList, it will sort by itself and collect distinct numbers.

Read this: How to sort arrays in Java and avoid TLE

In my job I am practicing java and I am facing...

Here is a quick editorial

A

SpoilerFrom

right to left, we want something like 000001000 where there are X=9 digits and the (Y=5)-th index is 1. We scan our string (from right to left) and determine the number of indexes where the digits are different.B

SpoilerWe can attempt the contests in increasing order of difficulty.

C

SpoilerWe can add to our answer greedily.

D

SpoilerIf the answer exists, it must be X = min(divs) * max(divs). We should check that it has the same number of divisors (N+2). To check how many divisors X has, write it in the form p1^e1 * p2^e2 * ... ; then the number of divisors is (e1+1) * (e2+1) * ...

E

SpoilerLet's look at the coefficient of a_i in the sum [0 indexed]. It is (i+1) * (N-i), since there are i+1 choices for the left index (0 <= j <= i) and N-i choices for the right index (i <= r < N) Now by the rearrangement inequality, we want to sort B opposite to these coefficients a_i * (i+1) * (N-i).

F

SpoilerIf the task is possible on day D, then its possible on day D+1, D+2, etc. So we can use a binary search to convert the question to a decision problem: is it possible to do it within D days?

We need an important observation: when a type is on sale, we don't need to buy it until it is the last day (in [1, D]) that it is on sale. Let's call this day its "final sale" day.

For each day, for each type that is on sale on that day, lets look at whether this type is on a final sale. We can do this with a binary search. If it is, we should put all our money into it, otherwise we could wait. At the end, anything we didn't buy should be bought at full price.

your E is wrong you shouldn't mod after multiplying with frequency

You cant % array A before sorting, it gave me Wrong Answer ...

In problem F, on i th day can i order more than 1 types of micro-instruction?

Yes

For problem D can someone explain the formula for the number of divisors?

`p1^e1 * p2^e2 * ...`

Suppose, N be a number. Then N can be written as follows:

`N = p1^e1 * p2^e2 * p3^e3 * p4^e4 * ......... * pk^ek`

This is called prime factorization of N. Now, if 'd' is a divisor of N, 'd' shouldn't contain any other prime except (1 <= pi <= k). And the power of pi should be within (0 — ei).

so

`d = p1^b1 * p2^b2 * p3*b3 * p4*b4 * .........* pk^bk`

, where, 0<=bi<=eiFor a single prime it can be present in a divisor in (ei+1) ways [ pi has power from 0 to ei ]

so total number of divisor

`(NOD) = (e1+1) * (e2+1) * (e3+1) * (e4+1) * ...... * (ek+1)`

I hope its clear to you. :)

Thanks a lot!

I have a small doubt in this problem F1,F2. Can we buy more than one types of microtransactions in a single day? e.g. 1 of type 1, and 1 of type 2 etc. Or its just that we can buy any number of any SINGLE microtransaction each day?

From your code it seems that we can actually buy multiple types. But this was not that clear from the problem statement.

In F the question doesn't ask us to keep the money spent minimum, so why don't we buy all type on the first day?

2nd test case of D problem Ruined my contest.

you have written,

if(n==1) cout << v[0]*v[0] << '\n';

which is not always true.

Example:

1 100000

1 is not allowed right?

Can you please elaborate your question ..??

For which case or whare, you want to know 1 is allowed or not.

sorry, my bad. 1 is the array size. I thought it was one of the divisor.

It is array size.

Even I didn't thought of all pairs.. e.g 1 2 2 10

shouldn't

Ebe solved this way ?:first sort a, and b array. Then by rearrangement inequality, minimum order must be a1b1 + a2b2 + .... .

Then for effective (O(n)) calculation, I used this (where pr[n] = a1 + a2 + ... a3, ... i.e. prefix sum)

which I think is correct formulation, but its giving me 643 instead of 646 for 1st test case. Can someone help please?

Thanks.

Read the problem.

It's because you are not allowed to permute array a, only b. There are also other errors with your solution. You are not adding to the final answer correctly. Check this.

do exaclty the same but not sorting A before you do the algorithm above

rupav Sort A after multiplying with the coefficient (i*(n-i+1)) i.e. Sort the Array ModifiedA where ModifiedA[i] = A[i]*i*(n-i+1).

See this solution.

Good Round with strong pretests. Thanks Vovuh

No the pretests were very weak for A. And to prove my point I hacked you. (Sorry)

Your way of proving things is really very harsh.

Perhaps, but if it’s any consolation, your code would have been tested through other hacks anyway at the end of the contest.

Yeah I know, was just joking.

I use binary search to solve B, I use std::lower_bound got correct 54118173 ,but I try to use std::set::lower_bound got incorrect 54110418, could somebody tell me why...ORZORZ

Yes, lowerbound(set.begin, set.end, value) will take O(n). Instead you should use set.lower_bound(value)

True, but not in any way relevant to what was asked :D

Sorry, my bad.

Check this test case: Input: 1 3 3 Output: 3 Your output: 2 Set erases not unique elements

thanks a lot

In your second submission you used set. set does not contain any duplicates. That's why. Consider This case:

then set will contain only one 5. So your output will be 1 instead of 5. Change your set to multiset you will get AC.

ORZ ORZ

What kind of test cases are being used to hack A?

11 5 2 11010000101

Is the correct answer 1?

Yeah

This contests was good except for weak pretests. For example I was hacked on A, and I know why I was hacked. I am surprised that pretests didn't catch this simple bug and my rating is going to suffer. I am dissapointed.

Great round with great problems! No issues with the servers either. Thank you

"I tried to make strong tests." While I believe this is true, I don't believe much thought or time went into them as seen by how many people were hacked on A. I know that Vovuh does many rounds but maybe he should take some time before finalizing it.

I feel like Vovuh should give you a rebate for those lost points man.

LOL

Hacking is a part of contest. If pretests are made very strong then what is the point of hacking?

time to change the name of codeforces to hackforces ...

I think so

Did anyone notice the number of submissions of F1 is exactly equal to the submissions of F2.

Strong tests !! Is the meaning of strong has been changed lately ?

Is E polinomially solvable if we are allowed to permute both a and b ?

Can anybody explain the first sample input/output of problem E ?

Input:

Output:

The problem statement isn't clear to me :)

If you reorder the elements of

bin this way:You'll have the next sums:

$$$ f(1,1) = 9, f(1,2) = 25, f(1,3) = 46, f(1,4) = 64, f(1,5) = 92 $$$

$$$ f(2,2) = 16, f(2,3) = 37, f(2,4) = 55, f(2,5) = 83 $$$

$$$ f(3,3) = 21, f(3,4) = 39, f(3,5) = 67 $$$

$$$ f(4,4) = 18, f(4,5) = 46 $$$

$$$ f(5,5) = 28 $$$

Then the total sum will be:

P.D. I hope this has helped you better understand the test case.

Thank you Ismael_Olvera.

I got the point :)

can u explain more ?

Of course. The task in this problem is reorder the elements of the array

$$$b$$$(the array$$$a$$$can't be moved). We need to reorder$$$b$$$in such way that the value of the following expression is the minimum possible.For clarity, let's call

$$$c$$$to the array such that $$$c_i = a_i * b_i$$$How does $$$\sum\limits_{1 \le l \le r \le n} f(l, r)$$$ mean?The expression is equal to say:

"take all the possible subarrays incand apply them this function, finally sum all the results".Example:$$$ a = [1,8,5] $$$

$$$ b = [9,4,7] $$$

If I choose this order, $$$ b = [4,7,9] $$$, the array of multiplications,

$$$c$$$, will be $$$ c = [4,56,45] $$$. Finally the sum of apply the functions to all the possible subarrays is:If I choose the order, $$$ b = [7,4,9] $$$, $$$c$$$ will be $$$ c = [7,32,45] $$$. And the sum of apply the functions to all the possible subarrays is:

As you can see, the order $$$b = [7,4,9]$$$ is better than $$$b = [4,7,9]$$$.

Note:If you have $$$n$$$ elements in the array, there are $$$n!$$$ ways to reorder$$$b$$$.Test case:$$$ a = [1,8,7,2,4] $$$

$$$ b = [9,7,2,9,3] $$$

As I said before, the best way to reorder

$$$b$$$is: $$$ b = [9,2,3,9,7] $$$.Just for extra help, the array that I called

$$$c$$$should be: $$$ c = [9,16,21,18,28] $$$.I hope this explanation can help you! :)

weak pretest:(

Is there any Pending System Testing now also?

Is this contest unrated? Because my rating is not updated yet, and my rating is less than 1600.

Just wait, it should be updated soon

Oh.. Okay. Actually the hacking phase was finished. So thats why i asked.

The thing is that the system's checking

allsolutions w/ hack-tests.Im about task D. Why the answer for this test is 9, not 6? k = 1, n = 1, d1 = 3.

Because for 6 dividers will be 3 and 2

Thanks

For 6, the almost divisors will be

2, 3. Whereas 9 will only has 3 as almost divisors.the first problem data is so easy I was hacked:(

does it matter if the contests is unrated

Who said it's unrated?

FBI

why and who said the contests is unrated

Where is editorial ?? What about system testing ??

Is this contest unrated?Why I don't get rating changes?

I don't know nobody said it's unrated

oh,thanks.It's too late to update the rating.

System still calculating something, my standing first dropped from 500 to 1700, now it's changing between 1500-1700

Emm,I got it.Thanks.

Your A got hacked by someone that's why your standing dropped from 500 to 1700.

See! it's because of my standing. 500 to 1700 was too much for a hacked A and it caused indecisive loop between 1500 and 1700. Now system test restarted to decide it :P

System Test has finished?

No

Can someone post a solution in

Pythonfor "D — Almost All Divisors" without "Time limit exceeded on test 4"?Or show me error in my code https://codeforces.com/contest/1165/submission/54168485

Updated 1: Fixed logical errors, still TLE

After

if divisors[i] * divisors[~i] != guess: print(-1) break

You should continue to see other test's instead you just break I think

Thanks, fix code https://codeforces.com/contest/1165/submission/54167593

Still have "TIME_LIMIT_EXCEEDED"

if not correct:continueThis is wrong, because you don't print -1 beforeThanks, fixed https://codeforces.com/contest/1165/submission/54168485

Submitting your code with pypy3 gives AC: 54169085. Though, I don't know why py3 is so slow in this task

Thanks!

BTW if not correct you have to print -1 but i am unable to see why TLE though maybe time limit is strict for python3 with fastio c++ 14 takes ~ 300 ms

Yeah, saw lots of similar algorithms in C++ that passed.

I had similar solution and it got accepted with Pypy3, cases like 2 999389 999917 too much for Python. Here I just wrote an alternative solution: link

Amazing job!

I submit D at the last second，and failed because of my poor Broadband net T.T

When system testing will be done for the contest??

I think it's already done

It is happening now.

when will contest ratings are going to be given ?

Is contest rated or not?

Yes Just who under 1600

when will our ratings will come?

using cf-predictor you can know your rating change will be +139 if any solution don't get wa on system test.

Guess mine as well:)

Yes i know that if my solutions will not get wa i will take about +139 but i want to take my +139

And Now whaaaaat!

When will the rating change come out?MikeMirzayanov Ratings are not updated yet ...Pls look into the matter

this round unrated??

No, I think it's not as written in the rules...but it's very late this time..hope it will be updated soon.

still some system test is going on

admins, plz press the start system test button

Admins busy, watching Game of thrones' Monday episode.

system test feels like a pause.

RATING CHANGE IS OUT ! ON THE RIGHT OF STANDINGS !

Check again -_-

Check it on friends Standings. It shows for me there.

unrated?why?

even system testing is not done.

Press the button.FINALLY !!!

I have a question in problem D, I have the same ideas

but I've got WA on test 5, and after some tries finally WA on test 6,I really feel frustrated . Could someone tell me why my code is wrong?54168335

Just try for find countertests.

1

3

3 4 9

Your output: 36

Right answer: -1

P.S. Try to check found number for correctness before printing.

Really Thanks . Now I have found My mistakes ！

Why is the test so slow?

It often takes some (1 to 2) hours to run system test

Was this round unrated?

Please tell why my approach for Problem E is incorrect?

My Solution: https://ideone.com/tBe1up

I am also doing like mapping max value of a with min value of b and so on. And then calculating the answer using dp like dp[i] denotes the answer for ai and bi arrays till index i.

Please tell, I can't figure out the same.

Editorial is doing the same thing for vali as given.

Make your code readable and ask again

Don't know why it was not readable. I made it public. Try this: https://ideone.com/tBe1up

he means your code has too much define and others may not understand

It is not much of define.

ll means long long

and fl(i,a,b) means for loop with range [a, b)

and slld(a) means scanf("%lld", &a)

Just this.

I think mapping arrays $$$a$$$ and $$$b$$$ it's not enough, you need to map the array $$$a'$$$, that $$$a'[i]=a[i]*cnt*(n-cnt+1)$$$

That's what I am asking. Why?

$$$a=[4, 3, 2, 1, 2, 3, 4]$$$; $$$b=[1, 1, 1, 1, 1, 1, 1]$$$ sorting $$$a$$$ you get: $$$a=[1, 2, 2, 3, 3, 4, 4]$$$ so you $$$a[i]*b[i]$$$ is the same as $$$a$$$ finally, you have $$$ans=[1*7, 2*12, 2*15, 3*16, 3*15, 4*12, 4*7]$$$ but the answer is: $$$resp=[4*7, 3*12, 2*15, 1*16, 2*15, 3*12, 4*7]$$$ as you can see, it's not enough mapping $$$a$$$ and $$$b$$$

phibrain How did you came up with this thinking of using vali instead of ai, by using some test cases only or any other thing?

It's just a counterexample of a possible solution, so it's not hard to got that.

My rate didn't change yet Why?

It has now! You gained 89 rating, congrats :)

ya thank u

Sorry for criticizing, but frankly I don't think Div 3 problems are easier than Div 2 in any sense.

Div 3 problems are implementation tasks and costs serious debug time, and this time Div 3 A is harder than Div 2 A (#559) imo. Other problems are also annoying implementations which I fail to debug quick enough to get a high rating.

Div 2 is generally a more relaxing coding experience for me, to calm down and think of ways to optimize to AC, but Div 3 is just me frantically debugging. 4 questions in Div 3 to increase rating is rusher than 3 in Div 2, don't we think?

Problem E- Can anyone please explain why that while using

long long int yyy=(n-i)*(i+1); a[i]=a[i]*yyy;

produces an error in https://codeforces.com/contest/1165/submission/54228312

whereas simply writing - a[i]=a[i]*(n-i)*(i+1) gets an AC

Hi, I am a newbie to codeforces. My approach for problem E is similar to that of above, however, I got an WA on testcase 5 IMO, this is due to overflow, but cannot figure out where since I have implemented required %mod in the arithmetic operations.

Deeply thanks for any constructional advices :)

My code

Update: When I change from unsigned long long to long long, it magically AC,

My code of AC

Has anyone came across the same problems of using all for mod result resulted in a WA but changed to ll made an AC, any explanation or idea?

Thanks a lot for the help :)

Regarding Problem C My code gives TLE . I've seen the editorial but I can't seem to find the problem in my code which leads to TLE. Here is the link to the code : https://ideone.com/fY10V4

I was the first one to solve problem E, yaaay! yaaay!