### Vovuh's blog

By Vovuh, history, 5 months ago, ,

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
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
872 successful hacks and 341 unsuccessful hacks were made in total!

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

• +118

 » 5 months ago, # |   -28 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.
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 do you now one time in edu contest i submit a code that shoud get TLE but after hours nobody hacked meso 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 ;\
 » 5 months ago, # |   -7 Waiting for a hackforces!!! :D
 » 5 months ago, # |   +1 I have nothing to say this time, ... I also would like to say that participants who will submit ...Just kidding :)
•  » » 5 months ago, # ^ |   -10 Honestly, I understood the meaning of your joke only a couple of minutes after downvoting your comment XD XD XD
 » 5 months ago, # |   +19 Hope there are no server issues this time .. xD
 » 5 months ago, # |   +13 The third category is good for people whose level is poor because it easier more than the second category
 » 5 months ago, # |   0 More < copy-pasted-part >< /copy-pasted-part > ?
 » 5 months ago, # |   +3 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!
•  » » 5 months ago, # ^ |   0 @JavaI agree! A was especially interesting. ;)
•  » » » 5 months ago, # ^ |   0 Woah, are you the real ben shapiro.
•  » » » » 5 months ago, # ^ |   0 I am not, what the moo? Are you high on geniosity?
•  » » » » » 5 months ago, # ^ |   0 Aren't you the guy that destroys people with facts and logic?
 » 5 months ago, # | ← Rev. 2 →   -29 fine
 » 5 months ago, # |   0 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.
 » 5 months ago, # |   -6 was my best contest ever..solved 5/7 . please dont hack me .
•  » » 5 months ago, # ^ |   +1 How did u solve D?(I've got WA on 32nd testcase and I am mad).
•  » » » 5 months ago, # ^ |   +2 sort the almost divisor list check if it satisfies. lets say our number X. divisor[i]*divisor[n-1-i]==X count the number of almost divisors of X. it must be equal to n.
•  » » 5 months ago, # ^ |   0 come on!
 » 5 months ago, # |   0 So, are we allowed to discuss problems during 12 hour phase?
•  » » 5 months ago, # ^ |   0 ofc, you can't submit anymore
•  » » 5 months ago, # ^ |   +1 Since the solutions are visible discussions should not be a problem.
•  » » 5 months ago, # ^ |   +3 Yes.
•  » » 5 months ago, # ^ |   +40 Yes
•  » » » 5 months ago, # ^ |   -11 почему ты игноришь серых?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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
 » 5 months ago, # |   0 Can anybody explain E,please?
•  » » 5 months ago, # ^ |   0 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}$
•  » » 5 months ago, # ^ | ← Rev. 8 →   0 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.
•  » » » 5 months ago, # ^ |   0 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 :)
•  » » » » 5 months ago, # ^ |   0 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 arraySo the answer should be ∑tmp[i]*b[i]
•  » » 5 months ago, # ^ |   +1 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.
 » 5 months ago, # |   +1 In D what is input when ans is -1 ?
•  » » 5 months ago, # ^ |   +1 for example: 1 2 2 8
•  » » » 5 months ago, # ^ |   +1 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 listYou may Consider Sample case where factors are: 2 3 4
•  » » » » 5 months ago, # ^ |   +2 first number = t. second number = n
•  » » » » » 5 months ago, # ^ |   0 Sorry, I misunderstood.
•  » » » » » » 5 months ago, # ^ |   0 but they have said it will contain all factor , so what will be the answer
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 5 months ago, # ^ |   0 i am confused. if all factor has given except 1 and x then 2 should be in input. please clear it to me.
•  » » » » » 5 months ago, # ^ |   0 Yes, that's why the answer is -1, because the input data is contradictory.
 » 5 months ago, # |   +1 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?
•  » » 5 months ago, # ^ |   +1 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]
•  » » » 5 months ago, # ^ |   +3 And be careful with overflows!
•  » » » 5 months ago, # ^ |   +1 Thanks ! Was multiplying a[i] with its frequency at last.
•  » » » 5 months ago, # ^ |   0 why do we multiply a[i] with its query frequency ?
•  » » 5 months ago, # ^ |   +1 -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
•  » » » 5 months ago, # ^ |   +1 Thanks ! Was multiplying a[i] with its frequency at last.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
 » 5 months ago, # |   -26 I dont feel like having anything learned from these problems. Its just understanding difficult language and fiddling with indexes. Not the fun stuff.
 » 5 months ago, # |   0 What is wrong in my code guys? Can you help me? Its about problem E: https://codeforces.com/contest/1165/submission/54136675
