vovuh's blog

By vovuh, history, 3 months ago, translation, ,

UPD: Pay attention to the changed start time of the competition.

<almost-copy-pasted-part>

Hello! Codeforces Round #627 (Div. 3) will start at Mar/12/2020 16:05 (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. 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 Daria ZeroAmbition Stepanova, Mikhail pikmike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

</almost-copy-pasted-part>

Thanks to Artem Rox Plotkin and Dmitrii _overrated_ Umnov for help with testing the round!

UPD2: Editorial is published!

• +203

 » 3 months ago, # |   +25 "You will be given 6 or 7 (or 8) problems and 2 hours to solve them."Does this means that the problems haven't been decided ?
•  » » 3 months ago, # ^ |   +83 No, Because it is almost-copy-pasted-part
•  » » 3 months ago, # ^ |   -6 The numbers of questions has been decides, maybe they will have a little change before contest.
•  » » 3 months ago, # ^ |   0 May not. I think it's just a general idea so that almost every contest could use this template. ^-^
 » 3 months ago, # |   +16 Which contest coincided with the original timing?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +38 Reply code challenge : https://codeforces.com/blog/entry/74502
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 sorry, misunderstanding from sentence!
•  » » » 3 months ago, # ^ |   0 The time that this contest was supposed to start. The contest was supposed to start 1.5 hour later.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +7 Does that matter?Edit: Well, I mean, do the time zones matter?
 » 3 months ago, # |   +33 Good luck everyone !!!
•  » » 3 months ago, # ^ |   0 Athena Chu <3
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 haha
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 The same to u <3
•  » » » 3 months ago, # ^ |   0 -.- <3
•  » » 3 months ago, # ^ |   0 Dont show that corona face
 » 3 months ago, # |   -20 Who else is hyped for Div 3 because can't get good rating from Div 2?
•  » » 3 months ago, # ^ |   +2 getting a good rating in Div3 is even tougher :(
 » 3 months ago, # | ← Rev. 2 →   -10 What does mean by "almost-copy-pasted-part"?
•  » » 3 months ago, # ^ | ← Rev. 3 →   +5 The "almost-copy-pasted-part" is almost equal in the announcements of most contests
 » 3 months ago, # |   0 So excited for first contest. Good luck everybody!
•  » » 3 months ago, # ^ |   0 Good luck and high rating <3
•  » » » 3 months ago, # ^ |   +3 Thank you so much <3
•  » » » » 3 months ago, # ^ |   0 Just solved three problems
 » 3 months ago, # |   -42 How was your Holi celebration ? Was anyone not able to play due to coronavirus threat?
•  » » 3 months ago, # ^ |   +5 So many downvotes :( . I haven't asked anything wrong :( .
•  » » » 3 months ago, # ^ |   +14 your question was right but on the wrong platform.
 » 3 months ago, # |   0 2 hours in Div 3 and 4 hours in Reply Code Challenge, it's going to be an exhaustive day.
•  » » 3 months ago, # ^ |   0 I think you are highely inspired by TVF Pitchers.
•  » » » 3 months ago, # ^ |   0 True
 » 3 months ago, # |   0 Hope that I can solve A-B-C.Good luck guys <3
•  » » 3 months ago, # ^ |   -17 stfu
 » 3 months ago, # |   0 well，is there anyone know what's the name of the other contest（1.5hours later） after this contest？
•  » » 3 months ago, # ^ |   +1 Reply code challenge : https://codeforces.com/blog/entry/74502
•  » » » 3 months ago, # ^ |   0 Thank you so~much
•  » » » » 3 months ago, # ^ |   0 You're welcome
 » 3 months ago, # |   -6 Hope to become expert after this round
•  » » 3 months ago, # ^ |   +13 No, you won't
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Yes, I will.
•  » » » 3 months ago, # ^ |   0 I think ... He will :)
•  » » 3 months ago, # ^ |   0 Would you like to share your secrets... with us :)
 » 3 months ago, # |   +4 I hope to get blue in this contest
 » 3 months ago, # |   0 I don't think i can solve over two problems...
•  » » 3 months ago, # ^ |   +9 if you think you can't, so you can't.Believing in yourself is the first step to success.
•  » » 3 months ago, # ^ |   0 you were wrong
 » 3 months ago, # |   +8 Hope problems will not be indirect like this
•  » » 3 months ago, # ^ |   +6 Well, you can jump through the centre.
•  » » » 3 months ago, # ^ |   +3 Ya I can for that I require wings of Advanced mathematics and data structures. Anyways Good Luck to everyone for the contest.
 » 3 months ago, # |   +5 Bad luck for me becoz i can't attend this contest.
 » 3 months ago, # | ← Rev. 3 →   +1 .
 » 3 months ago, # |   +2 Hope i will be green after this round :))
•  » » 3 months ago, # ^ |   +1 same
 » 3 months ago, # |   +3 I use this site during contest :)
•  » » 3 months ago, # ^ |   0 really that's i waited for
 » 3 months ago, # |   +64 I got logged out 2-3 times during contest. Did it happen to anybody else or problem at my end?
•  » » 3 months ago, # ^ |   +5 Same here :(
•  » » 3 months ago, # ^ |   0 Glad to see I wasn't the only one who faced the same issue.Made me wonder if my account got hacked or something :/
•  » » 3 months ago, # ^ |   0 Well, the thing you had also happened to me, so I felt unhappy during the contest:(
•  » » 3 months ago, # ^ |   +1 Yes,this happened with me also. Maybe a coincidence, but it happened mostly when I clicked submit button.
•  » » 3 months ago, # ^ |   +2 Me too. I thought it was my browser problem or something like that and erased cache and it happend again... :(
•  » » 3 months ago, # ^ |   0 same here, maybe it's the browser's problem or something else, idk
•  » » 3 months ago, # ^ |   0 Same to me ((
 » 3 months ago, # |   +17 I feel it difficult to understand some of the problem statements,does anyone feel the same?
