### vovuh's blog

By vovuh, history, 11 months ago, ,

Hi everyone! I'm glad to invite all of you to participate in Codeforces Round #574 (Div. 2) which will take a place in Jul/17/2019 17:35 (Moscow time).

This round is based on SIS team contest. You will be given 6 problems and 2 hours to solve them. This round will be rated for Div. 2 participants. In other words, this round will be rated for the participants with rating lower than 2100. As usual, participants from the first division are welcome to join out of competition.

Problems was invented and prepared by Nebuchadnezzar, Kurpilyansky, meshanya, TsarN, sava-cska, ima_ima_go and senek_k. I am just a coordinator of this round, I made a small amount of work such as English translations and editorials. I want to thank Mikhail MikeMirzayanov Mirzayanov for amazing systems Codeforces and Polygon, all authors of this great contest, KAN and _kun_ for help with difficulties estimating and choosing the problems and my dear friend Ivan BledDest Androsov for help with round preparation!

Good luck everyone and see only green system testing messages! :)

UPD: The scoring is 500 — 1000 — 1500 — (1000+1500) — 3000 — 3500.

UPD2: I would like to thank testers galloska, NatInTheHat and AlexPop28 for help and advices about the round!

UPD3: Editorial is published!

• +269

 » 11 months ago, # |   +109 It is usually a good contest if Vovuh is a coordinator. Good luck
 » 11 months ago, # |   +87
•  » » 11 months ago, # ^ |   +14 CF574
 » 11 months ago, # | ← Rev. 3 →   +48 Why some people participate out of competition even though their raiting is < 2100?
•  » » 11 months ago, # ^ |   +83 It will be fixed.
•  » » » 11 months ago, # ^ |   0 sir i submitted solution when 20-30 seconds remaining for problem D1 and D2 ,but it's not showing into mysubmissions please look into it.. i am on a very good broadband network, submit button was also working(not inactive) at that time. how it's possible??
•  » » » » 11 months ago, # ^ |   0 same problem with D1
 » 11 months ago, # |   -27 I hope to become cyan again.
 » 11 months ago, # |   -26 Will vovuh surpass pikmike
 » 11 months ago, # |   0 I hope to become white after this contest.
 » 11 months ago, # |   -12 I hope to become blue finally. :D
 » 11 months ago, # |   +26 I see people hoping to improve their colors (ratings). But I hope to have no WS, more ACs and a lot of fun :)
 » 11 months ago, # |   +14 Clashes with topcoder SRM 763!
 » 11 months ago, # |   -17 Some codeforces round will delay the start.I hope this round will not be like this.
 » 11 months ago, # |   +7 I'm noob so i wanna know what's the difference between div 2 and div 1 :D thanks
•  » » 11 months ago, # ^ |   +35 Generally,div.1 is harder than div.2div.2 C=div.1 Adiv.2 D=div.1 B ....
•  » » » 11 months ago, # ^ |   -20 Obviously.
•  » » » 11 months ago, # ^ |   +2 thank you bro
•  » » 11 months ago, # ^ |   0 There are three divisions (the more digit the easier problems): div3 — usually for pupils div2 — students div1 — high-skilled students, engineers etc.
 » 11 months ago, # |   +5 I'm sorry that I can take place.
•  » » 11 months ago, # ^ | ← Rev. 2 →   +22 you're sorry that you can take place!!!!???? Hey everybody, I'm sorry that I'm alive lol :P
 » 11 months ago, # |   +3 If i can solve Div 2 A,B,C regularly,can i ever become a specialist?
•  » » 11 months ago, # ^ |   0 yes, if u regularly solve 1,2,3 u can become specialist u can also get high rating in div 3
•  » » 11 months ago, # ^ |   +7 Absolutely yes!And if you are lucky enough,you can even become an expert.
 » 11 months ago, # |   +3 What is SIS contest?
•  » » 11 months ago, # ^ |   +5 I think Summer informatics School like Codeforces Round #530 (Div. 2).
•  » » 11 months ago, # ^ |   +5 SIS is for russian ЛКШ. It's a summer training camp in Russia
 » 11 months ago, # |   +4 What does it mean to coordinate a round ? What does the coordinator do ?
