### 4qqqq's blog

By 4qqqq, history, 12 days ago, translation,

Hello, Codeforces!

On Nov/26/2021 14:15 (Moscow time) Codeforces Round #757 (Div. 2) will start. This round will be rated for participants with a rating less than $2100$.

All the problems were authored and prepared by vaaven and me.

You will be given $5$ problems, one of which has two subtasks. You will have 2 hours to solve them.

We would like to thank everyone helped a lot with round preparation:

Score distribution: $500$ — $750$ — $1500$ — $(1500 + 1000)$ — $2750$.

Good luck everyone!

UPD: Editorial

• +99

 » 12 days ago, # |   +144 I hope that you will enjoy the short and concise statements. Also I hope that the hack I found will make people FST less (yes, it is in pretests )
•  » » 11 days ago, # ^ |   +44 I think you should change your mind about concise statements. Statements wrote very bad and statements are only stories that waste our time.
•  » » 11 days ago, # ^ | ← Rev. 5 →   +243 Well, you and lollihunter's translations are very bad, and I'm angry at it. Problem B, sample explanation is wrong. Later you post an announcement, so I don't have any words to say but just very annoyed. Problem E, even the statement is wrong. You write $P+1,P-1$ instead of $T+1,T-1$, and later you fix the mistake without posting an announcement. So many people test this contest, but why don't any of them find these obvious mistakes? I think you should reflect on yourselves.UPDAfter the talk with errorgorn, I realize that it isn't his fault. When I tested the round, the statements were much worse. That is why I told the coordinator that I would help clean up the english statements. I am very sorry to make this trouble. The mistake of problem E is maybe the problem setter's fault.
•  » » » 11 days ago, # ^ |   +99 Agree.
•  » » » 11 days ago, # ^ |   +72 I wasted a long time on the wrong statement of E,I've even written the code.I'm angry now.
•  » » » » 11 days ago, # ^ |   +15 Welcome to the club
•  » » » 11 days ago, # ^ |   +53 I think that problemsetter should tell competitors about statement-update quickly.
•  » » » 11 days ago, # ^ | ← Rev. 7 →   +22 I edited the statements for problems A,D,E only (and a removed problem). Problem B was added very late into testing so I did not look at it. I wrote problem E with only using $T$, I am not sure why it is changed as well. (I believe it was added quite late into testing as well so please do not blame the rest of the testers.) I tried to do my best as a tester but I did not want to interfere too much with the content of the problems. I personally felt that I was pushing it when I removed some backstories in the statements (you will notice the english statement for A is much shorter than the russian statement). I don't really have anything to defend myself but I did not know the statements were changed from what I edited it to until today.I can understand your frustration but there is only so much a tester can do...If there are any comments that are actually about translation and making the statements easy to read, I would be happy to read them. The problems you listed have nothing to do with translation. Do you really think they are the translators fault? They also appear in the russian version of the statements you know.
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +23 That's not lollihunter's or errorgorn's mistake, because they made translation before some edits in english texts.So, sorry for such terrible statements :(
•  » » 11 days ago, # ^ | ← Rev. 5 →   +4 Someone please give hint for Problem D1
•  » » » 11 days ago, # ^ |   +1 use dpalso , $\sum_{i=1}^n(\lfloor\frac{n}{i}\rfloor)$ is about $n \ln n$
• »
»
11 days ago, # ^ |
Rev. 4   -11

# error

I don't know, when will the editorial release so, I am commenting here.

In problem B I have just used

  sort(all(a), [&](auto &a, auto &b)
{
if (a.first != b.first)
return a.first > b.first;
else
a.second < b.second;
});


to sort the array and I got TLE.

Even if I remove else a.second < b.second;, still I am getting TLE.

I used this sort(all(a), greater<pair<ll,ll>>()); after the contest, the solution got accepted.

Solution1

Solution2

If possible, kindly resolve this issue, as according to me this should be a problem.

•  » » » 11 days ago, # ^ |   +4 Eh, I am only a translator... I guess i can help fix your codeThe issue is with the code below, sort(all(a), [&](auto &a, auto &b) { if (a.first != b.first) return a.first > b.first; else a.second < b.second; }); you have missed out the return statement in the else I think changing it to the edited code below should work sort(all(a), [&](auto &a, auto &b) { if (a.first != b.first) return a.first > b.first; else return a.second < b.second; }); 
•  » » » » 11 days ago, # ^ |   0 ohk, thanks :)
•  » » » 11 days ago, # ^ |   0 You missed a return in the compare function in solution 1.
•  » » » » 11 days ago, # ^ |   0 ohk, thanks :)
 » 12 days ago, # | ← Rev. 2 →   +27 This is my first time testing the round and I hope my feedback helped to balance it! I encourage you to read all of the problems — as they are very interesting.
•  » » 11 days ago, # ^ |   -17 Score distribution looks promising
 » 12 days ago, # |   -10 A great time for Chinese people. Hope everyone can gain rating.
