### Osama_Alkhodairy's blog

By Osama_Alkhodairy, 17 months ago,

Hello Codeforces!

We are glad to invite you to Codeforces Round #613 (Div. 2), which will be held on Jan/10/2020 17:05 (Moscow time). The round is rated for Div. 2 contestants. There will be six problems with a duration of 2:15

The problems were prepared by me, mohammedehab2002, DeadPillow, and MikeMirzayanov.

I'd like to thank awoo for coordinating the round, dorijanlendvaj, aryanc403, Ari, nooinenoojno, defolaut, Pavlova, mahmoudbadawy, zoooma13, Mohammad_Yasser, Rox, and BledDest for the invaluable testing, and MikeMirzayanov for great Codeforces and Polygon systems.

Good luck!

UPD1: We decided to add one more problem and extend the duration to 2:15 to make the contest more balanced.

UPD2: Score distribution: 500-1000-1250-1750-2250-3000

UPD3: Editorial is out.

UPD4: Thanks for participating! Congratulations to the winners:

Div. 1 (unofficial) participants

Div. 2 participants

• +401

 » 17 months ago, # | ← Rev. 2 →   +2 Cyan setters are all gone but it'll be good round.
 » 17 months ago, # | ← Rev. 2 →   +34 I don't think I've ever seen a shorter contest announcement beforeEDIT: Hope the statements are as short as the announcement
•  » » 17 months ago, # ^ | ← Rev. 4 →   -15 There was such a short announcement before. But it became longer as details have been added. Perhaps this announcement will be the case too. Anyway I hope the description of the problem is as simple as this announcement at the upload.
•  » » 17 months ago, # ^ |   0 I hope so! And the tasks will be easier than others in early contests
 » 17 months ago, # |   +5
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 [hashtag]deferredgang
 » 17 months ago, # |   +31 as always hope for interesting and SHORT STATEMENT problems!
 » 17 months ago, # |   +152 Waiting for XOR problems.
•  » » 17 months ago, # ^ |   +5 it's illegal
 » 17 months ago, # | ← Rev. 2 →   +22 Osama_Alkhodairy's fan club members are so proud of you <3
•  » » 17 months ago, # ^ |   0 It would be more difficult to solve...
 » 17 months ago, # |   +5 I always like that type of question which has no story.
 » 17 months ago, # |   0 It will be a nice round
 » 17 months ago, # |   -10 Arabic round :DI will participate for sure
 » 17 months ago, # | ← Rev. 4 →   +18 I look forward to more XOR questions from mohammedehab2002Fantastic job at setting the questions !$F$ looks like a classical question but somehow I am not able to figure out how to do it. Surely, there must be similar Project Euler questions ?
•  » » 17 months ago, # ^ |   0 It's Ehab. Please correct. I still remember the Ehab and expected XOR problem. That was my best contest so far.
•  » » » 17 months ago, # ^ |   +3 Thanks for the correction !
 » 17 months ago, # |   +12 5 problems... I think it will be good contest
 » 17 months ago, # |   +36 I predict that there will be a gap between problem C and problem D Let's see (:D
 » 17 months ago, # |   +14 Egyptian!! I'm so proud ❤
 » 17 months ago, # |   +16 An Egyptian round! :D I can't wait to see how good the problems will be tomorrow <3
 » 17 months ago, # |   +5 Where the cyan gang at?
 » 17 months ago, # |   +20 so proud of you guys , keep going <3 <3 i love Egypt
 » 17 months ago, # |   +8 Egyptian contest Of course i will participate ❤️
•  » » 17 months ago, # ^ |   0 Good Luck for All Egyptians :)
 » 17 months ago, # | ← Rev. 3 →   0 Hope to become newbie after this round.
 » 17 months ago, # |   +1 Hope pretest passed => system test passed
•  » » 17 months ago, # ^ |   +4 *pretest passed >= system test passed
•  » » » 17 months ago, # ^ |   0 I really hope that was a joke
 » 17 months ago, # |   +34 I know we're not a big audience, but it would be nice to have some contests at viable times for those in the PST time zone (California) :) I feel like most contests in the past year have started between midnight and 6:30 AM for us.