•  » » 11 months ago, # ^ |   +1 Coordinator finds mistakes in problems statements
 » 11 months ago, # |   +5 Will the pretests of problems in this contest be strong, like those in Educational Codeforces Round 68?
•  » » 11 months ago, # ^ |   +3 I agree that Educational Codeforces Round 68 had very strong pretests, which made hacking very difficult.
•  » » 11 months ago, # ^ |   +1 Oh, you are strong enough, and you won't be afraid of the strong pretests.
 » 11 months ago, # |   0 What will scoring distribution be like?
 » 11 months ago, # |   +9 Please let me see my repay! ->Codeforces Round #574 (Div. 2)
 » 11 months ago, # |   0 This round clashes with Codeforces Round #574.
 » 11 months ago, # |   +6 i will be cyan today....waiting for div3 vovuh (^.^)
•  » » 11 months ago, # ^ |   +32 i will be master today....waiting for div1 vovuh (^.^)
•  » » 11 months ago, # ^ |   +11 Challenge accepted :)
 » 11 months ago, # |   -10 A friend is saying me every contest "I'm gonna be specialist this contest" but he keeps dodging contests. This time again. Should I block him on messenger ?
 » 11 months ago, # |   0 What is SIS team contest ?? Can't find any relevant info about it on dd
•  » » 11 months ago, # ^ |   0 SIS stands for summer computer school, so SIS team contest means team contest held in SIS.
 » 11 months ago, # | ← Rev. 2 →   +35 500 — 1000 — 1500 — (1000+1500) — 3000 — 3500 Is it even div.2 ???
•  » » 11 months ago, # ^ |   +39 Easy div1 :)
•  » » 11 months ago, # ^ |   +23 Just one more div2D and this would've been a beautiful round with 2 divisions.
 » 11 months ago, # |   0 GOOd luc to all ! .. xd hope rating get
 » 11 months ago, # |   0 No Hackforces or Queueforces please!
 » 11 months ago, # |   0 Gray here I come!
•  » » 11 months ago, # ^ |   0 rating count begins from 1500 , if you perform well ,you can directly reach blue after first round, else you would be green
•  » » » 11 months ago, # ^ |   0 “ Else you would be green ”. You forgot one else if that he might be cyan if he writes contest not very bad)
•  » » 11 months ago, # ^ |   +24 Welcome to FairyForces :P
•  » » » 11 months ago, # ^ |   +2 That boy reminds me of Jace Beleren
 » 11 months ago, # |   +47 Sorry to say, but A is much to much text. That is not very motivating.
•  » » 11 months ago, # ^ |   +2 I didn't even understand the problem. Why the english is hard
 » 11 months ago, # |   +80 Nobody :Me:(5 mins before the contest): watching hunter_x_hunter(contest begins) : reading problem-A...(5 mins in contest) : still reading problem-A......(10 mins in contest) : (yawning) still reading-A.........(15 mins in contest) : watching hunter_x_hunter again
 » 11 months ago, # |   -18 Most Div3 contests have better and harder problems. Typeforces strikes again.
•  » » 11 months ago, # ^ |   0 naa. this was better 2222...
 » 11 months ago, # | ← Rev. 4 →   +15 is there someone else too or only me. till 20 min reading problem a.solved b in 5.again reading a for another 10.solved c .again reading a. solved d1.now still reading a... basically A ruined my mood .. :( .. what the question is saying. at one moment i thought of shut down and play pubg but b c d1 were easy ...&& also share approaches for d2 and e after the contest.Thanks.
•  » » 11 months ago, # ^ |   +1 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 ....
•  » » 11 months ago, # ^ |   0 oh shit i managed to solve only A after 40 min and got confused from B.
 » 11 months ago, # |   0 I think D2 worth more points. D1:750 D2:1750 would be better.
•  » » 11 months ago, # ^ |   0 Maybe there isn't too much difference if U think a lot about them:)
 » 11 months ago, # |   +15 F: another problem that Wikipedia makes a difference