•  » » 11 days ago, # ^ |   -10 Why downvote this? The comment is pretty wholesome.
 » 11 days ago, # |   -17 Score distribution looks promising
 » 11 days ago, # |   +8 Note the unusual timing
 » 11 days ago, # |   0 I hope to perform well in div2 contest.
 » 11 days ago, # |   -14 D1>D2? That's weird. I hope everyone can solve them.
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 I think that easy version points $>$ hard version points is usual, for example Codeforces Raif Round 1 (Div. 1 + Div. 2) and Codeforces Round #750 (Div. 2).
•  » » » 11 days ago, # ^ |   -10 but why is easy version points are greater than hard version points?
•  » » » » 11 days ago, # ^ |   +4 I think that if you solved hard version, you almost can solve easy version.
•  » » » » » 11 days ago, # ^ |   0 I got it. Thanks.
•  » » » 11 days ago, # ^ |   0 totally agree with your point ...
 » 11 days ago, # |   -155 Specialist setting rounds on CF. Pathetic! One day we will see newbies doing same.
•  » » 11 days ago, # ^ |   +37 Saw his profile, he came down from candidate master. Might be he had 1-2 bad contests and 1-2 bad contest doesn't define someone. You can assume a candidate master has set the problems.
•  » » » 11 days ago, # ^ |   -58 Who are you?
•  » » » » 11 days ago, # ^ |   +81 A codeforces user.
•  » » » » » 11 days ago, # ^ |   0 op
•  » » 11 days ago, # ^ |   +62 So, now I'm expert.
•  » » » 11 days ago, # ^ |   0 Congratulations! Amazing Performance, my friend.
•  » » » » 11 days ago, # ^ |   0 Thanks! :)
 » 11 days ago, # | ← Rev. 2 →   +8 I always see, when the contest is held in unusual time, there are relatively less people who participate in the contest. And that is why we get less rating changes as compared to a usual time contest (because rating change also depends on no. of participants).
•  » » 11 days ago, # ^ |   -35 Ok so you participate in contests just to get some ratings?This mentality of just gaining ratings and not enjoying CP as a sport has led to so many cheating cases these days!
•  » » » 11 days ago, # ^ |   +64 haha...go and check my profile...still stuck on specialist after giving around 70 contests. If I were a cheater I'd have been orange or red till date after giving around 70 contests. Moreover I have 192 days problem solving streak(and counting) till date. If I were a cheater, why would I have been practicing CP this much. These things are enough for anyone to understand that I don't cheat.Reward is something people wants when they works for it. People first need expectation to gain something in life provided that they are working fair. Yes I give contest for rating, but that is not greed. Because your school teacher has not taught you the meaning of greed. Greed is something that we want without working, and expectation is something that we want when we work hard for it. That is called 'achieving', not 'cheating'. I hope god made you smart enough to understand this.
•  » » » » 11 days ago, # ^ |   +7 op(2)
•  » » 11 days ago, # ^ |   -64 Looks like you have cheater mentality of just giving contest for Greed(ratings). Stop it or you will be banned..
•  » » » 11 days ago, # ^ |   +43 who are you, the thought police? no one's getting banned for their mentality
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +11 haha...go and check my profile...still stuck on specialist after giving around 70 contests. If I were a cheater I'd have been orange or red till date after giving around 70 contests. Moreover I have 192 days problem solving streak(and counting) till date. If I were a cheater, why would I have been practicing CP this much. These things are enough for anyone to understand that I don't cheat.Reward is something people wants when they works for it. People first need expectation to gain something in life provided that they are working fair. Yes I give contest for rating, but that is not greed. Because your school teacher has not taught you the meaning of greed. Greed is something that we want without working, and expectation is something that we want when we work hard for it. That is called 'achieving', not 'cheating'. I hope god made you smart enough to understand this.
•  » » » » 11 days ago, # ^ |   +7 respect++
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   -21 respect -= -1;
•  » » » » » 11 days ago, # ^ |   0 XD too many downvoted this comment which was simply respect++.
•  » » » » » » 7 days ago, # ^ |   0 I'm sorry for my poor English *it's much easier to get downvoted when your rating is low. But of course there is sometimes an exceptions 3
 » 11 days ago, # | ← Rev. 3 →   +31 First time being a tester, so excited (^.^). Although the start time is unusual again, hope you guys could spend time participating the well-prepared round with interesting problems >~<
•  » » 11 days ago, # ^ |   0 your graph is really motivating :)
•  » » » 11 days ago, # ^ |   +3 Thanks! I have focused on CP since last year in order to have an opportunity to participate in the national OI in my country. If I could proceed to the national round, my next target is reaching yellow color on CF ;)
•  » » » » 11 days ago, # ^ |   +3 I hope you do!, all the best
•  » » » » 11 days ago, # ^ |   0 solo ?
•  » » » 11 days ago, # ^ |   +1 look at my graph and be demotivated again lol
•  » » » » 11 days ago, # ^ |   0 I am not in the position to comment but lol
 » 11 days ago, # | ← Rev. 3 →   +8 Hope that my streak of underperformance ends here
 » 11 days ago, # |   +3 I hope to solve four problems in this round. Looking forward to it :).
•  » » 11 days ago, # ^ |   +1 maybe 5?
•  » » » 11 days ago, # ^ |   +1 But that's after I solve 4 :).
 » 11 days ago, # |   +39 As a tester I'm a tester
•  » » 11 days ago, # ^ |   +4 zamn
 » 11 days ago, # |   +62 Meme
•  » » 11 days ago, # ^ |   +13 Hopeforces
 » 11 days ago, # |   +1 fingers crossed for some non negative delta
 » 11 days ago, # |   0 Are Ratings going to update before the round starts ?? Any Idea ??