•  » » 17 months ago, # ^ |   0 Thanks for calling it out!
•  » » 17 months ago, # ^ |   +3 I'm in California too and I totally agree. The convenient thing is, at the very least, 6am contests are generally before school/work.
 » 17 months ago, # |   0 Nice Five
 » 17 months ago, # |   0 Very nice First Arabic round for Me
 » 17 months ago, # |   +52
 » 17 months ago, # |   0 Expected suitable problems .
 » 17 months ago, # |   +4 nice day, atcoder -> codeforces, two contests
 » 17 months ago, # |   0 Waiting for short problem !!!
 » 17 months ago, # |   0 What's the score for each problem?
 » 17 months ago, # | ← Rev. 2 →   0 Thanks for the sixth problem. You are the best
 » 17 months ago, # |   0 means the added problem can be solved in 15 minutes hope the problem added would be moderateUPD1:
•  » » 17 months ago, # ^ |   +4 It means that the added problem can be solved by the top level in 15 minutes.I expect the added problem to be C or D. Likely, the middling finishers will do A,B, and possibly C, then looking at the old next problem with over an hour left, they would find it nearly impossible. However, with this added problem, these middling finishers can now attempt to solve the added problem, with the hour they have left.
 » 17 months ago, # |   0 means the added problem can be solved in 15 minutes hope the problem added would be moderate
 » 17 months ago, # |   +17 I am getting feels that many solutions will fail on system tests.
 » 17 months ago, # |   0 The problem statements are as short as the announcement was.
 » 17 months ago, # |   +5 How to Solve D?
•  » » 17 months ago, # ^ | ← Rev. 2 →   +11 Trie + dp:You build a trie bit by bit with the first edges corresponding to the most significant bits. after that, you define dp[node] = minimum-maximum for the numbers in this subtrie(i made this word up) if you don't consider the first bits(up to the one corresponding to our node). The edge cases when you only have one child are easy. After all the subtrie which will have the opposite bit is gonna be the one which determines our answer so all you need to do is "dp[nod] = min(dp[child1], dp[child2]) + our current power of 2" and that is it.
•  » » » 17 months ago, # ^ |   0 could you elaborate ?
•  » » » 17 months ago, # ^ |   0 Can you explain more in detail?
•  » » 17 months ago, # ^ |   0 Hint — If I have atleast one number where ith bit is 0 and another number where ith bit is 1, I can't avoid having answer lesser than 2^i.
•  » » » 17 months ago, # ^ |   +7 I found that, but because many bits are connected, I couldn't reach the solution.
•  » » 17 months ago, # ^ |   +6 No dp required. Complexity will be O(NlogN). Let solve(vec,bitpos) indicate the answer , Now if all the numbers in the vector have same bit set/unset recurse solve(vec,bitpos — 1). Else answer is 2^bitpos + min(solve(vec1,bitpos-1),solve(vec2,bitpos-1)). Where vec1 and vec2 are vectors having the current bit set/unset respectively.Proof?: If X has current bit set answer has to come from the opposite set ( having bit complementary to X). This is because the numbers belong to the set having same bit parity can never contribute higher minimax that the complementary set.
 » 17 months ago, # |   +1 What is the pretest 6 on problem D?
 » 17 months ago, # |   +4 Pretest 2 of B?
•  » » 17 months ago, # ^ |   +1 It was just maximum subarray sum without including [1,n]
•  » » » 17 months ago, # ^ |   0 Yeah, i got that. But i don't know why my solution was failing.
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 if maximum subarray sum is equal to total sum by kandane's algo then subtract minimum of minimum of prefix sum and minimum suffix sum. If sum becomes less than previous sum then print yes else no . It took me 4 WA's to realise this case.
•  » » » » » 17 months ago, # ^ |   0 when sum get's equal i subtracted min(ar[0],ar[n-1]) from maximum subarray sum
•  » » » » 17 months ago, # ^ |   0 Try this: 1 3 1 1 0 
•  » » » » » 17 months ago, # ^ |   0 NO?
•  » » » » 17 months ago, # ^ |   0 3 0 0 100
•  » » » » » 17 months ago, # ^ |   0 answer will be no, right??
•  » » » » » » 17 months ago, # ^ |   0 yes
•  » » » » » » » 17 months ago, # ^ |   0 my code was working even for this case
 » 17 months ago, # |   +19 How to solve E?