•  » » 11 months ago, # ^ |   +5 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.
 » 11 months ago, # |   0 Woah, how to solve E? Is it some observation on the recurrence, or simply data structures? :O
•  » » 11 months ago, # ^ |   0 data structures
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Wow, really? I tried Seg2d but the time is too low. I tried Sparse Table 2d but the memory is too low... Which data structure have you used?
•  » » » » 11 months ago, # ^ |   +6 I used a 2D Deque
•  » » » » » 11 months ago, # ^ |   +5 Do you mean a 2D monotone queue?
•  » » » » 11 months ago, # ^ | ← Rev. 2 →   0 I use Sparse Table and AC
•  » » » » 11 months ago, # ^ | ← Rev. 3 →   0 You shouldn't save all powers of 2 in your sparse table, save just 2 greatest
•  » » » » » 11 months ago, # ^ |   0 though save all powers of 2 is also OK look at mine http://codeforces.com/contest/1195/submission/57270378
•  » » » » » » 11 months ago, # ^ | ← Rev. 3 →   +1 I had 2d sparse table in my solution, so 3000*3000*13 is too much)
•  » » » » » » » 11 months ago, # ^ |   0 no only 3000*13 and reuse it
•  » » 11 months ago, # ^ |   0
•  » » 11 months ago, # ^ |   0 Pretty much the same as https://discuss.codechef.com/t/chsqarr-editorial/12662
•  » » 11 months ago, # ^ |   0 I think it is using trees, but I failed to pass it in time.
•  » » 11 months ago, # ^ |   +3 Argh, deque. The tutorial is everywhere, but it's not that hard to not figure out, so just blame myself.Thanks abhayps! ;)
•  » » » 11 months ago, # ^ |   0 and only O(n*m*log(n+m))
•  » » 11 months ago, # ^ |   0 In fact only use Sparse Table can solve it. My submission http://codeforces.com/contest/1195/submission/57270378
 » 11 months ago, # |   +11 Spoiler E?
 » 11 months ago, # |   -12 For E, why doesn't a segtree solution pass?
•  » » 11 months ago, # ^ |   +19 Simply too costly, keep in mind that $n$ and $m$ may both reach $3000$.
•  » » » 11 months ago, # ^ |   0 Do I have to drop two logs?
•  » » » » 11 months ago, # ^ |   +21 Even one additional log into the $nm$ will cause TLE immediately. I tried.
•  » » » » » 11 months ago, # ^ |   +19 The proof of the pudding is in the eating. Thanks a lot.
•  » » » » » » 11 months ago, # ^ | ← Rev. 4 →   +21 Best solution (based on std::multiset) with O(nm log(n + m)) asymptotic 57272696Just new / delete optimisation with small test generation analysis (weak test cases)but not at the contest time...UPD: This is just an example of how to reduce the execution time of a program.
•  » » » » » 11 months ago, # ^ |   +3 My solution using std::priority_queue has one $\log$ in its time complexity. Some other solutions with $\log$ also passed system test.
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   0 I'm on the first page of fastest solutions with $O(nmlog(nm))$... Edit: my runtime increased by about 20% after systests so this statement is no longer true. It's still 420 ms though.
 » 11 months ago, # |   0 Can anyone share how to solve D1? I bruteforced it and got tle in tc7.Also A took me so much time to solve like 3*(time req for B). It was really demotivating :(
•  » » 11 months ago, # ^ |   0 -First i solved examples on paper, then recognized pattern. Result=summation(f(a[i],a[i])*n
•  » » » 11 months ago, # ^ | ← Rev. 2 →   0 Wow! Was it that simple.
•  » » 11 months ago, # ^ |   0 My solution to D1 is: Work out how many times each digit appears in each position. Add the digits in each position. 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.
 » 11 months ago, # |   +1 How to solve D2 ?