•  » » 11 days ago, # ^ |   0 don't think so
 » 11 days ago, # |   +1 Can we participate in a contest without rating update from the previous contest?
 » 11 days ago, # | ← Rev. 2 →   0 Will this round take place with the current ratings or would it be considered after yesterday's round rating changes are updated? MikeMirzayanov
 » 11 days ago, # |   +1 Thxx for the unusual timing. Its better for us (russians)
 » 11 days ago, # |   0 hey I have confusion as previous contest rating is not updated yet so this contest rating will be calculated with change in rating or rating before previous contest ? please someone clearify
 » 11 days ago, # |   +6 The contest was delayed by 10 minutes!
•  » » 11 days ago, # ^ |   0 Yeah. I guess there must have been some server issue.
•  » » 11 days ago, # ^ |   +20 Maybe in the meantime, the rating will be changed
•  » » » 11 days ago, # ^ |   +1 done
 » 11 days ago, # |   +6 Why delay??
 » 11 days ago, # |   0 Why you made changes in timings??
 » 11 days ago, # |   +237 Sorry, I postponed the round. I would like to have time to update the rating based on the results of yesterday's Div3. I'm in a hurry!
 » 11 days ago, # |   -17 I have not copied or shared any information with anyone, but I got this message from the system that my submission significantly coincides with someone else. Can someone please look into this
•  » » 11 days ago, # ^ |   0 don't use ideone. Its the major reason for this type of issues.
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 I did not use any online editor and am sure I kept my submission private.
•  » » 11 days ago, # ^ |   0 I did the ideone rookie mistake. Hopefully will recover in this contest. OP is right. Keep it all private.
•  » » 11 days ago, # ^ | ← Rev. 3 →   0 Edit: Problem solved. I have got my rating.
 » 11 days ago, # |   +1 Good decision to increase 10 minutes , i didn't drink coffee
 » 11 days ago, # |   -7 Why it's start time is 19:15(in China)?It's usually 22:45(in China).
 » 11 days ago, # |   +14 Congratulations to 4qqqq to get 107 ratings. XD
 » 11 days ago, # |   0 Good luck to everyone
 » 11 days ago, # |   0 Wow! MongoliaTop has AKed this contest!
 » 11 days ago, # |   -6 Is it div.3?
•  » » 11 days ago, # ^ |   +7 No its Div93849329 you're too noob
•  » » 11 days ago, # ^ |   +29 Is it some IGM alt ?
•  » » » 11 days ago, # ^ |   +8 Maybe LGM.
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +3 list, coding style seems very close
•  » » 11 days ago, # ^ |   -6 ow that's rude
•  » » 11 days ago, # ^ |   +120 It is div.trash
•  » » 11 days ago, # ^ |   +58 It is div.114514
 » 11 days ago, # |   +7 Another mathforces round :(
 » 11 days ago, # |   +13 Retired_MiFaFaOvO participating .. after a long time
 » 11 days ago, # |   +1 The amount of ad hoc contained in problem C frightened me.
 » 11 days ago, # |   +13 pretest 2 of problem c has cost me my mouse and sanity
•  » » 11 days ago, # ^ |   0 How do you solve it? Pretest 2 killed me
•  » » » 11 days ago, # ^ |   0 In my case I missed the input like:11 11 1 1073741823it took my last 40 minutes during the contest...
 » 11 days ago, # |   0 How to solve D2? How to optimise from O(Max(ai)*log(max(ai)))?
 » 11 days ago, # | ← Rev. 2 →   +2 The problems themselves are good, but the contest is unbalanced. There are so many math problems. Problems A and B are too easy, and problems D E are too hard. If you have some problems with problem C, like me, wasting too much time for mistaking "OR" by "XOR", you will be finished.
•  » » 11 days ago, # ^ |   +3 I saw it after seeing your comment I thought it's xor of subsegment.. I'm doomed
•  » » 11 days ago, # ^ |   +1 Same thing happened to me also :(.
 » 11 days ago, # |   +1 Hint for C I wasted my 30 minutes in thinking this logic. Could have googled it early and got a decent rank!