•  » » 3 months ago, # ^ |   +8 me!!!
•  » » 3 months ago, # ^ |   +11 Yes :/
•  » » 3 months ago, # ^ |   +11 me，especially problem a
•  » » » 3 months ago, # ^ |   0 F too
•  » » » 3 months ago, # ^ |   0 Me too ,I got such penalties!
•  » » » 3 months ago, # ^ |   0 statement of A was simple for those who played tetris before.
•  » » 3 months ago, # ^ |   +22 yeap, understanding Problem A was harder than solving it
•  » » » 3 months ago, # ^ |   0 Couldn't agree more
•  » » » 3 months ago, # ^ |   0 True that
•  » » » 3 months ago, # ^ |   0 Still don't get it ;/[100] step1) replace ai with ai+2 = [102] step2) replace ai with ai-1 then how [102] = [0] ?
•  » » » » 3 months ago, # ^ |   0 If different between any two ai's is odd then it's not possible to achieve them at equal level(0) ..
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I took maximum time on A
•  » » 3 months ago, # ^ |   +7 problem E is difficult to understand
•  » » 3 months ago, # ^ |   +2 E was the most difficult to understand. I understood A maybe because I had played that game before.
•  » » 3 months ago, # ^ |   0 Exactly!E was really confusing, in the examples they didn't even specify the mod h part
•  » » 3 months ago, # ^ |   0 me
 » 3 months ago, # | ← Rev. 2 →   +23 A Done B Done C Done Me Done Nice Contest
 » 3 months ago, # |   +5 Good to see that vovuh is the writer.
 » 3 months ago, # | ← Rev. 2 →   0 The problems are too easy so that more than 500 participants solved all the problems
 » 3 months ago, # | ← Rev. 2 →   0 Guys,I have a problem! do not have a point of 1900 or higher in the rating Is that means standings in contest is different from your rank which is the final standings?
•  » » 3 months ago, # ^ |   +4 The contest will be rated for those participants who have a rating below 1600. However, participants with rating greater than or equal to 1600 can participate unofficially. Separate standings are available for official and unofficial+official participants.
•  » » » 3 months ago, # ^ |   -8 I get it.Thanks!
•  » » » » 3 months ago, # ^ |   0 You're welcome
 » 3 months ago, # |   +44 During the contest, I automatically got logged out from codeforces. I had two tabs of codeforces open in firefox. When I tried to submit I got to know I am not logged in. This has happened thrice. Is it normal/minor bug or there is some other problem ?
•  » » 3 months ago, # ^ |   +4 Even I faced this issue around 4-5 times.
•  » » 3 months ago, # ^ |   0 I didn't count but it was infuriating.
 » 3 months ago, # |   +1 For those who cannot understand what is subgraph and subtree. Click :(
 » 3 months ago, # |   +19
•  » » 3 months ago, # ^ |   +8 Faster than Lightening! Thanks!
•  » » 3 months ago, # ^ |   +8 Thank you
•  » » 3 months ago, # ^ |   +39 .
•  » » 3 months ago, # ^ |   0 There's an easier solution for C BTW. Just count max length of continuous L's in the string.
 » 3 months ago, # |   0 Thank you very much for the rating friendly contest
 » 3 months ago, # | ← Rev. 9 →   +2 How to solve D ;-; My approachSplit array into negative-diff (A), positive-diff (B), zero-diff (C) We have ai + aj > bi + bj <=> ai - bi > -(aj - bj) <=> ci > -cj (where ck = diff(ak, bk) = ak - bk for all k E [1, n]) => Count number of sum ci + cj > 0 Let res = |A| * (|A| - 1) / 2 + |A| * |C| // sum of them is always >= 0 for i = 0 -> |A| - 1 -- while (j + 1 < |B| && B[j + 1] < A[i]) ++j // move the pointer until the next element >= current -- res = res + j output << res  My source code#include #include #include using namespace std; typedef long long ll; typedef vector vi; int main() { int n; cin >> n; /// Count ai - bi > bj - aj // ci > -cj /// 0 3 -2 5 -1 /// -2 -1 /// 0 3 5 vi a(n); for (int i = 0; i < n; ++i) { int x; cin >> x; a[i] = x; } for (int i = 0; i < n; ++i) { int x; cin >> x; a[i] -= x; } int zero = 0; vi nega, posi; for (int i = 0; i < n; ++i) { if (a[i] < 0) nega.push_back(a[i]); if (a[i] > 0) posi.push_back(a[i]); if (a[i] == 0) zero++; } nega.insert(nega.begin(), 0); int p = nega.size(); int q = posi.size(); sort(nega.begin(), nega.end(), greater()); sort(posi.begin(), posi.end(), less()); /* for (int i = 0; i < p; ++i) cout << nega[i] << ' '; cout << endl; for (int i = 0; i < q; ++i) cout << posi[i] << ' '; cout << endl; cout << endl; */ if (posi.empty()) { cout << 0; return 0; } if (posi.size() == n) { cout << 1LL * n * (n + 1) / 2; return 0; } ll res = q * (q - 1) / 2 + q * zero; for (int t = 0, i = 0, j = 0; i < q; ++i) { while (j + 1 < p && -nega[j + 1] < posi[i]) ++j; res += j; } cout << res; return 0; } Found Mistake: (wrong formula) cout << 1LL * n * (n + 1) / 2; -> cout << 1LL * n * (n - 1) / 2; Found Mistake: (integer overflow) ll res = q * (q - 1) / 2 + q * zero; -> ll res = 1LL * q * (q - 1) / 2 + 1LL * q * zero; AC Code (Spoiler warning)#include #include #include using namespace std; typedef long long ll; typedef vector vi; int main() { int n; cin >> n; /// Count ai - bi > bj - aj // ci > -cj /// 0 3 -2 5 -1 /// -2 -1 /// 0 3 5 vi a(n); for (int i = 0; i < n; ++i) { int x; cin >> x; a[i] = x; } for (int i = 0; i < n; ++i) { int x; cin >> x; a[i] -= x; } int zero = 0; vi nega, posi; for (int i = 0; i < n; ++i) { if (a[i] < 0) nega.push_back(a[i]); if (a[i] > 0) posi.push_back(a[i]); if (a[i] == 0) zero++; } nega.insert(nega.begin(), 0); int p = nega.size(); int q = posi.size(); sort(nega.begin(), nega.end(), greater()); sort(posi.begin(), posi.end(), less()); /* for (int i = 0; i < p; ++i) cout << nega[i] << ' '; cout << endl; for (int i = 0; i < q; ++i) cout << posi[i] << ' '; cout << endl; cout << endl; */ if (posi.empty()) { cout << 0; return 0; } if (posi.size() == n) { cout << 1LL * n * (n - 1) / 2; return 0; } ll res = 1LL * q * (q - 1) / 2 + 1LL * q * zero; for (int t = 0, i = 0, j = 0; i < q; ++i) { while (j + 1 < p && -nega[j + 1] < posi[i]) ++j; res += j; } cout << res; return 0; } 