•  » » 5 months ago, # ^ |   +2 a[i]*b[i] can overflow,can do (a[i]%mod)*(b[i]%mod)
•  » » » 5 months ago, # ^ |   0 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!!!
•  » » » » 5 months ago, # ^ |   +1 You are right. Your mistake is modding array $a$.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Does it matter if a take %mod of a and not taking of b?
•  » » » » » » 5 months ago, # ^ |   +6 a[i] = (((n-i+1LL)*i)*a[i])%mod;When u mod $a_{i}$, sorting goes wrong.
•  » » » » » » » 5 months ago, # ^ |   +3 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa thank you
•  » » » » » » » » 5 months ago, # ^ |   0 You are welcome
•  » » » » » » » 5 months ago, # ^ |   0 Thanks...Such a minute observation...Finally able to solve it after reading this comment...
•  » » 5 months ago, # ^ |   +1 you don't mod after you multiply with the frequency
 » 5 months ago, # |   +1 It's my first codeforces contest. Can anyone please explain to me what is this hacking period?
•  » » 5 months ago, # ^ |   +1 You search for bugs in codes of other people
•  » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   0 what's the approach to solve C please?
•  » » 5 months ago, # ^ |   0 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
•  » » » 5 months ago, # ^ |   0 Any proof?
•  » » » » 5 months ago, # ^ |   0 @AlphatranceIt 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.
•  » » » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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
 » 5 months ago, # |   +4 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?
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   +13 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.
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ |   0 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).
•  » » » » » 5 months ago, # ^ |   0 That's a good point. Alternatively, one could use Long instead of long.
•  » » » » » » 5 months ago, # ^ |   +3 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()
•  » » 5 months ago, # ^ |   0 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
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   +3 Read this: How to sort arrays in Java and avoid TLE
•  » » 5 months ago, # ^ |   +6 In my job I am practicing java and I am facing...
 » 5 months ago, # | ← Rev. 2 →   +33
 » 5 months ago, # | ← Rev. 3 →   +47 Here is a quick editorialA 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. N, X, Y = map(int, raw_input().split()) S = map(int, raw_input()) ans = 0 for i in xrange(X): need = 1 if (i == Y) else 0 if S[N - 1 - i] != need: ans += 1 print ans B SpoilerWe can attempt the contests in increasing order of difficulty. N = int(raw_input()) A = map(int, raw_input().split()) A.sort() day = 0 for a in A: if a >= day + 1: day += 1 print day C SpoilerWe can add to our answer greedily. N = int(raw_input()) S = raw_input() ans = [] for c in S: if len(ans) % 2 == 0 or ans[-1] != c: ans.append(c) if len(ans) % 2 == 1: ans.pop() print N - len(ans) print "".join(ans) 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) * ... def solve(N, A): X = min(A) * max(A) if any(X % d for d in A): return -1 d = 2 divs = 1 # Number of divisors of X while d * d <= X: e = 0 while X % d == 0: X /= d e += 1 divs *= e + 1 d += 1 if d == 2 else 2 if X > 1: divs *= 2 return divs == N + 2 T = int(raw_input()) for _ in xrange(T): N = int(raw_input()) A = map(int, raw_input().split()) print solve(N, A) 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). N = int(raw_input()) A = map(int, raw_input().split()) B = map(int, raw_input().split()) MOD = 998244353 coeffs = [(i+1) * (N-i) * A[i] for i in xrange(N)] coeffs.sort() B.sort(reverse = True) ans = 0 for i in xrange(N): ans += coeffs[i] % MOD * B[i] % MOD ans %= MOD print ans 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. import bisect, collections N, M = map(int, raw_input().split()) need = map(int, raw_input().split()) offers = [map(int, raw_input().split()) for _ in xrange(M)] offers.sort() O1 = collections.defaultdict(list) O2 = collections.defaultdict(list) for d, t in offers: O1[d].append(t-1) O2[t-1].append(d) def possible(day): cash = 0 A = need[:] for cur_day in xrange(1, day+1): cash += 1 for t in O1[cur_day]: B = O2[t] j = max(0, bisect.bisect(B, day) - 1) if cur_day < B[j] <= day: delta = min(A[t], cash) cash -= delta A[t] -= delta if cash < 0: return False return cash >= 2 * sum(A) lo, hi = 0, 2 * sum(need) while lo < hi: # invariant: hi is possible mi = (lo + hi) / 2 if possible(mi): hi = mi else: lo = mi + 1 print lo 