•  » » 11 days ago, # ^ |   0 Same
•  » » » 11 days ago, # ^ |   0 Two Friends Of Mine Tried Solving It Using Lazy Propagation xD, only one got ACC
•  » » 11 days ago, # ^ |   0 I was able to figure this out — but what was the logic for finding the frequency/number of each bit present in the array? e.g. in array [1, 2] — 0th bit freq is 1, and 1st bit freq is 1. How do I get that info from the subsegments?
•  » » » 11 days ago, # ^ | ← Rev. 3 →   0 if an element is covered by more than 1 subsegments, then its largest possible value is the bitwise AND of all values corresponding to the subsegments that are covering it.For example, if we have n=3 and subsegments 1 2 7, 2 3 14, then the largest possible value of a_2 is 7 & 14 = 6. Moreover, a possible value must only have the bits occur in the binary representation of the largest possible value. But we can safely just use the largest possible value here.I used a segment tree (range update + point query) to process this information, and I wonder whether there exists a simpler approach.
•  » » » » 11 days ago, # ^ |   +2 What i did was, took OR of all the OR's given (irrespective of l,r) and just multiplied it with pow(2,n-1). This passed pretests as well as sys tests.
•  » » » » » 11 days ago, # ^ |   0 It's like we don't need to reconstruct a valid sequence, am I right?Could you briefly explain the intuition (or proof) behind this? Thanks
•  » » » » » » 11 days ago, # ^ |   0 Yeah, we don't need to construct a valid sequence.Try this link here for a formal proof
•  » » » » » » 11 days ago, # ^ |   0
•  » » » » » » 11 days ago, # ^ |   +1 If X is the bitwise OR of a segment, then for each set bit of X, there exists an element with that bit set. Then consider all subsequences excluding that element (2^(n-1) of them): they either XOR to 1 or 0 times 2^(bit). If they XOR to 1, then subsequence with our set bit XORS to 0; if they XOR to 0, then subsequence with our set bit XORs to 1. Either way, we are guaranteed a contribution of exactly 2^(bit) times 2^(n-1) from that bit, i.e. its contribution to x. So we just need to know if a given bit is set anywhere in the whole sequence, and if so we add that contribution. Otherwise, the bit is skipped.
•  » » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 i am such a stupid that i started figuring out a valid sequence and I figured out how to find a valid sequence.But when i used combinatorics to find the number of subsequences i realized that we just need to know whether there is a particular bit on in any of the element in the array which can easily be figured out by just looking OR of all elements.2^(num of on jth bit-1)*2^(n — (num of on jth bit)) you can see that num of on jth bit cancels out but you can see num of on jth bit — 1>=0 num of on jth bit >=1
•  » » » » » 11 days ago, # ^ |   0 Yes, I'm seeing some submissions with this logic. Could you explain the intuition plz
•  » » » » » 11 days ago, # ^ |   +3 Why does this work? I got that OR of all the ORs given will be the OR of the original array. But why does it become sum of XOR of all subsets after multiplication with pow(2,n-1) ?
•  » » » » » » 11 days ago, # ^ |   +1 In binary, look at digit r (aka the bit corresponding to the place 2^r) of all numbers in the original array. Say a of them are 1s and b of them are 0s. From the set of a numbers, choose i to be in some arbitrary subsequence, and from the set of b numbers, choose j. Note that making such a choice corresponds to forming exactly one subsequence (for now, dealing with digit r only). Clearly, the bitwise XOR will yield a 1 for digit r iff i is odd. If a>0, this corresponds to aC1 + aC3 + aC5 + ... = 2^(a-1) ways of choosing a set of i numbers from the original a, where i is odd, and simply 2^b ways of choosing any j numbers from the b with 0s at digit r. Hence, when a>0, the total contribution from all subsequences to coziness by digit r is 2^(a+b-1) * 2^r = 2^(n-1) * 2^r, as a+b=n. When a=0, however, the contribution to coziness is 0. The coziness can thus be written as 2^(n-1) * sum(2^r, where a>=1 at position r). Observe that this sum is the bitwise OR of the n numbers, and we're done.
•  » » » » » » » 11 days ago, # ^ | ← Rev. 4 →   +1 Thanks a lot. This seems fine. Although I found this another explanation by going through the comments-If at a given place, if at least one of the numbers has its bit = 1 :1) lets remove any number from the array whose bit is 1 at that place.2) now, rest of the numbers(n-1) will make pow(2,n-1) sets, now all the sets with xor of bits = 1 will contribute to the solution (addition of XORs) 3) but if xor of the bits in a set is 0, the it will become 1 when the excluded number with set bit is added to all the sets, and then it will contribute to the solution.4) So if at least one of the numbers has its bit 1 at a place, it ensures that this place will contribute place_value*pow(2,n-1) to the solution (sum of XORs)5) Now to ensure if at least one number has its bit 1 at place, we can find OR of all the numbers and check if the it is 1 at that place.6) OR of all the given ORs will be the OR of the array.
•  » » 11 days ago, # ^ |   +3 I wasted a lot of time in solving this, however, I still didn't solve it. Thanks for your hint. My rating must be reduced a lot. :(
•  » » » 11 days ago, # ^ |   +15 Rating is temporary. Skill is permanent.
•  » » » » 11 days ago, # ^ |   0 Thanks.
•  » » 11 days ago, # ^ |   +23 So its googleforces :/
•  » » » 11 days ago, # ^ |   0 Agree.
•  » » 11 days ago, # ^ |   0 i just cannot become friendly with XOR, doesnt matter how much i try.
•  » » » 11 days ago, # ^ |   +3 Yea me too. In theory XOR has the same abstract complexity as AND and OR. But I feel like our (at least mine) minds don't understand XOR the same, natural way they understand AND and OR. Also XOR has so many weird characteristics that aren't easy to come up with on spot.
•  » » » » 11 days ago, # ^ |   0 exactly, XOR questions according to me are hard to visualize, but AND and OR are so easily visualized...
•  » » 10 days ago, # ^ |   0 for m segements, [l, r], we can just think it as there is a x in the array, no matter the position.
 » 11 days ago, # |   +10 How to solve D1?
•  » » 11 days ago, # ^ |   +64 Sorry for my poor English.Let we call $b_i=\gcd(a_1,\cdots a_i)$,then we have $b_i|b_{i-1}$.And $b$ is like $[c,\cdots c,d,\dots d,e,\cdots]$.$dp_i$ Means the max value when you choose all $j$ That $i|a_j$.Add some $i$ after $[\cdots,ki,\cdots,ki]$,so $dp_i=\max(dp_{ki}+i(t_i-t_{ki}))$ where $t_i$ means $\sum\limits_{j=1}^n[i|a_j]$.Then we can solve it in $O(a\log a+n\sqrt a)$.
 » 11 days ago, # |   -45 D1 was really interesting!