•  » » 3 months ago, # ^ |   +3 You can use binary search. create a diff array such that diff[i] = teacher[i]-student[i]. sort this array. at a particular point i calculate how much you'll need to compensate for when you choose j. e.g if teacher[i]-student[i] = -2. then we know we need diff[j] >= 3, so as to make teacher[i]+teacher[j] > student[i] + student[j].you can easily binary search this value in diff array.
•  » » » 3 months ago, # ^ |   0 I had the same logic, but failed somewhere in implementation i guess. Did you get AC with this logic?
•  » » » » 3 months ago, # ^ |   0 Yup ... I had the same logic... ACed
•  » » » » » 3 months ago, # ^ |   0 I have implemented same logic in java but getting TLE in 24 testcase. but it is taking nlog(n) time. Your text to link here...
•  » » » » » » 3 months ago, # ^ |   0 Change your int c[] to Integer c[] My submission of your code: 73104414
•  » » » » » » » 3 months ago, # ^ |   0 Thanks a lot, buddy. What is the reason?
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Yes, I had AC
•  » » 3 months ago, # ^ |   +2 Let $c_i = a_i - b_i$. Now you have to count the number of pairs of $c_i$ with the positive sum. It can be done in $O(n log n)$ with binary search.
•  » » » 3 months ago, # ^ |   0 Can I ask why my approach failed ? T_T
•  » » 3 months ago, # ^ |   +1 Create an array of differences of a[i]-b[i] then use lower bound to find good pairs for negative numbers and zero numbers and for positive use binomial coefficient (ncr).
•  » » » 3 months ago, # ^ |   0 What formula should I use ?
•  » » 3 months ago, # ^ |   +10 I used PBDS.
•  » » » 3 months ago, # ^ |   0 how?
•  » » » » 3 months ago, # ^ |   0 Let's just iterate over the array from the start, and since we need to find unordered pairs, so for a particular i, we need all elements before it such that: ai — bi > bj — aj or Let's denote bj — aj as val, then we need all such elements where : val < ai — bi So PBDS on pair of elements acts like a multiset with additional feature ,giving count of elements less than x too.So use that function for each i and get count of elements less than {ai-bi-1,inf}, and add it to answer and insert pair {bi-ai,i} to the pbds.
•  » » » » » 3 months ago, # ^ |   0 Can u please explain — "st.order_of_key(mp(arr[i]-arr1[i]-1,inf))"--- In this part of your code,why you used inf?
•  » » » » 3 months ago, # ^ |   +1 Use PBDS as a multiset (comparator less_equal). Traverse from the end of the array and for each index, increment answer by order_of_key of $a[i]-b[i]$ (basically index of upper bound). Then insert $b[i]-a[i]$ in the PBDS.
•  » » » » » 3 months ago, # ^ |   +6 Yes, yes, yes, shooting pigeons with a cannon — that's my style! 73043201
•  » » » 3 months ago, # ^ |   0 Can you share your code? I tried using pbds, but it gave wa on test 6.
•  » » » » 3 months ago, # ^ |   0 You can look it up in my submissions and if are not permitted, then add me as a friend and then look it up in standings submission. Sharing code here will scribble the comment section.
•  » » 3 months ago, # ^ |   +1 It can also be done with sorting; if you have a sorted array $c$ and you want to know for particular $i$, how many $j$ satisfy $c[i]+c[j]>0$, then you can decrement $j$ from $n$ down to the first index where $c[i]-c[j]<=0$, and count $n-j$. Then if you iterate over increasing $i$, this $j$ can only decrease.
•  » » 3 months ago, # ^ |   0 What is wrong with my approach ? ;-;
•  » » 3 months ago, # ^ |   +5 problem is similar to inversion count, so used BIT tree to solve it, after compression.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I'm glad i'm not the only one who used BIT :)))))
•  » » » 3 months ago, # ^ |   0 I to used BIT to solve this. But I complicated it as hell. ACed
•  » » 3 months ago, # ^ | ← Rev. 4 →   0 Let c[i] = a[i] — b[i]. Now we have to count the number of pairs with positive sum. Sort array c.Set two pointers, one at index 0 (pointer j) and the other at index n-1 (pointer k). In each iteration decrease k by 1 and find the corresponding index j, by running a separate loop within the previous loop. Exit when j >= k.Initialize ans = 0, and keep adding (k — j) in each iteration, i.e. ans += k — jNote that j keeps on increasing in each iteration. We do not restart j from 0 each time.Time Complexity: O(n)
•  » » » 3 months ago, # ^ |   0 You have to sort array c as well, otherwise this 2 pointer technique will not work.
•  » » 3 months ago, # ^ |   +1 thanks for taking your time to write an explanation.
•  » » » 3 months ago, # ^ |   0 Thanks for saying that <3
 » 3 months ago, # |   -12 There's no one later than me to solve A! I like playing with the tetris game,but I do not like this problem!
 » 3 months ago, # |   +1 Can any one give a hack on the following approach for D?Sort them by $a_i-b_i$, then use binary search to find last okay one.