•  » » 5 months ago, # ^ |   +8 your E is wrong you shouldn't mod after multiplying with frequency
•  » » 5 months ago, # ^ |   0 You cant % array A before sorting, it gave me Wrong Answer ...
•  » » 5 months ago, # ^ |   0 In problem F, on i th day can i order more than 1 types of micro-instruction?
•  » » » 5 months ago, # ^ |   0 Yes
•  » » 5 months ago, # ^ |   0 For problem D can someone explain the formula for the number of divisors? p1^e1 * p2^e2 * ...
•  » » » 5 months ago, # ^ |   +2 Suppose, N be a number. Then N can be written as follows: N = p1^e1 * p2^e2 * p3^e3 * p4^e4 * ......... * pk^ekThis 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. :)
•  » » » » 5 months ago, # ^ |   0 Thanks a lot!
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 months ago, # ^ |   0 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?
 » 5 months ago, # |   0 2nd test case of D problem Ruined my contest.
•  » » 5 months ago, # ^ |   0 you have written,if(n==1) cout << v[0]*v[0] << '\n';which is not always true.Example: 1 100000
•  » » » 5 months ago, # ^ |   0 1 is not allowed right?
•  » » » » 5 months ago, # ^ |   0 Can you please elaborate your question ..??For which case or whare, you want to know 1 is allowed or not.
•  » » » » » 5 months ago, # ^ |   0 sorry, my bad. 1 is the array size. I thought it was one of the divisor.
•  » » » » 5 months ago, # ^ |   +1 It is array size.
•  » » » 5 months ago, # ^ |   0 Even I didn't thought of all pairs.. e.g 1 2 2 10
 » 5 months ago, # |   +1 shouldn't E be 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)  fr(i, n){ ans += ((((1ll*pr[i+1])*(1ll*b[i]))%mod)*(n-i))%mod; } which I think is correct formulation, but its giving me 643 instead of 646 for 1st test case. Can someone help please?Thanks.
•  » » 5 months ago, # ^ |   +7 Read the problem.
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 do exaclty the same but not sorting A before you do the algorithm above
•  » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   0 Good Round with strong pretests. Thanks Vovuh
•  » » 5 months ago, # ^ |   +39 No the pretests were very weak for A. And to prove my point I hacked you. (Sorry)
•  » » » 5 months ago, # ^ |   +1 Your way of proving things is really very harsh.
•  » » » » 5 months ago, # ^ |   0 Perhaps, but if it’s any consolation, your code would have been tested through other hacks anyway at the end of the contest.
•  » » » » » 5 months ago, # ^ |   0 Yeah I know, was just joking.
 » 5 months ago, # | ← Rev. 3 →   0 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
•  » » 5 months ago, # ^ |   0 Yes, lowerbound(set.begin, set.end, value) will take O(n). Instead you should use set.lower_bound(value)
•  » » » 5 months ago, # ^ |   +4 True, but not in any way relevant to what was asked :D
•  » » » » 5 months ago, # ^ |   0 Sorry, my bad.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +6 Check this test case: Input: 1 3 3 Output: 3 Your output: 2 Set erases not unique elements
•  » » » 5 months ago, # ^ |   0 thanks a lot
•  » » 5 months ago, # ^ |   0 In your second submission you used set. set does not contain any duplicates. That's why. Consider This case: 5 5 5 5 5 5 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.
•  » » 5 months ago, # ^ |   0 ORZ ORZ
 » 5 months ago, # |   0 What kind of test cases are being used to hack A?
•  » » 5 months ago, # ^ |   0 11 5 2 11010000101
•  » » » 5 months ago, # ^ |   0 Is the correct answer 1?
•  » » » » 5 months ago, # ^ |   0 Yeah
 » 5 months ago, # |   -8 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.
 » 5 months ago, # |   +11 Great round with great problems! No issues with the servers either. Thank you
 » 5 months ago, # |   -23 "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.
•  » » 5 months ago, # ^ |   0 I feel like Vovuh should give you a rebate for those lost points man.
•  » » » 5 months ago, # ^ |   0 LOL
•  » » 5 months ago, # ^ |   +4 Hacking is a part of contest. If pretests are made very strong then what is the point of hacking?
 » 5 months ago, # |   -6 time to change the name of codeforces to hackforces ...
•  » » 5 months ago, # ^ |   0 I think so
 » 5 months ago, # |   0 Did anyone notice the number of submissions of F1 is exactly equal to the submissions of F2.
 » 5 months ago, # |   +4 Strong tests !! Is the meaning of strong has been changed lately ?
 » 5 months ago, # |   +13 Is E polinomially solvable if we are allowed to permute both a and b ?
 » 5 months ago, # |   +4 Can anybody explain the first sample input/output of problem E ?Input: 5 1 8 7 2 4 9 7 2 9 3 Output: 646 The problem statement isn't clear to me :)