•  » » 11 months ago, # ^ | ← Rev. 3 →   +4 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.
 » 11 months ago, # |   +4 Problem D: So the digit combining function helped the students find the coordinates of the treasure?
 » 11 months ago, # |   0 Where am i wrong.Can someone please help? For C problem https://codeforces.com/contest/1195/submission/57227259
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 change int to long long  vector a(n,0),b(n,0),dp1(n,0),dp2(n,0); 
•  » » » 11 months ago, # ^ |   +2 Such a silly mistake. Spent 45 mins trying to find the error. So sad.
•  » » » » 11 months ago, # ^ |   -13 typedef int long long;
 » 11 months ago, # |   0 Why didn't you send a single announcement that you updated problem B statement? I didn't refresh and wasted a lot of time with it.
 » 11 months ago, # | ← Rev. 3 →   -21 it make the chinese stay up late
 » 11 months ago, # |   +23 Nice round! I solved two problem but didn't have idea of problem C. Does someone teach me how to do?
•  » » 11 months ago, # ^ |   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<
•  » » 11 months ago, # ^ | ← Rev. 2 →   +13 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.
•  » » » 11 months ago, # ^ |   +1 simply 2 variables would have been enough i think?
•  » » » » 11 months ago, # ^ |   +3 Yes x=A[0],y=B[0] loop(1,n){ temp=x; x=max(x,b+A[i]); y=max(y,temp+B[i]); } 
•  » » 11 months ago, # ^ |   0 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.
•  » » » 11 months ago, # ^ |   0 I don't get the exact logic of "There's no point in skipping 2 elements". I think I can get a feel that at any state we have two paths to go — one from taking just next element and the other is from taking next to next element but I can't prove it. I recurse for all the states with memoization but got TLE only because your logic works but I couldn't prove why?
•  » » » » 11 months ago, # ^ | ← Rev. 5 →   +1 prabhat7298 there is nothing to prove in it.take this example : 1 2 3 75 6 8 9taking index — 1 based. suppose we are at column 4, and we choose element from row 1 that is 7. now we must choose a previous element from row 2. suppose u skip 2 elements and choose 5 from 2nd row. now to choose 7 u can go through 5 -- 2 -- 8 -- 7 . since the numbers are positive we will only add +ve numbers to our answer. if we skip two elements we can always form a ziz zag path. so it would be optimal for us to not skip 2 elements.
•  » » » » » 11 months ago, # ^ | ← Rev. 2 →   0 Thanks atlasworld
•  » » 11 months ago, # ^ |   0 You can use dynamic programming for that one.Let C(r, c) be the optimal cost to choose the team if we begin our choice from row r and have c individuals in each row. Then:C(1, 1) = H(1, 1) C(2, 1) = H(2, 1) C(1, c) = max(H(1, c) + C(2, c-1), C(1, c-1)) C(2, c) = max(H(2, c) + C(1, c-1), C(2, c-1))Once we've built our array, the solution is just max(C(1, n), C(2, n)).
•  » » 11 months ago, # ^ |   +3 Thanks you guys, I will think how to do it with your tutoral. Hope me I will get accept :D
•  » » 11 months ago, # ^ |   0 You can refer to my submission here. It is an easy application of dp
 » 11 months ago, # | ← Rev. 2 →   0 I'm so sad if just 3 minutes I could've solved D2 ugh stupid bug lost 30 more rateEdit : it was WA lol I'll never assume my solution is right unless I see the fukin accepted
 » 11 months ago, # |   -18 After lot of searching, I found problem C at https://www.geeksforgeeks.org/maximum-sum-from-three-arrays-such-that-picking-elements-consecutively-from-same-is-not-allowed/ only to find out the code does't give correct output on pretest 2. Tried to fix it, failed.RIP rating.
 » 11 months ago, # |   +113
 » 11 months ago, # |   +15 Very good round!! First round to solve 4 problems. I usually solved 2 or 3