•  » » 11 days ago, # ^ |   +5 Really curious to know, How to do it ?
•  » » 11 days ago, # ^ |   -9 This is certainly not the right place to talk about it but I saw you video reviewing profile of users, I am stuck in green here. Would be glad If you could suggest something. Many thanks
•  » » » 11 days ago, # ^ |   0 I don't have a lot to suggest. It seems like you left CP for a long time. Anyway, if you continue to solve problems in rating [1300:1500], you should be good to go. Also, up solving at least 1 problem after every contest is a must.
 » 11 days ago, # | ← Rev. 2 →   +5 How to solve D2 ? Does it involve the fact that we only have to consider atmost 25 distinct elements?
•  » » 11 days ago, # ^ |   +15 I didn't use it . I just made some small constant optimization on the code of D1 . If so , I think there is no need to set D2 ...
 » 11 days ago, # |   +5 Problem B, i figured out total time, but how can i print the vector? Divan's office at 1 and then sort given vector in decreasing order, then v[0] at 2,v[1] at 0, v[2] at 3 v[3] at -1 ....
•  » » 11 days ago, # ^ |   +3 you can sort a vector> where the first element of each pair is the value, and the second element is the original index. In such way you can preserve the information of the original index.
•  » » » 11 days ago, # ^ |   0 Thank You so much
 » 11 days ago, # |   0 Hi everyone, sorry to bother but :( in the contests I participated in during this time, the codeforces page loads very slowly :( this prevented me from submitting my post C at the last minute can anyone give me some advice.
•  » » 11 days ago, # ^ |   0 Try submitting using Codeforces Tool, or through these mirror sites:
•  » » » 11 days ago, # ^ |   0 I tried but it's not loading MathType.
•  » » » » 11 days ago, # ^ |   0 You can use the main site for viewing problem statement, while using the mirror sites for submission :P
 » 11 days ago, # | ← Rev. 5 →   -11 Help needed!!!! In q.2 of today's contest I have made a submission :https://codeforces.com/contest/1614/submission/137006738Above is the code ,I surely believe that there is some system error that's why it is giving me wrong answer on test case 4 ,which passed when I made some meaningless changes,in short can someone tell me why this code is not passing because I have made this submission after 13th minute ,so if this code passes then I get a very good rank as compare to now...please help
•  » » 11 days ago, # ^ |   0 Did you forget to use long long ?
•  » » » 11 days ago, # ^ |   0 No i have used it. https://codeforces.com/contest/1614/submission/137006738 you can check it here @vaaven please help!!
•  » » » » 11 days ago, # ^ |   +11 "#define ll int"
•  » » » » » 11 days ago, # ^ |   0 ohk thank you my bad
 » 11 days ago, # | ← Rev. 3 →   0 Can someone help me understand why https://codeforces.com/contest/1614/submission/136996986 got TLE? its O(nlogn).EDIT — Seems like many people who used Python TLE'ed this problem.
•  » » 11 days ago, # ^ |   0 Yes, this is happen with me as well. Other language with nlog(n) passes all the test case while python fail
•  » » 11 days ago, # ^ |   0 I guess it's because of print(*ans)Use join, it's faster: print (' '.join(map(str, ans))
 » 11 days ago, # |   0 D is such a funny problem. The difference between D1 and D2 is that max(a_i) difference is about 4 times bigger. Time for ConstantForces
•  » » 11 days ago, # ^ |   0 Author's solutions have different asymptotics for D1 and D2.Editorial will be ready soon.
•  » » » 11 days ago, # ^ |   +16 I hope it isn't max(A_i)^3/2 and max(A_i)log(max(A_i)).
•  » » » » 11 days ago, # ^ |   +1 It is D1: max(A_i) * log(A_i) D2: max(A_i) * log(log(A_i))
 » 11 days ago, # | ← Rev. 3 →   +63 My D2: TLE on test 1[main tests] https://codeforces.com/contest/1614/submission/137008202
 » 11 days ago, # |   +2 Started 1 hour late Happy that solved A,B in 15 min. Figured out C quick Forgot to take MOD in final answer for C Moral: No matter what happens, even if it's a life and death situation, never forget to take MOD :(
 » 11 days ago, # |   0 Help needed!!!! In q.2 of today's contest I have made a submission :https://codeforces.com/contest/1614/submission/137006738Above is the code ,I surely believe that there is some system error that's why it is giving me wrong answer on test case 4 ,which passed when I made some meaningless changes,in short can someone tell me why this code is not passing because I have made this submission after 13th minute ,so if this code passes then I get a very good rank as compare to now...please help
•  » » 11 days ago, # ^ |   0 line 4 #define ll int and your "meaningless changes" include changing it to #define ll long long int
•  » » 11 days ago, # ^ |   0
 » 11 days ago, # |   0 How to approach and solve D1 and D2?Thanks in advance.
 » 11 days ago, # | ← Rev. 2 →   0 Is it possible for pretests to have a worse max runlength than systests? I remember being concerned that both my B and C solves took more than 600ms (vs. tight-for-python 1s TL), but now the latter is down to 327ms after systests.edit: not a complaint, just hoping to diagnose an issue if there is one... either I'm wrong in assuming systests include pretests, or there was a problem that resulted in wild swings in runtimes (independent of actual individual complaints)
 » 11 days ago, # | ← Rev. 2 →   +12 Why this submission in C++ 17 gives TLE for D1 And the similar solution to it C++ 20 passes within the given time limits even though the worst case runtime for both the solutions is same.Why changing in different version of C++ has so much big difference in runtime and if so then should the problem not have much flexible time limits as you can see it cost me an extra penalty just because I choose C++17 version initially
 » 11 days ago, # |   0 C is segment tree range-AND for each segment with their beauty and then XOR-sum in O(n) right ? Got TLE on test case 2 sadge