•  » » 3 months ago, # ^ |   0 Gradually sort?
•  » » » 3 months ago, # ^ |   0 Can you explain it further please?
•  » » » » 3 months ago, # ^ |   0 I think simply sort will TLE. What's your method?
•  » » » » » 3 months ago, # ^ |   0 Pasting my code here: (ignore the stable sort part, using sort fails also) Link
•  » » » » » » 3 months ago, # ^ |   0 We need ai-bi+aj-bj>0 instead of ai-bi>aj-bj
•  » » 3 months ago, # ^ |   0 sorting them will change the order of the indices and in the problem you need $j$ to be $>$ $i$
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +2 That doesn't matter, if you are counting all distinct pairs $(i,j)$ which satisfy some property, then this will equal the number of distinct pairs $(\sigma(i),\sigma(j))$ which satisfy the same property, for any permutation $\sigma$
•  » » 3 months ago, # ^ |   0 deduce condition ,suppose if ai-bi=di; then we need all di+dj>0 (j>i)pairs (counted once)for this make a array d=ai-bi you can divide array into three parts — positive(np) ,negative(nn) ,zero(n0); solve separately for zero , positive and negative;we can get our condition satisfied in three way , 1. positive di pairs 2. zero paired with any positive di 3. positive negative pairs where magnitude of positive is bigger than negative;a1=np(np-1)/2 (Ist cond); a2= n0*np(IInd cond) ; and for a3(IIIrd cond) ,you can loop in (O(nn+np)) time and at last ans=a1+a2+a3;
•  » » 3 months ago, # ^ |   0 Make an array of Ai — Bi, sort it and binary search the right one for each. That's the solution I think.
•  » » 3 months ago, # ^ |   0 Maybe you can use the Binary Indexed Tree in value.First discrete all $a_i - b_i$ and $b_i - a_i$.Then for every $i \in [2, n]$, calculate all for $j \in [1, i)$ which $b_j - a_j < a_i - b_i$The time complexity will be $O(n \log n)$.
 » 3 months ago, # |   -7 Lightning-fast system testing
•  » » 3 months ago, # ^ |   +1 There is a 12 hr hacking phase, after which system testing will begin.
•  » » » 3 months ago, # ^ |   0 Codeforces has large servers which can carry out fast testing.
 » 3 months ago, # |   0 What is the 8 test case for problem D?
 » 3 months ago, # |   +11 Why, i kept logging out after few intervals ,throughout the contest??
•  » » 3 months ago, # ^ |   +1 Me too!
•  » » » 3 months ago, # ^ |   +1 Same here
•  » » 3 months ago, # ^ |   0 Same here !
 » 3 months ago, # |   0 How to solve E? Also, what is the name of the concept used in E?
•  » » 3 months ago, # ^ |   +13 I believe it's called dynamic programming.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +1 Dynamic programming. $dp_{i, j}$ is the number of good times when we consider the first $i$ times ($0$-indexed) and did this $-1$ "operation" $j$ times. The answer is $\max\limits_{j=0}^{n} dp_n$.
•  » » » 3 months ago, # ^ |   0 what's the meaning of the first $i$ times，I can't get it
•  » » » » 3 months ago, # ^ |   +3 More correctly, $dp_{i, j}$ is the number of "good times" when we consider first $i$ values $a_i$ and used $-1$ $j$ times. Transitions are also pretty easy: if the sum of the first $i$ values $a_i$ is $s$ then $dp_{i + 1, j} = max(dp_{i + 1, j}, dp_{i, j} + [(s - j) \% h \in [l; r]])$ and $dp_{i + 1, j + 1} = max(dp_{i + 1, j + 1}, dp_{i, j} + [(s - j - 1) \% h \in [l; r]])$. $\%$ is modulo operation ofc.
•  » » » » » 3 months ago, # ^ |   0 I understand that now, thank you very much~~
•  » » 3 months ago, # ^ |   0 state are index and modulo
•  » » » 3 months ago, # ^ |   0 Submission:73073024
 » 3 months ago, # |   -7 in problem D , solution of 10^10 was giving TLE for test case 12,althought time limit was 2 seconds, http://codeforces.com/contest/1324/submission/73076815 i thought 10^10 solutions can run in 2 sec