•  » » 17 months ago, # ^ |   -22 think when does removing a segment actually increases the answer. think about difference arrays (of what? think about that too xD). just saying, but in both [1,10] [2,15] [3,17], and [1,10], [2,15], [12, 17], remove the middle segment and see?
•  » » 17 months ago, # ^ |   +5 Sort all points in increasing order, process them from left to right, keep a set of segments. If a segment starts at a give point, add to the set and vice versa. When number of segments changes from 2 -> 1 -> 2, we update increase[index]++ where index is the index of the segment when the num segments were exactly 1 in the pattern 2 -> 1 -> 2.Answer is number of union set without removing + max_element of increase.Hope I explained it fine.
•  » » » 17 months ago, # ^ |   +10 Honestly I had the same idea, but after atcoder got a bit too lazy to implement it...
 » 17 months ago, # |   0 What's the pretest 2 of question B?
•  » » 17 months ago, # ^ | ← Rev. 4 →   0 did you try case of considering only first element ? When i was implenting kadane's algo i forgot to test dp[0] in max() , hence got wrong answer. But after considering dp[0] i got right answer.Wrong submission: https://codeforces.com/contest/1285/submission/68526435 Right submission: https://codeforces.com/contest/1285/submission/68528340Note: this is pending system tests, might still be wrong
 » 17 months ago, # | ← Rev. 2 →   0 In problem D 1285D - Dr. Evil UnderscoresThe answer always will be $2^x$ where x is an integer between 0, 30 right ? I came with this idea but I don't know whether its correct or no
•  » » 17 months ago, # ^ |   +1 I tested this case:510 13 16 20 26and I found the answer is 20, which is not the power of 2.
•  » » » 17 months ago, # ^ |   0 Oh my idea turns out to be wrong Thanks for your help :)
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 NO, take $n=7 ,arr =$ $1,2,3,4,5,6,7$
•  » » 17 months ago, # ^ |   +1 Not true. Consider the input 4 0 1 2 3 Answer is 3
 » 17 months ago, # |   +2 i have a feeling all my solutions will be wrong in system tests lol
 » 17 months ago, # | ← Rev. 2 →   -10 Recursion.....uggggh
 » 17 months ago, # |   +14 xorforces lcmforces, great contest, thanks!
 » 17 months ago, # | ← Rev. 5 →   +7 task-B -> find maximum subarray sum for a[0..n-1] and a[1...n-1] take the max of those 2 and compare with array sumtask-C -> find the divisors and store them in vector. Now by brute-force check every pair of elements and output the answer.EDIT: My C failed :(
•  » » 17 months ago, # ^ |   0 for problem B wouldn't your sol is O(n^2)
•  » » » 17 months ago, # ^ |   0 No its O(n). Search for Kadanes algorithm for maximum subarray sum. :)
•  » » » » 17 months ago, # ^ |   0 Yeah but you are searching for max subarray for 0 to n-1 to [n-2,n-1] right? So you are calling kadanes n time right ?
•  » » » » » 17 months ago, # ^ |   0 No i calculate once for a[0 ... n-1] and once for a[1 ... n]
 » 17 months ago, # |   0 What was Pretest 5 for C? and is the answer for 999999999999: 999999 1000001