•  » » 11 days ago, # ^ | ← Rev. 3 →   +7 Doesn't actually need to be this complicated. If X is the bitwise OR of a segment, then for each set bit of X, there exists an element with that bit set. Then consider all subsequences excluding that element (2^(n-1) of them): they either XOR to 1 or 0 times 2^(bit). If they XOR to 1, then subsequence with our set bit XORS to 0; if they XOR to 0, then subsequence with our set bit XORs to 1. Either way, we are guaranteed a contribution of exactly 2^(bit) times 2^(n-1) from that bit, i.e. its contribution to x. So we just need to know if a given bit is set anywhere in the whole sequence, and if so we add that contribution. Otherwise, the bit is skipped.In pseudocode terms ans = 0 For each segment: get(l,r,x) ans |= x ans *= 2^(n-1) (Take mods where appropriate)
•  » » » 11 days ago, # ^ |   +8 I wonder how I miss that while still understanding we can do XOR-sum in O(n) for kinda the same argument. Thank you that was helpful.
•  » » » » 11 days ago, # ^ |   0 I actually missed it in contest too. I did a brute force over each bit, setting only those I had to set to 0 (i.e. where we had information on a whole segment that the bit was 0). From there I applied some combinatorics.This was all a bit of a waste of time, and my solution just scraped through in the 1s limit.I later realised that, by symmetry, all my combinatorics effectively came out at "half of all subsequences" for any set bit.
•  » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 I guess for Question C, the question should have also asked for the possible values of elements of array, so that Lazy_propagation would have become necessary.Here's my submission by which we can also print possible values of array.
•  » » » » » » 11 days ago, # ^ |   0 lazy propagation wouldn't be "necessary" strictly speaking, because you can apply all the range updates before printing the array
•  » » » » » » » 11 days ago, # ^ |   0 Actually I used LAzy propagation in Segment tree for range updates. So I guess it's necessary.
•  » » » » » » » » 11 days ago, # ^ |   0 You can do offline range update (i.e. process all the range update operations, then print the array) without lazy propagation segment tree
•  » » » » » » » » » 11 days ago, # ^ |   0 Oh Thanks
•  » » » 11 days ago, # ^ |   0 I did exactly that still got WA on pretest 3. Any idea why?
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   0 Need long long, not int, I think. When you’re multiplying two ints together you’re potentially getting an overflow before you MOD them.
•  » » » » » 11 days ago, # ^ | ← Rev. 2 →   0 but, I have defined #define int long long in the beginning (around 5th line)
•  » » » » » » 11 days ago, # ^ |   0 Sorry you're right. You shouldn't MOD your value o.
 » 11 days ago, # |   -30 worst problemset i've ever saw...
 » 11 days ago, # |   +2 Very great contest,but I think the time limit for C can be 2s.
 » 11 days ago, # |   +14 Finally Specialist Today !!!!
•  » » 11 days ago, # ^ |   0 So seems like you aren't a loser anymore! :)
 » 11 days ago, # |   0 In problem B, I failed for the error message for the pretest: "wrong answer answer is wrong: pans = 14 is not equal real_pans = 18 (test case 1)" But the example output is 14 for the test case 1. I checked many acceptable submissions, the answer is still 14 not 18. Do I miss something?
•  » » 11 days ago, # ^ |   0 optimal answer is 14 but your output array will give 18 that's why it is showing 18..
 » 11 days ago, # |   0 Tester: "As a tester, I tell you that the problems are well balanced and well prepared!!" CF User: "Ok I will participate then" Tester IRL
 » 11 days ago, # |   +11 Passed pretests of D2 only to see failing on sample in system testing. -,-
•  » » 11 days ago, # ^ |   0 I know right. I literally did some stupid optimization and passed D2 right now. To be honest, look at the time variance of any code from any test although solution is independent of N. The time variance is just too large sometimes reaching 500ms in that problem for no reason.
•  » » 11 days ago, # ^ |   +3 Just noticed system test was run for 3rd time. (Pretest passed, TLE2 on 1st ST, TLE18 on 2nd ST, AC on 3rd ST). What is going on? :|
•  » » » 11 days ago, # ^ |   +5 I guess they decided to give people a fair go (i.e. when the servers weren't overloaded)
•  » » 11 days ago, # ^ |   +5 My submission TLEs on different test each time I resend it... Time limits should either be tighter or looser.
 » 11 days ago, # |   0 137041121 137027753 This is not ok. One parnthesis off
 » 11 days ago, # |   0 Still don't get problem 2. I was the only one who struggled due the errors in the examples?
 » 11 days ago, # |   0 Can anyone please explain why this solution of mine for problem B is getting TLE 137017820