•  » » 3 months ago, # ^ |   0 I think a bound of 10^(7-8) is good for 2 secs, 10^10 is taking it too far.
•  » » » 3 months ago, # ^ |   0 Okay..
 » 3 months ago, # |   +19 Downvoted because the sentence in problem E is completely unreadable.The sentence "The i-th time he will sleep exactly after ai hours from the time he woke up" and "Vova can control himself and before the i-th time can choose between two options: go to sleep after ai hours or after ai−1 hours." sounds inconsistent.
 » 3 months ago, # | ← Rev. 2 →   0 for problem D, i Stored two arrays one array has (ai-bi) values and the other has (bi-ai) values and i ran a nested loop from i to n-1 & j=i+1 to n-1 and counted the number of elements that are greater than current element. what could i have done better?
•  » » 3 months ago, # ^ |   +4 In fact, you can first discrete all $a_i - b_i$ and $b_i - a_i$.Then use a Binary Indexed Tree to count all the values.The time complexity will be $O(n \log n)$.
•  » » 3 months ago, # ^ |   +7 Use a binary indexed tree.Insert $a_i - b_i$ into it after checking how many elements there are before $i$ which satisfies $a_j - b_j > b_i - a_i$. Discrete all $a_i - b_i$ and $b_i - a_i$ first thing first.
 » 3 months ago, # | ← Rev. 2 →   -31 UPD: Sorry for the comment. I didn't think much, it's my bad.Appologize for the round, sorry.
•  » » 3 months ago, # ^ |   +18 Do you write is serious? The "subSTRING" problem, as you say, is not "more interesting" and can be solved in $O(n)$ considering $3$ or $4$ consecutive characters.D — data structure problem? The problem "sort the array and do (lower bound or binary search)" is data structure problem?
•  » » » 3 months ago, # ^ |   +13 Sorry for that. I didn't think too much.I am terribly sorry for the words.
•  » » » 3 months ago, # ^ |   +6 How to "sort the array and do (lower bound or binary search)"?It seems very interesting.I used binary indexed tree after discretion.
•  » » » » 3 months ago, # ^ |   +6 See this
•  » » 3 months ago, # ^ |   0 Can't the substring problem be solved in O(N)?, I did that only after I misread the problem! :( Just check all "3 consecutive characters substring" and "4 consecutive characters substring".
 » 3 months ago, # |   +1 Interesting fact for myself: Everytime people celebrate a rating-friendly contest, I lose ratings; Everytime people complain about toxic problems, I gain ratings.
 » 3 months ago, # |   +6 You did not think that the tasks are too simple even for div 3 ?)