•  » » 17 months ago, # ^ |   0 Try : 8
•  » » » 17 months ago, # ^ |   0 Its 2 4 ?
•  » » » » 17 months ago, # ^ |   0 should be 1 and 8 since lcm of 2 and 4 is 4 instead of 8
•  » » » » » 17 months ago, # ^ |   0 Oh no! Made a blunder.
•  » » » » 17 months ago, # ^ |   0 It should be 1 8
•  » » » » 17 months ago, # ^ |   0 LCM of $2$ and $4$ is four, not $8$
•  » » » 17 months ago, # ^ |   0 It's giving 1 8
•  » » » » 17 months ago, # ^ |   0 Can you share your approach?
•  » » » » » 17 months ago, # ^ |   0 If x is even: then loop through 1 to sqrt(n) and find a number(k) which is greater than x/4 and smaller than x/2. If number not found answer is 1 and X otherwise k and x/2 If X is odd: then loop through 1 to sqrt(n) and find number which is divisible by X and form the optimal pair(min of max(a,b) where a = divisor and b = quotient)
•  » » » » » » 17 months ago, # ^ |   0 Try: 49
•  » » » » » » » 17 months ago, # ^ |   0 Gotcha. It's giving 7 7
•  » » » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 That is definitely incorrect... You are making a mistake of including sqrt(X) in the loop which shouldn't be because, in case of perfect square number, this will always lead to two same factors.
•  » » » » » » » » » 17 months ago, # ^ |   0 How did you come up with this number?
•  » » » » » » » » » 17 months ago, # ^ |   0 Two same factors will make the that number as LCM which is not X which is the target.
•  » » » » » 17 months ago, # ^ |   0 Approach for C is simple.find set S={Pi^ci: Pi is prime divisor of N. ci is integer >0} it's guarantee that no of distinct element in S can't be more than 15. Because 15!>10^12.Now you have to partition this set into two half(say S1 and S2) and find a partition such that max(x,y) {where x=product of no in S1 and y=product of no in S2} is minimum.since |S|<=15 you can use Bit-masking for finding such portioning or just do recursion.
•  » » » » » » 17 months ago, # ^ |   0 Hey, my number theory is weak, Can you suggest me some good resources?
 » 17 months ago, # |   +9 How to solve D? Explain for me, plz
•  » » 17 months ago, # ^ | ← Rev. 2 →   +4 One way is to use a prefix trie. If you are at a node at the i'th bit, if there is only one valid edge, say a 0, then that means you can take a 1 without increasing the max xor. If there are two valid children, then that means no matter if you pick a 0 or 1, you will have to increase the max xor by 2^i. So, you can just add 2^i to your answer, recurse on the child nodes and take their minimum.
•  » » 17 months ago, # ^ |   0 Note that the answer won't exceed than 30 bits.Starting from 30th bit, check if the numbers in the array have the same bit on the 30th bit or not. If yes, it is possible to put the same bit in X to make minimum XOR-SUM.If not, then we can put either 1 or 0 in X at the 30th bit. If the 30th bit is set 1 in X, then all the numbers in the array with 30th bit as 1 will not give max XORSUM. Hence form a new array with the numbers having 0 as the 30th bit, and continue further towards 29th bit. Similarly, for 30th bit as 0 in X can be handled and take the minimum of them.I handled it recursively. LINK TO MY SOLUTIONP.S. Don't forget to empty the array before starting pushing the array. I wasted 30 minutes to debug that mistake.
•  » » » 17 months ago, # ^ |   0 We have two choices for Every X so it seems that its 2^30 can you correct me?
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 Well, if you would observe closely, every number in the array will be appearing the same number of times as the number of bits.It is (n*lg(n)), since lg(n) bits are there which is 30 here. The choice of the bit at a particular position also reduces the size of the array, though it's really difficult to explain.
•  » » » » » 17 months ago, # ^ |   0 can you elaborate more how the complexity is n*lg(n) ?I think it should be n^2 according to your explanation
•  » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 at every choosing position, we divide the current array into two parts one with on bit elements and another with off bit.thus it become log(N) with total complexity of O(N log N).
•  » » 17 months ago, # ^ |   0 Let's use a Binary trie. Insert all N numbers in the trie. If a number has its 30th bit on then it goes to the right of the root, else goes to the left. similarly at the next level we'll make decision for the 29th bit and so on.After you have inserted all numbers in the trie, consider what is the answer for a particular subtree.if the root of the subtree has only one child that would mean all numbers under consideration have this bit either on or off and hence we may choose a number such that our answer will have this bit off. In this case answer will the same as the childAns.if the root of subtree has two children then numbers under consideration belong to both bit on and off categories and hence no matter what number we choose this bit will definitely be on in our answer. In this case the answer will be (1<
•  » » 17 months ago, # ^ |   0 Alternative soln without trie: Sort all the elements. Let solve(l, r, pos) be the function which gives the answer for the range [l, r] considering only pos least significant bits. Now, observe that most significant bit will be 0 first then 1 in the sorted order. Let f the last position of 0 bit. Now, you can do recursive calls to solve(l, f, pos-1) and solve(f+1, r, pos-1) and then take the answer as (1<
 » 17 months ago, # |   +4 Thank you for quality problems. Had fun
 » 17 months ago, # |   +31 F. Classical?Yes.