•  » » 11 months ago, # ^ |   +35 I think it's better to solve few harder problems, rather then wasting time implementing easy ones. I haven't liked it -_-
•  » » » 11 months ago, # ^ |   0 Agreed
•  » » 11 months ago, # ^ |   0 Congrats!
 » 11 months ago, # | ← Rev. 3 →   0 Is it possible to solve B mathematically? To solve this system of equations: 1. x(x + 1)/2 - y = k 2. x + y = n which gives y^2 - y(2n + 3) + n^2 + n - 2k = 0 and solve this quadratic equation for y. Then, check whether y fits [0, n]. It fails on the 11th test, what have I done wrong?
•  » » 11 months ago, # ^ |   0 Do $int(sqrt(...))$
•  » » 11 months ago, # ^ |   +1 You can put $y = n - x$ which gives you $(x^2 + x)/2 + x - n = k$. It's quite simple to solve :)
•  » » 11 months ago, # ^ |   +3 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; } 
•  » » » 11 months ago, # ^ |   0 Standart C++'s sqrt() gives AC.
•  » » » » 11 months ago, # ^ |   0 Hmm, yes it does... But, anyway — sqrt isn't precise =)
•  » » » » » 11 months ago, # ^ | ← Rev. 3 →   0 Ofc, but as condition says It's guaranteed, that for the given n and k the answer always exists.If it hadn't guaranteed, sqrt() probably would have got WA.
•  » » » » » » 11 months ago, # ^ | ← Rev. 4 →   +3 Try to avoid using fractional types if it is possible toFor example in this problem you can iterate over x from 0 to C and try each of them to fit your formula (here C is some constant that x will never exceed e.g. 10^5)
•  » » 11 months ago, # ^ |   0 Any other non-math solution?) my solution: 57211560
•  » » 11 months ago, # ^ |   0 Ohhh I see. My Equations were as follows : k = (n-x+1)*(n-x)/2 - xWhere x was the number of actions where she ate a candy and n-x was the number of adding candy operations. So basically solve for x. I used binary search : 57215407
•  » » 11 months ago, # ^ |   +6 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:)
•  » » 11 months ago, # ^ |   0 x^2 + 3x -2(n + k) = 0its 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.
 » 11 months ago, # |   0 can someone explain the first sample in D1 please ?!
•  » » 11 months ago, # ^ |   0 I think that you forgot f（45，45）=4455 also makes sense.
•  » » 11 months ago, # ^ | ← Rev. 4 →   0 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) = 4455Sum these up, you'll get 26730.Hope this explains :)
•  » » » 11 months ago, # ^ |   0 oh shit !what got to my mind when i read this : $∑ni=1∑nj=1f(ai,aj)$ is 12,12 12,33 12,45 33,33 33,45 45,45really sad !
•  » » 11 months ago, # ^ |   +1 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])
 » 11 months ago, # |   0 Couldn't solve D2 because I forgot to multiply by 2 :/ This really sucks
 » 11 months ago, # | ← Rev. 2 →   +5 Lucky me.
•  » » 11 months ago, # ^ |   0 Same — fellow newbies represent!
 » 11 months ago, # | ← Rev. 3 →   +31 Problem F,why the sample input different with the image. 3 2 2 1 2 2 1 but the image is: ------- | / | / | / | / |/ why??????
 » 11 months ago, # | ← Rev. 3 →   +9 Here is an interesting approach for problems like today's E. It provides an $O(n)$ solution to the minimum element on all subarrays of length k problemLinkDo this for every row with a sliding window (two pointers) of length b, and then with these results do it again for every column with a sliding window of length a (or vice-versa)I tried it using a map, but it seems $O(n\cdot m\cdot logn)$ is too much this time :(
 » 11 months ago, # |   -8 If I submit two correct solutions in different time, which one is scored? Latest one or first one? I miss submit D2 solution to D1...
•  » » 11 months ago, # ^ |   0 last correct submission is considered.
•  » » » 11 months ago, # ^ |   -17 OMG... It's unfair
 » 11 months ago, # | ← Rev. 2 →   0 Why is the TL of E so tight? Even O(n * m * log(m)) solution is not passing the time limit :(
•  » » 11 months ago, # ^ |   +9 The problem E.aka TLE :D
•  » » 11 months ago, # ^ |   +6 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.
•  » » 11 months ago, # ^ |   0 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.
 » 11 months ago, # |   +16 Wow, another ImplementationForces round, so cool (yes!)
 » 11 months ago, # |   0