•  » » 11 days ago, # ^ |   0 large input/output causes TLE, use this instruction before write anything in the main function:ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) ;
 » 11 days ago, # |   -14 Why do you set the minimum temperature of question e to 0? Why is it not 1 or -1e9? The important boundary information is written so unobviously, fuck.
 » 11 days ago, # | ← Rev. 3 →   0 I can't understand the verdict of [problem:1614B]problem B in my code? https://codeforces.com/contest/1614/submission/137041237
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 Can you check my code?
•  » » » 11 days ago, # ^ |   0 check your answer manually it's coming wrong..
•  » » 11 days ago, # ^ |   0 2 5 4 3 1 0 Your array outputs: (3*2)*3+(2*2)*8+(1*2)*10+(1*2)*6+(2*2)*1 = 86 which is not the correct answer.
 » 11 days ago, # |   +16 What a painful lesson to learn that $2^{30} > 10^9+7$. (Problem C)
 » 11 days ago, # |   +3 Was this the intended solution for D1? I used 1D DP over all the possible factors of all the numbers. https://codeforces.com/contest/1614/submission/137040944
 » 11 days ago, # |   0 I wrote a dp solution for probleme [problem:https://codeforces.com/contest/1614/problem/C] , while the complexity of my code should work just fine, the time constraints didn't fit [submission:https://codeforces.com/contest/1614/submission/137034593], changing from long long to int, made the solution pass just fine [submission:https://codeforces.com/contest/1614/submission/137043656] , it's been a while since the last time I encountered such a problem.I know It's not the intended solution, but mine should be accepted too, or what do you think?
•  » » 11 days ago, # ^ |   0 NVM, both get AC now.
 » 11 days ago, # | ← Rev. 5 →   0 I would like to ask if system test slower than pretest?When I solve problem C, it says pretests passed (12 test cases) and the time cost is about 820 ms. After carefully consideration, I decided to move on. But I finally failed the system test, and the maximum time cost for first 12 test cases is 951ms. (And it finally failed test case 15). If I get 951ms in the pretest, I will try to optimize my code.I see in comment section that @iaNTU failed the first test case in the system test with problem D2, he must passed test case 1 in the pretest, that is why I ask this question. UPD: Thanks god, my contest code get AC after rejudgement.
 » 11 days ago, # |   +4 Problem COrigial problem at Leetcode 1863
 » 11 days ago, # | ← Rev. 2 →   0 Was there no pretest in C for the max N? my code TLE'd on test 17. it was O(NlogN*logN) and maybe it can be optimised but I didnt try as the pretests passed. Please try to include max N in pretests. Nice problems thoEdit: submission rejudged it is AC now
•  » » 11 days ago, # ^ |   0 You should always check the max N by yourself, e.g. via the Custom Invocation. There has to be some area for hacking lol
•  » » » 11 days ago, # ^ |   0 my bad, the submissions are rejudged, i should not have commented before the contest was officially over
 » 11 days ago, # |   0 The contest had some really nice problems and problem C ahh I feel so sad that I forgot to mod after the multiplication of or_of_all_elements*2^(n-1) and like ugh I feel really disappointed, rating's gna drop for sure! After the contest, I was talking to my friend and he told me, dude you forgot to mod and then I was like \$h!t such a stupid bug. Overall the contest was really nice orz.
 » 11 days ago, # |   +1 Can there be more than 1 answer in problem C?
•  » » 11 days ago, # ^ |   0 I don't think so. Howsoever the distribution of bits across all N elements is, in the end, it only matters if a particular bit is set in any of the N elements.
•  » » 11 days ago, # ^ |   0 don't know but there can be multiple possible values of array, of which one could have been asked to print to make the question better.
 » 11 days ago, # |   0 How to solve D?
 » 11 days ago, # | ← Rev. 2 →   +27 Tutorial video by Retired_MiFaFaOvO (in Chinese)
•  » » 11 days ago, # ^ |   0 I wish I knew chinese
 » 11 days ago, # |   0 Hi, there is a chinese tutorial.Welcome to watch and correct(dls tydy
 » 11 days ago, # |   +5 Originally I wrote a solution for problem E which passed pretests, but resubmitted later because I was scared about TLE. Glad I did, because even my faster submission took 1996 ms! (https://codeforces.com/contest/1614/submission/137021260)
 » 11 days ago, # |   0 Can someone share their idea of dp solution in D1?
 » 11 days ago, # |   +12 I am no Psychologist, but brah this Divan has some serious problems..
 » 11 days ago, # |   0 Lol, the number of upvotes of this post is getting fewer and fewer
 » 11 days ago, # | ← Rev. 2 →   0 .
 » 11 days ago, # |   -6 I hope there will be more rounds like this.
 » 11 days ago, # |   -10 I have a pupil title on the site how do I cheat from newbies?
 » 11 days ago, # |   0 today, will giving the contest my code coincides with the kingkd code. Sorry for the voilation of the rule but this will not happen again as kingkd id(iamstupiddude26@gmail.com) is my previous id only which due to some reason i lost it,but few days ago i got my id password back so mistakenly given the contest with same id, this will never happen again and i will permanently close my kingkd id, sorry for the voilation of the rules, please provide a last warning.
 » 11 days ago, # |   -12 MikeMirzayanov Have you forget to update the ratings?
•  » » 11 days ago, # ^ |   0 means
•  » » 11 days ago, # ^ |   0 please forgive the mistake one time.
 » 11 days ago, # | ← Rev. 3 →   +1 kingkd and ayushkedia0511 are both my id because kingkd is my old it which is lost but i got it and mastakenly i gave the contest with both id, for for the voilation of rules and i will not use my old (kingkd ) id for more contests