•  » » 17 months ago, # ^ |   0 I just copy-pasted code from a problem I solved yesterday :Dd(Simpler solutions exist for sure though)
•  » » » 17 months ago, # ^ |   +16 In our defense we had no knowledge of this problem and it only appeared recently. But I agree it does look like a google-able problem, But we didn't find any similar problems so we though why not. I would like to see if there is an old problem with similarities to this one.
 » 17 months ago, # |   +8 How to solve F?
•  » » 17 months ago, # ^ |   -17 This is much similar to F see this
•  » » » 17 months ago, # ^ |   +9 No it is not.
 » 17 months ago, # |   0 it felt that this was the easiest Div2 contest I have ever participate but still... :')
•  » » 17 months ago, # ^ |   0 wait till you get a surprise WA in sys tests lol, i know i will
 » 17 months ago, # |   0 Is Trie without DP enough to pass D?
•  » » 17 months ago, # ^ |   +4 Memoization is not needed here.
•  » » » 17 months ago, # ^ |   0 You didn't even try to answer his question
•  » » 17 months ago, # ^ |   0 Yes
 » 17 months ago, # |   +21 C can be solved by this way:Change the A from [sqrt(X)] to 1, and find A and B in which A*B==X and gcd(A,B)==1. The larger A is, the smaller B is, so when A is first found to satisfy the above conditions, A and B at that time are the answer..
•  » » 17 months ago, # ^ |   +31 Dude, nobody was asking for c solution, why did you put it here?
•  » » » 17 months ago, # ^ |   +13 Because it is related to the competition anyway, and there is no matter.
•  » » » » 17 months ago, # ^ |   0 explain F
•  » » » 17 months ago, # ^ |   +11 Dude, nobody was asking for your opinion, why did you put it here?
•  » » » » 17 months ago, # ^ |   0 its recursion. Dude, nobody was asking your opinion, why did you put it here?
•  » » » » » 17 months ago, # ^ |   0 Why did you reply him, dude? Nobody was adking for your opinion, why did you put it here?
•  » » 17 months ago, # ^ |   0 how you are sure that this will give right answer.. can u explain it more
 » 17 months ago, # |   0 Hello, mango_lassi. Your solution for B is so simple. Can you care to explain?Thank you :)https://codeforces.com/contest/1285/submission/68502173