•  » » 11 months ago, # ^ |   0 deleting the comment lines and thinking that it will be missed out from the codeforces users :D:
•  » » » 11 months ago, # ^ |   0 It definitely missed the plagiarism check though.
•  » » » » 11 months ago, # ^ |   0 how the system did not detect it? it is kinda weird
•  » » 11 months ago, # ^ |   +4 MikeMirzayanov Please look into this.
•  » » 11 months ago, # ^ |   0 Both from Hangzhou, China. Coincidence? I don't think so ...
•  » » 11 months ago, # ^ |   0 ???I think I don't give this guy my code.Anyway,I find the similar problem of this round's EMight he use my code by the similar problem.So Why [user:ljc2002]not skipped?
•  » » » 11 months ago, # ^ | ← Rev. 2 →   +40 hello . I'm ljc2002 and I want to explain why my code is very similar to yours.The problem E may be a combination of two subproblems(the "sliding window" ，滑动窗口)。But, I completely copied the solution to this topic into this question. However，the author of the problem I referenced participated in the competition again.So it may led to this misunderstanding.I’m terribly sorry about this thing. I hope to get your understanding.I emphasize one point,the code of ours is done by ourselves.And,there is no any communication in the examination.大家好，我是ljc2002，我想和大家(特别是对ChthollyTree同学)解释一下这次事件的原因。problem E是由两次的"滑动窗口"组合而来的，但是我使用了某篇题解的代码来解决这个问题，但是，这篇题解的作者可能也参加了这个比赛，所以就导致了这样的误会。我对ChthollyTree同学感到非常抱歉，并且希望得到他的谅解。我指出一点，两道题目的代码是由我们两个自己分别独立，完成的。不存在考场上的交流
•  » » » » 11 months ago, # ^ |   +13 复用已有代码是符合规范的，没必要道歉。
•  » » » » 11 months ago, # ^ |   +11 I believe that ljc2002 can solve problem by himself.
 » 11 months ago, # |   +3 In round #574 (div 2), problem D1 I had submitted my solution with 10-20 seconds remaining and it was in the queue for verdict but suddenly the contest was over and I was redirected to the home page of contest. Please look into the problem.
 » 11 months ago, # |   0 editorial?
 » 11 months ago, # | ← Rev. 2 →   0 Idea for the problem D1?
•  » » 11 months ago, # ^ |   +7 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.com/contest/1195/submission/57225770
•  » » » 11 months ago, # ^ |   0 What about d2. How to solve it.
•  » » » » 11 months ago, # ^ |   +1 It's very similar. You just have to be careful about the weights in the 10's expansion that you assign to the longer number.For this, my approach was to maintain a frequency array having a[i] as the number of elements with length i.Now, for each number in your input array, traverse its 10's expansion. If you're at the ith digit then surely, all numbers with >=i digits will ensure that this ith digit will play out similarly as in D1. Only for numbers with 
•  » » » » » 11 months ago, # ^ |   0 during 10's expansion in both d1 and d2, will there be an issue of carry generated?
•  » » » » » » 11 months ago, # ^ |   0 It's always taken care of on its own. For ex., when you're doing 98+76, you're essentially doing (9*10)+(8*1)+(7*10)+(6*1). Any generated carry will be taken into account in the calculations by itself.
 » 11 months ago, # |   +14 Editorials?
 » 11 months ago, # |   0 can any one explain test cases in (problem D1) >> thanks ..
•  » » 11 months ago, # ^ | ← Rev. 3 →   0 312 33 45you 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=3or just:f(a1,a1)*n + f(a2,a2)*n + f(a3,a3)*n
 » 11 months ago, # |   0 What was the correct approach for A? Many people (including myself) got WA in test 13 :/