•  » » 5 months ago, # ^ |   +14 If you reorder the elements of b in this way: 9 2 3 9 7 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: 646 P.D. I hope this has helped you better understand the test case.
•  » » » 5 months ago, # ^ |   0 Thank you Ismael_Olvera.I got the point :)
•  » » » 5 months ago, # ^ |   0 can u explain more ?
•  » » » » 5 months ago, # ^ |   0 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. $\sum\limits_{1 \le l \le r \le n} f(l, r)$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 in c and 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: 371 = (4) + (56) + (45) + (4+56) + (56+45) + (4+56+45) 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: 284 = (7) + (32) + (45) + (7+32) + (32+45) + (7+32+45) 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! :)
 » 5 months ago, # |   0 weak pretest:(
 » 5 months ago, # |   +12 Is there any Pending System Testing now also?
 » 5 months ago, # |   0 Is this contest unrated? Because my rating is not updated yet, and my rating is less than 1600.
•  » » 5 months ago, # ^ |   0 Just wait, it should be updated soon
•  » » » 5 months ago, # ^ |   0 Oh.. Okay. Actually the hacking phase was finished. So thats why i asked.
•  » » » » 5 months ago, # ^ |   0 The thing is that the system's checking all solutions w/ hack-tests.
 » 5 months ago, # |   0 Im about task D. Why the answer for this test is 9, not 6? k = 1, n = 1, d1 = 3.
•  » » 5 months ago, # ^ |   0 Because for 6 dividers will be 3 and 2
•  » » » 5 months ago, # ^ |   0 Thanks
•  » » 5 months ago, # ^ |   0 For 6, the almost divisors will be 2, 3. Whereas 9 will only has 3 as almost divisors.
 » 5 months ago, # |   0 the first problem data is so easy I was hacked:(
•  » » 5 months ago, # ^ |   0 does it matter if the contests is unrated
•  » » » 5 months ago, # ^ |   0 Who said it's unrated?
•  » » » » 5 months ago, # ^ |   0 FBI
•  » » » 5 months ago, # ^ |   0 why and who said the contests is unrated
 » 5 months ago, # |   +2 Where is editorial ?? What about system testing ??
 » 5 months ago, # |   0 Is this contest unrated?Why I don't get rating changes?
•  » » 5 months ago, # ^ |   0 I don't know nobody said it's unrated
•  » » » 5 months ago, # ^ |   0 oh,thanks.It's too late to update the rating.
•  » » 5 months ago, # ^ |   0 System still calculating something, my standing first dropped from 500 to 1700, now it's changing between 1500-1700
•  » » » 5 months ago, # ^ |   0 Emm,I got it.Thanks.
•  » » » 5 months ago, # ^ |   +4 Your A got hacked by someone that's why your standing dropped from 500 to 1700.
•  » » » » 5 months ago, # ^ |   0 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
 » 5 months ago, # |   0 System Test has finished?
•  » » 5 months ago, # ^ |   0 No
 » 5 months ago, # | ← Rev. 4 →   0 Can someone post a solution in Python for "D — Almost All Divisors" without "Time limit exceeded on test 4"?Or show me error in my code https://codeforces.com/contest/1165/submission/54168485Updated 1: Fixed logical errors, still TLE
•  » » 5 months ago, # ^ |   +1 After if divisors[i] * divisors[~i] != guess: print(-1) breakYou should continue to see other test's instead you just break I think
•  » » » 5 months ago, # ^ |   0 Thanks, fix code https://codeforces.com/contest/1165/submission/54167593Still have "TIME_LIMIT_EXCEEDED"
•  » » » » 5 months ago, # ^ |   0 if not correct: continue This is wrong, because you don't print -1 before
•  » » » » » 5 months ago, # ^ |   0
•  » » » » » » 5 months ago, # ^ |   0 Submitting your code with pypy3 gives AC: 54169085. Though, I don't know why py3 is so slow in this task
•  » » » » » » » 5 months ago, # ^ |   0 Thanks!
•  » » » » 5 months ago, # ^ |   +1 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
•  » » » » » 5 months ago, # ^ |   0 Yeah, saw lots of similar algorithms in C++ that passed.
•  » » 5 months ago, # ^ |   +1 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
•  » » » 5 months ago, # ^ |   0 Amazing job!
 » 5 months ago, # |   0 I submit D at the last second，and failed because of my poor Broadband net T.T
 » 5 months ago, # |   +2 When system testing will be done for the contest??