•  » » 17 months ago, # ^ |   0 Solution for B:Yasser's Score = sum of Ai'sAdel's Score = max sum of subarray of A (Can be found using Kadene's Algorithm, by running from 1 to n-1 and 2 to n.... Since we can't take the whole array sum)if (Yasser's score > Adel's score) Print("Yes") otherwise Print("No")
•  » » 17 months ago, # ^ |   +2 If $\sum a_{i} \leq 0$, Adel can just pick any cupcake with nonnegative tastiness. Answer NO.If some prefix has sum at most zero, Adel can buy all cupcakes not in that prefix. If some suffix has sum at most zero, Adel can buy all cupcakes not in that suffix. Answer NO.Otherwise answer YES. Assume Adel buys the interval $[l, r]$. Then Yasser's tastiness minus Adel's tastiness is $sum(1, l-1) + sum(r+1, n) > 0$, as all nonempty prefixes and suffixes have positive sum, and either the prefix or suffix is nonempty.
•  » » 17 months ago, # ^ |   0 Calculate prefix and suffix sum of arrayif any term in prefix or suffix sum array is less than or equal to 0, then the answer is "NO" else the answer is "YES"
•  » » 17 months ago, # ^ |   0 He did it smartly say the sum of the array is S, Now if prefix sum is less than or equal to 0 then suffix sum must be greater than or equal to S Hence [Fail] As prefix sum + suffix sum = S, Similarly, we can do it for suffix case.Now you may think it may not cover all the cases, Consider any [l,r], Say the cases we stated above doesn't happen, Then sum[0,l-1] > 0, So it is safe to consider [0,r] and you can easily visualize that sum[0,r] won't be greater than or equal to S in any case, As sum[r,n] > 0. Hence we prove that for any [l,r] We won't find sum>=S Hence[Pass]Hope this helps.
 » 17 months ago, # |   +6 When would the system testing start?
 » 17 months ago, # |   +12 it's too late to start system test........
 » 17 months ago, # |   0 https://codeforces.com/contest/1285/submission/68549930 can anybody explain why is this giving wrong answer?
•  » » 17 months ago, # ^ |   +1 The initial value of min is too small. If $X$ has a divisor that is a power of a prime number and this divisor greater than INT_MAX, the correct min will greater than INT_MAX.For example: If $X=10000600009=100003^2$ ($100003$ is a prime number), your solution outputs 4 2147483647, correct answer is 10000600009 1.
•  » » » 17 months ago, # ^ |   0 thank you so much. so basically i missed out on 1100 points because of that
 » 17 months ago, # |   0 The contest was great. But I'm anxious for system test and it's too late.
 » 17 months ago, # |   0 Wow，8000 passed pretest, good number
•  » » 17 months ago, # ^ |   -6 More like: good number in base 10
 » 17 months ago, # |   +8 Anyone feels that C was easier than B