•  » » 11 months ago, # ^ |   +6 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!!!!
•  » » » 11 months ago, # ^ |   +6 Nice answer, fits the style of the question ;)
 » 11 months ago, # |   -13 Everyone has done problem C as bottom-up approach if anyone wants top-down approach then here it is #57250417
 » 11 months ago, # |   0 Can anyone xplain the logic of problem C?
 » 11 months ago, # |   +6 It's been almost 10hrs since the contest ended. Why isn't the editorial released yet ? Isn't it prepared beforehand ?
•  » » 11 months ago, # ^ |   -21 Here is the Editorial
 » 11 months ago, # |   0 My submission for D1 gives a WA verdict for the test 5 1000000000 1000000000 1000000000 1000000000 1000000000. But the answer matches the expected output in my system. Any help would be appreciated. Link to my submission https://codeforces.com/contest/1195/submission/57257009
•  » » 11 months ago, # ^ |   0 Try debugging your code through 'Custom invocation' feature of Codeforces.
 » 11 months ago, # |   +3 Where are the EDITORIALS?
 » 11 months ago, # | ← Rev. 5 →   0 can someone pls tell me where i went wrong. It is for question B,I used a function similar to binary search one and after 10 pretests I got wrong at 11th one. //int ans(int l, int r) { if (r>=l){ int idx = l + (r — l) / 2; long long int o= idx*(idx+1)/2;  if (o-(n-idx)==k) return idx; else if (o-(n-idx)>k) return ans(l,idx-1); else return ans(idx+1,r); }return -1;} // the following test case gives me wrong answer. 999999994 108004280
•  » » 11 months ago, # ^ | ← Rev. 2 →   0 Overflow. The right side is calculated first. (int)*(int) -> overflow.
•  » » » 11 months ago, # ^ |   0 thnk u and also bro I dont know how to solve this issue . could u pls tell me how to solve this??
•  » » » » 11 months ago, # ^ |   0 "long long idx" or "1ll*idx*(idx+1)/2"
•  » » » » » 11 months ago, # ^ |   0 either of these things doesnt help. still getting wrong answer :(
•  » » » » » » 11 months ago, # ^ |   0
•  » » » » » » » 11 months ago, # ^ |   0 yeah, i used long long unsigned int for o which gave 6 as answer for 5 0, while the answer should have been 3. when i removed 'unsigned' it somehow gave right answer and my code got accepted. thank you.
 » 11 months ago, # |   +5 How to solve E
•  » » 11 months ago, # ^ |   +1 Consider the row and the column respectively. Let $r[i][j] = \min(h[i][j], h[i][j+1], \dots, h[i][j+b-1])$ $c[i][j] = \min(r[i][j], r[i+1][j], \dots, r[i+a-1][j])$The answer is obvious. $\sum_{i=1}^{n-a+1}\sum_{j=1}^{m-b+1} c[i][j]$Now the problem is to find the minimum value of fixed-length subarrays in a sequence, and it can be solved in linear time with sliding window(or monotone queue)method.
 » 11 months ago, # |   +13 Why is the meaning of question A so difficult? 0.0
 » 11 months ago, # |   0 Can anyone suggest a testcase to make this solution fail? https://codeforces.com/contest/1195/submission/57264099
•  » » 11 months ago, # ^ |   +3 You can even take look at this one! I've checked your solution for all valid inputs such that $N \le 10^4$ and It was okay (I'm not sure that there exists any counterexample).This problem can be solved using the quadratic equation (submission).
•  » » » 11 months ago, # ^ |   +5 Yeah I know the solution, just wanted to find the counter example for this. Thanks anyways :)
•  » » 11 months ago, # ^ |   +11 I don't think you will find one. The correct solution is: n + floor(3 -sqrt(9 + 8*(k+n))/2 (actually for valid test cases the floor function doesn't change anything).This code does: n - floor((1 + sqrt(1+8*(k+n))/2) +1 If we say x =8*(k+n) then the difference between these is: d(x) = floor((3 -sqrt(9+x))/2) + floor((1+sqrt(1+x))/2) -1 = floor((1-sqrt(9+x))/2) + floor((1+sqrt(1+x))/2)) For x>=0 we have 0 < sqrt(9+x) - sqrt(1+x) < 2 so d(x) is either 0 or 1.For valid testcases x is an even number such that 9+x is an perfect square.If 9+x is a perfect square and x > 0 then 1+x isn't, so d(x) will be 0. In other words, the code will get the correct answer for all valid testcases, even if it does it in a slightly strange way.
 » 11 months ago, # |   +4 Hi, these 2 people have exact same code for D2 all they did was just rename the variables and added spaces and random ass functions which have no job in the code. Is this allowed to do so? it can't be coincidence that their code is exact same except the variable names.BTW they from same college too.Sad