•  » » 5 months ago, # ^ |   0 I think it's already done
•  » » 5 months ago, # ^ |   0 It is happening now.
 » 5 months ago, # |   +1 when will contest ratings are going to be given ?
 » 5 months ago, # |   +5 Is contest rated or not?
•  » » 5 months ago, # ^ |   +2 Yes Just who under 1600
 » 5 months ago, # |   +18 when will our ratings will come?
•  » » 5 months ago, # ^ |   -8 using cf-predictor you can know your rating change will be +139 if any solution don't get wa on system test.
•  » » » 5 months ago, # ^ |   0 Guess mine as well:)
•  » » » 5 months ago, # ^ |   +14 Yes i know that if my solutions will not get wa i will take about +139 but i want to take my +139
 » 5 months ago, # |   0 And Now whaaaaat!
 » 5 months ago, # |   0 When will the rating change come out?
 » 5 months ago, # | ← Rev. 2 →   0 MikeMirzayanov Ratings are not updated yet ...Pls look into the matter
 » 5 months ago, # |   0 this round unrated??
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 No, I think it's not as written in the rules...but it's very late this time..hope it will be updated soon.
•  » » 5 months ago, # ^ |   0 still some system test is going on
 » 5 months ago, # |   +3 admins, plz press the start system test button
•  » » 5 months ago, # ^ |   0 Admins busy, watching Game of thrones' Monday episode.
•  » » 5 months ago, # ^ |   0 system test feels like a pause.
 » 5 months ago, # |   0 RATING CHANGE IS OUT ! ON THE RIGHT OF STANDINGS !
•  » » 5 months ago, # ^ |   0 Check again -_-
•  » » » 5 months ago, # ^ |   0 Check it on friends Standings. It shows for me there.
•  » » 5 months ago, # ^ |   0 unrated?why?
 » 5 months ago, # |   0 even system testing is not done.
 » 5 months ago, # |   +7 Press the button.
 » 5 months ago, # |   +1 FINALLY !!!
 » 5 months ago, # |   0 I have a question in problem D, I have the same ideas sort the divisors make them all ans = ans * divisor[n] / __gcd(ans,divisor[n]) if ans = MaxDivisor , ans *= MinDivisor , then list all the divisors of new ans. 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
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 Just try for find countertests.133 4 9 Your output: 36Right answer: -1P.S. Try to check found number for correctness before printing.
•  » » » 5 months ago, # ^ |   0 Really Thanks . Now I have found My mistakes ！
 » 5 months ago, # |   +1 Why is the test so slow?
•  » » 5 months ago, # ^ |   +1 It often takes some (1 to 2) hours to run system test
 » 5 months ago, # | ← Rev. 2 →   0 Please tell why my approach for Problem E is incorrect?My Solution: https://ideone.com/tBe1upI 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.
•  » » 5 months ago, # ^ |   0 Make your code readable and ask again
•  » » » 5 months ago, # ^ |   0 Don't know why it was not readable. I made it public. Try this: https://ideone.com/tBe1up
•  » » » » 5 months ago, # ^ |   0 he means your code has too much define and others may not understand
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 It is not much of define.ll means long longand fl(i,a,b) means for loop with range [a, b)and slld(a) means scanf("%lld", &a)Just this.
•  » » » » » » 5 months ago, # ^ |   0 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)$
•  » » » » » » » 5 months ago, # ^ |   0 That's what I am asking. Why?
•  » » » » » » » » 5 months ago, # ^ | ← Rev. 3 →   0 $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$
•  » » » » » » » » » 5 months ago, # ^ |   0 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?
•  » » » » » » » » » 5 months ago, # ^ |   0 It's just a counterexample of a possible solution, so it's not hard to got that.
 » 5 months ago, # |   0 My rate didn't change yet Why?
•  » » 5 months ago, # ^ |   0 It has now! You gained 89 rating, congrats :)
•  » » » 5 months ago, # ^ |   0 ya thank u
 » 5 months ago, # |   0 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?
 » 5 months ago, # | ← Rev. 2 →   0 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/54228312whereas simply writing - a[i]=a[i]*(n-i)*(i+1) gets an AC
 » 5 months ago, # | ← Rev. 4 →   0 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
•  » » 5 months ago, # ^ |   0 Update: When I change from unsigned long long to long long, it magically AC,My code of ACHas 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 :)
 » 5 months ago, # |   0 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
 » 5 months ago, # |   0 I was the first one to solve problem E, yaaay! yaaay!