•  » » 17 months ago, # ^ |   0 Yup, C was indeed easier than B
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 B was infact copy-paste from gfg (kadane's algo),tho C required some brain cells Ps: I got accepted B in 6 attempts lol
•  » » » 17 months ago, # ^ |   0 I solve C without much thinking and even though i know B need kadane's algo still i couldn't solve
•  » » » » 17 months ago, # ^ |   0 see my solution for B,I just took care of the condition which requires not to select whole array as subarray. here
•  » » 17 months ago, # ^ |   0 I tried C first than B because I felt it easier and I wasn't sure of my approach of B...But it wasn't a good strategy xd
 » 17 months ago, # | ← Rev. 2 →   0 Good D problem.
 » 17 months ago, # |   0 DeadPillow Tell me the truth. You started the system test late to add the case that breaks my problem F. :P
•  » » 17 months ago, # ^ | ← Rev. 2 →   +5 You'd think so but surprisingly me and mohammedehab2002 were able to handle most heuristics almost right before the contest.
•  » » » 17 months ago, # ^ |   0 DeadPillow Try to break this one: 68691230
 » 17 months ago, # |   +10 Can someone give me a hint for problem F?
 » 17 months ago, # |   +11 Just saw a WA on 159! Time to leave earth!
•  » » 17 months ago, # ^ |   0 I saw 163.. add me too...
 » 17 months ago, # |   +1 Can anyone hack https://codeforces.com/contest/1285/submission/68545833 ?
 » 17 months ago, # |   0 Can anyone explain why the output is to be NO for this case for problem B 1 10 10 5 -12 7 -10 20 30 -10 50 60
•  » » 17 months ago, # ^ |   0 take [20 30 -10 50 60] 20+30-10+50+60 = 10+5-12+7-10+20+30-10+50+60
 » 17 months ago, # |   0 Never use INT_MAX as infinity....today i realised it is smaller than 10^12
 » 17 months ago, # |   +3 After several tries on F, passed in the last second!!! ... System test: What? What did you say?
 » 17 months ago, # | ← Rev. 2 →   +8 Guys , I submitted the second problem( B ) successfully . In the system testing it gives me TLE , on the go I resubmitted the same code and it submitted succesfully . HOW ?? Can anyone explain to me ?
•  » » 17 months ago, # ^ |   0 Quite strange.The TLE code shown is accepted. I think, you must tag admin in this case.Maybe he can help.
 » 17 months ago, # |   +7 Nice and balanced problem set.
 » 17 months ago, # |   0 I just got a mail saying that my solution of problem D coincides with another contestant (Hemose) . The solutions are completely different except from the Scanner class that is used by most of German University in Cairo students because it is implemented by a senior in our community here is a link to the Scanner class https://github.com/AhmadElsagheer/Competitive-programming-library/blob/master/other_algorithms/Scanner.java. All my problems are "skipped" . Help!!!
 » 17 months ago, # |   +5 problem D had really bad pretest.
•  » » 17 months ago, # ^ |   0 I agree.
 » 17 months ago, # |   0 Problem C.Can anyone tell me why my solution gets TLE on test case 84. My solution is find all divisors of x and store in a vector. Then iterate all possible pair and pick which pair is minimum.Submission Link: https://codeforces.com/contest/1285/submission/68510565Thanks :)
•  » » 17 months ago, # ^ |   0 I also did the same and got TLE during system testing. I read somewhere that the upper bound on the number of divisors of a number is of the order n^1/3. So the total complexity of the solution will be O(n^2/3). Which according to the constraints will run till 10^8. Correct me if I am wrong.
 » 17 months ago, # |   0 Dear Sir/Ma'am,I have not committed any kind of plagiarism act in this contest.The question is very common and the same has already been taught to both of us in our Coding institutes named Coding Ninjas. We have done the same way as our mentor taught us. This may be the reason why our codes are matching. Please believe me I have dont been involved in such activity and will make sure that my code doesn't match with anyone. Please update my ratings as soon as possible instead of marking it as a System error.This is really unfair with me.All my submissions are marked as skipped.Please help. 1285B - Вкусные покупки
 » 17 months ago, # |   0 Dear Sir/Ma'am,I have not committed any kind of plagiarism act in this contest.This question is very common and the same has already been taught to both of us in our Coding institutes named Coding Ninjas. We have done the same way as our mentor taught us. This may be the reason why our codes are matching. Please believe me I have dont been involved in such activity and will make sure that my code doesn't match with anyone. Please update my ratings as soon as possible instead of marking it as a System error.This is really unfair with me. All my submissions are marked skipped.Please help.1285B - Вкусные покупки
 » 17 months ago, # |   0 Can somebody help me figure out the cause of runtime error in this 68552675. Here is the accepted solution 68560810.Only thing I changed is a line in comparator, I changed it from if(a & (1ll << bit)) return 1; to if((a & (1ll << bit)) && !((b & (1ll << bit)))) return 1;.I have already checked the two numbers for equality (and returned zero if they are equal). Is there anything else that is needed to be taken care of while using comparators? Can someone one point out my mistake?
 » 17 months ago, # |   0 Unable to understand div2 round613 editorial for question C for(int i = 0 ; i < (1 << n) ; i++){ ll a = 1, b = 1; for(int j = 0 ; j < n ; j++){ if((i >> j) & 1) a *= f[j]; else b *= f[j]; } if(max(a, b) < max(ansa, ansb)){ ansa = a; ansb = b; } }This part, what is it doing?
 » 17 months ago, # |   +5 please explain problem f classical
 » 17 months ago, # |   -9 After seeing today's solution div3 A's reaction will be like this->
 » 17 months ago, # |   0 Please help!! I got WA in test case 7 in Problem C. The testcase is 999999999989In my computer the output is 999999999989 1 But in judge output is 1 1 My submission 68590352
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 my submission in contest time also got WA for same problem 68547513
•  » » 17 months ago, # ^ |   0 Initialise mi with 3e18 or any greater value in your code.
•  » » » 17 months ago, # ^ |   0 is it problem with LONG_MAX ?