•  » » 11 months ago, # ^ |   -24 Cheating on codeforces is quite common. More shameful thing is that MikeMirzayanov doesn't take any serious action. I only remember one time when he responded. Otherwise he has nothing to do. But if you are red he might respond. Example when he even responded a blog asking for debugging help
•  » » » 11 months ago, # ^ |   +16 I guess we should not blame anyone for that, Codeforces contest frequency is so high, all the people who are providing these for free,work very hard .Not because of money,but because they love this work.if some people cheated it's shame on them.but I want to ask why are you wasting your time .I guess codeforces have plagiarism checker it might be slow.Think it as learning platform,its not some real exam.its the platform u make mistakes and learn. Time is valuable resource invest it in right direction, try to solve hard problems instead of looking into such matters, it's for your benefit.no offense.
•  » » » » 11 months ago, # ^ |   0 Hi thank you for your suggestion,I agree with your views on how busy the platform is. I just wanted to clarify that I'm not obsessed with checking if the 2 users cheat or not. I was just reading their answers for method to solve a problem and found that they were same. If you know a user who gives good concise answers to problems in contests you can share their handle please. Thank you.
 » 11 months ago, # |   +6 Will the editorial be published for this round, Vovuh?
 » 11 months ago, # |   0 please ,publish editorial fast ....
 » 11 months ago, # |   +37 The editorial will be within one-two hours. I almost done with it. Sorry for delay.
•  » » 11 months ago, # ^ |   +12 You are really a good author and coordinator. Thank you!
 » 11 months ago, # | ← Rev. 3 →   0 following is the solution for B in O(1) time complexity:-) O(1) solution for B expressions are : 1. (x*(x+1))/2 - y = k ( here x is the no of times she put candies) 2. x+y = n 3. let no of candies eaten = req; solve 1 and 2 equations . we obtain a quadratic eqn in x , n and k as given below - quadratic eqn : x^2 + 3*x -2*(n+k) = 0 solve this equation and take positive root . after finding the root(x) .. now we have to subtract this from n since we need how many she ate .. as we know no of candies eaten(req) + no of candies put(x) = no of chances(n) thus req = n-x. this is the ans. for code click this link -> https://codeforces.com/contest/1195/submission/57284355 
 » 11 months ago, # |   0 How to solve F
 » 11 months ago, # | ← Rev. 4 →   0 Can anyone help me indicate why this situation happens?They are both my submissions (in practice) for problem E (https://codeforces.com/contest/1195/problem/E) in this contest.They are exactly the same code yet submitted with different compilers, e.g., GNU C++11 and MS C++ 2017. However, the one submitted using GNU C++11 got wrong answer with the output 0 for the first system test while got accepted if submitted using MS C++ 2017.
 » 11 months ago, # |   0 What wrong with my submission on test case 5 D2 problem. Thanks in advance!https://codeforces.com/contest/1195/submission/57376447
 » 11 months ago, # |   +1 Hard div.2(A) problem ever:)
•  » » 10 months ago, # ^ |   0 Maybe you would like to know CF200A :D
 » 10 months ago, # |   0 I know this is really late but test cases for F are weak; solutions which use doubles to store atan2(example: 58176014) pass system tests even though the following test case makes them output 3 instead of 5: 2 3 0 0 1000000000 999999999 0 1 3 0 0 999999999 999999998 0 1 1 1 2 `
•  » » 10 months ago, # ^ |   0 Thank you! Added your test into testset to prevent accepting such solutions in the future.