•  » » 11 days ago, # ^ |   +6 looking at your code, i realised that you submitted your code with kingkd untill you got accepted, and then you submitted with ayushkedia0511.it's 100% obvious that you used two accounts in purpose but now you are still lying that it was an mistake.
•  » » » 11 days ago, # ^ |   0 I wanted to say I don't know that I can't use to accounts if you will see my kingkd account only 4 submission are there , I used it after a very long time and this time I am only experimenting and this account banned happened
•  » » » 11 days ago, # ^ |   0 That's why I am requesting to give a chance because I don't know about this
 » 11 days ago, # |   0 When will be the editorial published? I think this is already late.
 » 11 days ago, # | ← Rev. 3 →   +2 Please Update the Ratings . I want to see myself as a Specialist Today :_: before i go to Sleep it Late night in here in India.. Also jee main paper Doesnt decide your Future
 » 11 days ago, # |   0 Can someone help me figure out why these 2 similar solutions for D2 are giving different results? Is there some optimisation I'm missing?Passing: 137049637 Not passing: 137046389
•  » » 11 days ago, # ^ |   +5
•  » » » 11 days ago, # ^ |   0 Thanks! interestingly it's not just the compiler but also changing long long -> int. Seems like there were some razor thin time limits.64 bit compiler with long long instead of int: 137063729
•  » » » » 11 days ago, # ^ |   0 There is too much unnecessary use of long long, use int instead and then you should be fine.
 » 11 days ago, # |   -75 There must have been something special about your round since Retired_MiFaFaOvO took it (his first cf contest in almost 2 years). Congrats on getting this legend back!
 » 11 days ago, # |   0 D problem was tricky.
 » 11 days ago, # |   0 Hey! Can anyone please explain C problem. I know it is easy but i didn't get it properly.
 » 11 days ago, # |   +6 Here are two of my exact same submissions, which differ by almost 600ms in runtime. Before this, one submission got TLEd on the first submit, and then the same code got accepted on submitting it again. 137066206 and 137066133Are such large differences common? It seems to me that something is up with the judge.
•  » » 11 days ago, # ^ |   +5 hope this gets upvoted, the D2 time limit was really too low. See also this comment
 » 11 days ago, # |   0 Auto comment: topic has been updated by 4qqqq (previous revision, new revision, compare).
 » 10 days ago, # |   0 nice problems, bad contest
 » 10 days ago, # |   0 How to solve D2? I cant think of any other way than computing dp for all divisors. I used the same D1 code, compute the factors only if required. But still got TLE. submission. I also tried to create an array of divisors for all 2e7 integers with complexity 2e7 * number of divisors. Optimized to compute only where all of the prime factors of this number is <= to the max number of prime factors. There I got MLE submission. So how to solve it ?
•  » » 10 days ago, # ^ |   0 You can create prime tables in $\mathcal{O}(2e7)$ and the we can enumerate prime's multiples. Submission
•  » » 10 days ago, # ^ | ← Rev. 2 →   +4 We can take primes using classic sieve. This is fast enough. Instead of taking multiples using a sieve-like approach, we can count multiples using $sqrt(val)$ factorization. For the dp state transition, it is enough to check for "prime steps" (i.e, instead of looking at $2*i$, $3*i$, $4*i$ ..., just look for $2*i$, $3*i$, $5*i$, $7*i$, ... is enough). Reason is that this prime multiples (or steps) has already taken into account the composite steps. Example is when you are at $dp(5)$, you can look at $dp(10)$, $dp(15)$, $dp(20)$. But $dp(10)$ has already looked up to $dp(20)$ earlier, plus it's easy to see that $dp(i)$ >= $dp(i * k)$ where $k$ is some constant. So going for a composite check is unnecessary.
 » 10 days ago, # |   0 mysubmissionwhat's wrong with my code,can anyone help me?? thanks in advance
•  » » 10 days ago, # ^ |   0 I think res[i+1]*a[i] is an int multiplication which overflows in your example
•  » » » 10 days ago, # ^ |   0 Yes,it got accepted now
 » 10 days ago, # |   +3 In question B, it is given how the businessman will travel for first 10 years(5256000 minutes) only. And it is asked to choose the cordinates such that it minimises the time for walking within first 10 years only, no info. about what to consider if he can't visit every building in that time, what to print in that case the minimum time < 10 years by visiting only some good buildings or just try to minimise the time only if buildings can be travelled within 10 years or something else can't decide
•  » » 10 days ago, # ^ |   0 Same Doubt
 » 10 days ago, # |   0 anyone can explain to me C Problem Properly.
 » 10 days ago, # |   0 Submission for problem D1Can anyone explain the time complexity analysis of this solution and also in general for any dp solution. I become little confused sometimes while calculating time complexity of a dp solution.Thanks in advance:)
 » 10 days ago, # | ← Rev. 2 →   0 Submission for CCould anyone please explain what's wrong in my code? I applied the exact same approach as in the editorial. Thanks in advance. Upd: Found my mistake.
 » 10 days ago, # |   0 Here's my apology for the mistake I had in the contest.Please pardon me this time.https://codeforces.com/blog/entry/97309
 » 10 days ago, # |   +6 Could someone tell me how to get the table cnt[x] where cnt[x] denotes how many numbers are there which are divisible by x in o(nloglogn ) or in o(n)