•  » » 3 months ago, # ^ | ← Rev. 2 →   +7 Speed is really need. lol
•  » » 3 months ago, # ^ |   -26 vovuh made them easy to please div3 pplhere
•  » » » 3 months ago, # ^ |   +64 Haha, that's funny. I don't know how to prepare "good" round. I prepare slightly hard round, people say "omg that's div.1, not div.3!". I prepare slightly easy round, people say "loool 2ez4me that was not even a round". I don't know what to do.
•  » » » » 3 months ago, # ^ |   +62 Lol. You should ignore comments made by candidate masters on div3 rounds. A candidate master saying div3 is easy is like a pupil / grey guy saying div1 is hard.
•  » » » » 3 months ago, # ^ |   +20 actually, vovuh, you did well, i really appreciate as most of div.3 contests are made of you
•  » » » » 3 months ago, # ^ |   -62 Don't coordinate anymore divs 3 rounds )
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +45 Yea, yea, I remembered you. You wrote the same about pikmike. That's all I need to know.
•  » » » » » » 3 months ago, # ^ |   -13 axaxaxxa
•  » » » » » » » 3 months ago, # ^ |   +19
•  » » » » » » » » 3 months ago, # ^ |   +3 You look like Radewoosh
•  » » » » » » » » » 3 months ago, # ^ |   +4 I'm his brother
•  » » » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Blue blood in ICPC?
•  » » » » » » » » » 3 months ago, # ^ |   0 Twin brother.
•  » » » » » » » » » 3 months ago, # ^ |   0 who knows who knows
•  » » » » 3 months ago, # ^ |   +24 Actually, vovuh, you are the best. You prepare quality Div 3 contests, and I enjoy participating in your contests. Also, I participating out of the contest; I get to learn new concepts and techniques from your contests. I hope you keep up this great work and keep contributing to more such awesome contests.
•  » » » » 3 months ago, # ^ |   +4 I really liked D problem of this contest. I've been focusing on pbds/fenwick last 2 weeks and this problem really put my knowledge to test. I like how I saw 3 different approaches on this problem(bin search, pbds, fenwick and treap). The problem really managed to capture the creativity of the community. Well done, our Div.3 King
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +1 Great job vovuh, don't give in to the hate. As it is, it's hard and time consuming to create problems and test cases, let alone deal with criticism such as this.Personally, I think this is a good level of difficulty, otherwise how do we differentiate between Div 2 and Div 3 problems. Once in a while, problems in Div 3 are easier compared to other Div 3 contests — but I think many people in Div 2/Div 3 enjoy the opportunity to solve a few problems (that are in reach and where we can apply what we've learnt recently) and then learn from the other unsolved problems.
•  » » 3 months ago, # ^ |   +9 I think that this is the perfect difficulty level for Div 3. Myself being an Expert (Rating: 1734), I was only able to solve A, B, C, D. So, I believe that it justifies my claim.
 » 3 months ago, # |   +13 Speedforces
 » 3 months ago, # |   0 Tried E for the first time in my life. Got wrong answer test 40! I think I made a silly mistake but couldn't figure out yet. My submission: 73079617
•  » » 3 months ago, # ^ |   0 It failed for me as well, test case is involving l = 0 I guesss, and I had counted t = 0 case, which is wrong. Removing that gave me AC.
 » 3 months ago, # | ← Rev. 2 →   0 Why these two submissions using PBDS for problem D got different verdicts Vovuh please look into the matter.Correct SOlution:-73082017 Rejected Submission:-73079109
•  » » 3 months ago, # ^ |   +3 It's because, in your case, it couldn't contain same elements.
•  » » » 3 months ago, # ^ |   0 thank you for reply oh I got that it is property of sets
 » 3 months ago, # |   +9 During contest I was logged out several times. Does someone know why?
•  » » 3 months ago, # ^ |   0 The same happened with me 4 times as well.
 » 3 months ago, # |   0 It's quite easy. Even my i got more rating, but i think i wouldn't satisfy with those.
 » 3 months ago, # |   0 What's wrong with this submission for D? https://codeforces.com/contest/1324/submission/73081429
 » 3 months ago, # |   0 Why I am getting ILLEGAL CONTEST error while pushing "hack it"? Please fix
•  » » 3 months ago, # ^ |   +1 you must go to submission link and then press hack it there instead of hack from status
•  » » » 3 months ago, # ^ |   0 TY. It works
 » 3 months ago, # |   0 Hey guys Can anyone tell meWhy this submission fails :https://codeforces.com/contest/1324/submission/73068802and this one passes: https://codeforces.com/contest/1324/submission/73082736I'm not able to find the problem can anyone point this out with an example.Thank you!
•  » » 3 months ago, # ^ |   0 Please guys :)
•  » » 3 months ago, # ^ | ← Rev. 7 →   0 ll cn1=pos.size()*(pos.size()-1)/2;pos.size() => returns (int value) not (long long value) you must work casting.
•  » » » 3 months ago, # ^ |   0 Thank you so much it worked now. Didn't work during contest so sad :(
 » 3 months ago, # | ← Rev. 3 →   +1 Hello? I'm a bit curious about how to solve F, can someone help me? Thanks
 » 3 months ago, # |   0 can someone please explain the reason for TLE in my submission of E my code -link
•  » » 3 months ago, # ^ |   0 Because at last where you have done dp[id][sum][f]=ans, your value of sum is changed, but your dp[id][sum][f] should use original value of sum not the updated one.
 » 3 months ago, # |   0 1 5 2 2 2 2 4 why this will give yes in A?
•  » » 3 months ago, # ^ |   0 NO, since all elements must have same parity (either odd or even), then only answer can be "YES"
•  » » » 3 months ago, # ^ |   0 can you show the steps?
•  » » » » 3 months ago, # ^ |   0 Add 2 with each 2 then reduce 1 by 1 in 4 steps
•  » » 3 months ago, # ^ |   0 Is it a full test or a single case? If it is a full test(i.e. 1 represents number of cases,5 represents number of columns) then simply put blocks in column 1-4 If it is a case(i.e. there are 7 columns),the answer is NO.
 » 3 months ago, # |   +5 +104 -> +8, thx for B pretests, goodbye expert:(
•  » » 3 months ago, # ^ |   0 THIS HAPPENED WITH ME TOO :'(
•  » » 3 months ago, # ^ |   0 exactly same problem.... :/ why would they create such weak tests?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +1 Actually, it means we should be more careful, and find out all special cases.
•  » » » 3 months ago, # ^ |   0 the thing is , the hacks arent even special cases, the hack could have easily been in the example test.
•  » » » » 3 months ago, # ^ |   0 If you didn't consider something, for you it was a special case I suppose.
•  » » » » » 3 months ago, # ^ |   0 how did you figure out your rating change?
•  » » » » » » 3 months ago, # ^ |   0 Chrome extension "CF-predictor"
•  » » » » » » » 3 months ago, # ^ |   0 Oh thanks. I can't see the prediction, I guess I was supposed to have it before the contest too?
•  » » » » » » » » 3 months ago, # ^ |   0 Sorry, I don't know.
 » 3 months ago, # |   0 Hack for B?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 1 3 1 1 1 
 » 3 months ago, # | ← Rev. 3 →   0 !!NEED HELP!!My solution for problem-D : 73076688According to me,it's complexity nlogn, but i m getting time limit. Can anyone explain why it is happening or where m i wrong??TIA
•  » » 3 months ago, # ^ |   +1 sum+=(ll)distance(it,ms.end()); has linear complexity -> O(n^2logn)
•  » » » 3 months ago, # ^ |   0 If I hack my own solution, then will that be an advantage?? like my scores would not reduce
•  » » » » 3 months ago, # ^ |   0 No, you'll just hack your own solution instead of someone else.
•  » » » » » 3 months ago, # ^ |   0 Seppuku, the honourable way.
•  » » » » » » 3 months ago, # ^ |   0 So, I made that:)
 » 3 months ago, # |   0 quite sad that my solution for B got accepted in the first place , was it intentional to make the test cases all weak for only an odd length palindrome / 2 different numbers only? would've solved 5 problems in one contest for the first time.
•  » » 3 months ago, # ^ |   0 Yeah i mean i totally forgot about that test case.. I mean i knowingly did this when i should have not done it and it would have passed.
 » 3 months ago, # |   0 Hi, can anyone explain why this solution 73084554 is giving WA. While this solution works 73037149 by tmwilliamlin168. Thanks in Advance!
 » 3 months ago, # | ← Rev. 5 →   0 Problem B $O(N)$73087070
 » 3 months ago, # |   +3 I liked this contest vovuh. Good job. I'm interested to know your thoughts on the difficulty levels of $D$ and $E$ if this was a Div $2$ contest. Do you think $D$ is harder than $E$ ?How to solve $F$ ?
•  » » 3 months ago, # ^ |   0 I think D is between the div2B and the div2C, while E is between the div2C and the div2D.However, you may just wait until when these problems are recorded in PROBLEMSET and the difficulty of them will be visble for you.
•  » » » 3 months ago, # ^ |   0 I think segment trees are too difficult to be asked for $B$. It might be a $C$. Can you please tell me how to solve $F$ ?
•  » » » » 3 months ago, # ^ |   +8 In fact, you don't need segment tree for D since the binary search is enough for it.For problem F, I apply DFS twice on the trees.In the first DFS, I regarded no.1 node as root and regarded the trees as a rooted trees. In this DFS, I get the correct answer for no.1 node.In the second DFS, I started my DFS from no.1 node and calculated the answer of other nodes in my traversal.For more details ( since I'm poor in English but good at C++ ), you can look up my code.
•  » » » » » 3 months ago, # ^ |   0 Nice ! I never thought of binary search for counting inversions ! :)My main doubt was in the second DFS. Thanks !
•  » » » » » 3 months ago, # ^ |   0 I implemented the same algorithm in Java, but failed test case 3. I couldn't figure out why it fails. Can you help me? My submission is: 73110580
•  » » » » » » 3 months ago, # ^ |   0 It seems like ts3 is just a random tree whose node is all black. So you can just make a small test to see what happens in your program.
•  » » » » » » » 3 months ago, # ^ |   0 My tree building logic was wrong, I need to build a 0-rooted tree recursively, thanks anyway!
•  » » 3 months ago, # ^ | ← Rev. 2 →   +6 Root the tree arbitrarily and let $dp_x$ be the answer for $x$'s subtree. We can do this with a single dfs. But then $dp_x$ won't necessarily have its full answer (because we didn't consider the path through $x$'s parent). So do a second dfs and for each parent node $y$ update each of $y$'s child's $dp$, (child may benefit from path via their parent $y$), but be careful to not to over count that child's contribution from $dp_y$.for clarity you can see my submission: 73067648
•  » » » 3 months ago, # ^ |   0 Ah ! The overcounting is tricky ! We should subtract only if $f(c) > 0$. The reason is that if $f(c) > 0$, then we never added $f(c)$ to $f(v)$Thanks !
 » 3 months ago, # | ← Rev. 2 →   +1 it is the first time i tried in E but i got WA on 40 any one can help me why it is wrong https://codeforces.com/contest/1324/submission/73078402
•  » » 3 months ago, # ^ |   0 Corner Case: 1 3 0 0 1You miss this case.
•  » » » 3 months ago, # ^ |   0 yo boy!
 » 3 months ago, # |   0
 » 3 months ago, # |   0 Can someone please explain to me the DP state for problem E?
•  » » 3 months ago, # ^ |   0 Before considering sleeps #$i,i+1,\ldots,n$, suppose you last slept at time t. Then under these conditions, dp[i][t] is the maximum number of good sleeps among $i,i+1,\ldots,n$. The question asks to find dp[1][0].
 » 3 months ago, # |   +1 Can B be solved in O($n^2$) will it pass?
•  » » 3 months ago, # ^ |   0 i think. YES, as n=5000
•  » » 3 months ago, # ^ |   0 Yes, but if you have a constant factor $a$ you will have runtime $O(a * n^2)$, which may TLE because worst case scenario you will do something like $a * 5000 * 5000$ operations which may not be executed in time (I hacked a couple ppl with this idea)
•  » » 3 months ago, # ^ |   0 Yes, since sum of all n is <= 5000.
 » 3 months ago, # |   0 Can someone explain why the order (i
•  » » 3 months ago, # ^ |   +1 i
•  » » 3 months ago, # ^ |   +2 It is another way of telling that pairs (i,j) and (j,i) are the same. And they have to be counted as 1.
 » 3 months ago, # | ← Rev. 2 →   0 Is problem F a classic problem? Because i notice that many people write similar code in their dfs. If it is, please tell me. Thanks is advance :)
•  » » 3 months ago, # ^ |   +3 i think you are talking about F
•  » » » 3 months ago, # ^ |   0 Thanks! fixed now.
•  » » 3 months ago, # ^ |   +3 i think because its straight forward.
•  » » 3 months ago, # ^ |   +3 Yes it's a classic problem based on dp on trees. You can refer to rachitiitr youtube videos regarding in-out dp.
•  » » » 3 months ago, # ^ |   0 Can you provide the link please :)
•  » » » 2 months ago, # ^ |   0 Can you suggest links for rerooting technique and in-out dp?
 » 3 months ago, # |   0 Could someone help me figure out my mistake in Problem E 73091842. Thanks in advance.
•  » » 3 months ago, # ^ |   +1 It's because you don't take maximum of dp[i][j]s any where in your for loops.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Ok
 » 3 months ago, # |   -10 Are you guys mad? I have missed the contest due to change in timing, now I can't attend div1 challenges.
 » 3 months ago, # |   +4 Vovuh you are great author your problems are amazing
 » 3 months ago, # |   0 Hack case of B . 1 3 2 2 2
 » 3 months ago, # | ← Rev. 3 →   0 how is this O(n^2) solution timing out on B for 2 secs??.Link
•  » » 3 months ago, # ^ |   0 It seems like you are using map which takes $O(\log n)$ time for adding and looking for element. Also, std::map is especially slow (big constant factor) so your solution has time complexity $O(n^2 \log n)$ with big constant factor.
•  » » » 3 months ago, # ^ |   0 Ah, wow. i always thought map was constant access and insertion. thanks btw
•  » » » » 3 months ago, # ^ |   +1 I think what you want is unordered map which uses hash. It has constant access time on average (but can be up to $O(n)$ worst case). It also is quite slow since internal structure is somewhat complicated. I mean, don't expect something like a array-access speed. Also, since it uses random, it can be hacked if some experienced coder tries to craft specific testcase to kill unordered map. I think there was a good blog on CF about this (and also how not to get hacked from that) but I can't find it now.
•  » » » » » 3 months ago, # ^ |   +1 Neat info thanks. i guess using a boolean array in this case would have been better. my loss
•  » » » » » 3 months ago, # ^ |   0 You might be talking about this.
•  » » » » » » 3 months ago, # ^ |   +1 coderanant orz
•  » » » 3 months ago, # ^ |   0 So this should time out too? 73028508
•  » » » » 3 months ago, # ^ |   0 I don't think so. Your code is performing $n$ map access operations which make the whole complexity like $n \log n$. The code originally asked was using about $n^2$ map access.
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Thanks. I was misinformed about the access time of maps, now its clear.
•  » » 3 months ago, # ^ |   0 I think map takes O(log n) time for searching thus complexity goes to O(n^2logn)
•  » » » 3 months ago, # ^ |   0 thanks
 » 3 months ago, # |   +15 When it's my first time to solve 4 problems and I've a new high rank:HACKS:
 » 3 months ago, # |   0 Nice Contest! My solutions: A. Check the parity of all elements. If the parity is same, then the answer is YES, else NO B. Its always enough to check for palindrome sequences of length 3. So considering each element as center, check if the right and left parts contain atleast 1 element in common. C. its always beneficial to use R and not L. (why? bcoz with L you can only reach back to reach some R, which anyway you would have reached before reach the cell with L). so find the largest gap in reaching a R. D. Compute ci = bi-ai and sort this array. Then for each ai and bi count the number of elements in array c less than ai-bi. Also make sure to consider the edge cases where you have counted the same element again. E. Use dp. The state is (i, time), where i is the day (or the ith sleep) and time is the current time. Write transitions to each of ai and ai-1. F. Assuming you run bfs from some initial root node, Compute max(wi-bi) for each node i in its subtree rooted at i. Now we need to compute the value in parent part. This can be done using tree rerooting technique.
 » 3 months ago, # |   0 Could someone help me with my problem E submission. I am not able to figure out the mistake.Thanks in advance[submission:73096035]
•  » » 3 months ago, # ^ |   0 Corrected code 73127806 Explanation$dp[i][j] = 0$ makes it so impossible situations (states of $dp$) can change the result. Setting $dp[i][j] = - inf$ fixes it. Example of simple hacktest: 2 24 23 231 1 Correct answer is 0.
•  » » » 3 months ago, # ^ |   0 Thanks
 » 3 months ago, # |   0 Can anyone tell me why this 73097950 passes and this 73098017 does not ?
•  » » 3 months ago, # ^ | ← Rev. 3 →   +1 they will give different output when v contain same value more than once.Check this 3 6 6 6 2 2 2
 » 3 months ago, # |   0 Can somebody hack this?PS: I find similar solutions getting hacked.
 » 3 months ago, # |   0 what's wrong? After submitting the (A) question of Round #627 Div. 3, in test case #2 it is showing this: "wrong answer Answer contains longer sequence [length = 100], but output contains 28 elements ". Can I know the reason?
•  » » 3 months ago, # ^ |   0 You should print 100 output not 28, That is, 1 output for each test case.
•  » » » 3 months ago, # ^ |   0 I think my code is doing it. can you please check it? solution no: 73099642
 » 3 months ago, # |   +20 ![ ]()
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Edit: now i know that these are the number of hacks.
 » 3 months ago, # | ← Rev. 2 →   0 I got TLE error during contest instead of WA! even after the contest when I was submitting correct answer I was getting TLE. I got frustrated and then copy pasted solution of another user then also I got TLE. Also, I was logged out multiple times automatically during the contest!! solution link: https://codeforces.com/contest/1324/submission/73104474
•  » » 3 months ago, # ^ |   +4 use pypy 3 instead of python 3 as your language on codeforces.
•  » » » 3 months ago, # ^ |   0 It worked, thanks for the help! do you know reason/line where its failing in python3.7?
•  » » » » 3 months ago, # ^ |   0 There are answers in stackoverflow.com
•  » » » 2 months ago, # ^ |   0 I am getting error in 6th problem too, for 36th test case! can you help me in that too? https://codeforces.com/contest/1324/submission/74307112
 » 3 months ago, # |   +8 Will there be any system testing after the hacking round is finished??
•  » » 3 months ago, # ^ | ← Rev. 2 →   +8 YesAll of the AC solutions will be rejudged with original tests and successful hacks once the hacking phase is over.
 » 3 months ago, # |   +9 Why I want to hack a solution and it shows Illegal contest ID ？
•  » » 3 months ago, # ^ |   +6 Try to hack solutions via the Status page instead of the Standing Page
•  » » » 3 months ago, # ^ |   +6 Ok I get it. Appreciating your help !
 » 3 months ago, # |   0 Can Somebody please explain why this solution is not giving compile time error on pretest cases and arbitrary cases on offline compiler Solution for Problem 2
 » 3 months ago, # |   +14 When system test will start?
 » 3 months ago, # |   0 What's wrong with my solution for E problem? 73075794
 » 3 months ago, # |   +2 I am wonder that when the system test will begin.
 » 3 months ago, # |   +1 Anyone who solved problem D using two pointers? Please explain your approach