Hello Codeforces!
We are glad to invite you to Codeforces Round 613 (Div. 2), which will be held on 10.01.2020 17:05 (Московское время). 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, TripleM5da, 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
Cyan setters are all gone but it'll be good round.
I don't think I've ever seen a shorter contest announcement before
EDIT: Hope the statements are as short as the announcement
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.
Trying to make enough money to afford MIT. I see you. Only a few ten thousand dollars left np
as always hope for interesting and SHORT STATEMENT problems!
Waiting for XOR problems.
it's illegal
Osama_Alkhodairy's fan club members are so proud of you <3
I always like that type of question which has no story.
It will be a nice round
Arabic round :D
I will participate for sure
I look forward to more XOR questions from mohammedehab2002
Fantastic 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 ?
It's Ehab. Please correct. I still remember the Ehab and expected XOR problem. That was my best contest so far.
Thanks for the correction !
5 problems... I think it will be good contest
I predict that there will be a gap between problem C and problem D Let's see (:D
Egyptian!! I'm so proud ❤
An Egyptian round! :D I can't wait to see how good the problems will be tomorrow <3
Where the cyan gang at?
so proud of you guys , keep going <3 <3 i love Egypt
Egyptian contest Of course i will participate ❤️
Hope pretest passed => system test passed
*pretest passed >= system test passed
I really hope that was a joke
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.
Thanks for calling it out!
I'm in California too and I totally agree. The convenient thing is, at the very least, 6am contests are generally before school/work.
Nice Five
nice day, atcoder -> codeforces, two contests
Waiting for short problem !!!
What's the score for each problem?
Thanks for the sixth problem. You are the best
means the added problem can be solved in 15 minutes hope the problem added would be moderateUPD1:
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.
means the added problem can be solved in 15 minutes hope the problem added would be moderate
I am getting feels that many solutions will fail on system tests.
The problem statements are as short as the announcement was.
How to Solve D?
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.
Can you explain more in detail?
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.
I found that, but because many bits are connected, I couldn't reach the solution.
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.
What is the pretest 6 on problem D?
Pretest 2 of B?
It was just maximum subarray sum without including [1,n]
Yeah, i got that. But i don't know why my solution was failing.
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.
Try this:
NO?
How to solve E?
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?
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.
Honestly I had the same idea, but after atcoder got a bit too lazy to implement it...
What's the pretest 2 of question B?
In problem D 1285D - Dr. Evil Underscores
The 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
I tested this case:
5
10 13 16 20 26
and I found the answer is 20, which is not the power of 2.
Oh my idea turns out to be wrong Thanks for your help :)
NO, take $$$n=7 ,arr = $$$ $$$1,2,3,4,5,6,7$$$
Not true. Consider the input
Answer is 3
i have a feeling all my solutions will be wrong in system tests lol
Recursion.....uggggh
xorforceslcmforces, great contest, thanks!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 sum
task-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 :(
What was Pretest 5 for C? and is the answer for 999999999999: 999999 1000001
Try : 8
Its 2 4 ?
should be 1 and 8 since lcm of 2 and 4 is 4 instead of 8
It should be 1 8
LCM of $$$2$$$ and $$$4$$$ is four, not $$$8$$$
It's giving 1 8
Can you share your approach?
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)
Try: 49
Gotcha. It's giving 7 7
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.
How did you come up with this number?
Two same factors will make the that number as LCM which is not X which is the target.
How to solve D? Explain for me, plz
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.
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 SOLUTION
P.S. Don't forget to empty the array before starting pushing the array. I wasted 30 minutes to debug that mistake.
We have two choices for Every X so it seems that its 2^30 can you correct me?
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.
can you elaborate more how the complexity is n*lg(n) ?I think it should be n^2 according to your explanation
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).
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<<bitPos) + min(leftChildAns, rightChildAns).
Also for time complexity analysis, the solution can be implemented with a simple DFS. Maximum possible nodes in the trie : 10^5 * 30.
implementation : https://codeforces.com/contest/1285/submission/68543045 (I hope it passes the systest xD).
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<<pos) + min(solve(l, f, pos-1), solve(f+1, r, pos-1)). Link to code
Thank you for quality problems. Had fun
F. Classical?
Yes.
I just copy-pasted code from a problem I solved yesterday :Dd
(Simpler solutions exist for sure though)
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.
How to solve F?
This is much similar to F see this
No it is not.
Is Trie without DP enough to pass D?
Memoization is not needed here.
You didn't even try to answer his question
Yes
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..
Dude, nobody was asking for c solution, why did you put it here?
Because it is related to the competition anyway, and there is no matter.
explain F
Dude, nobody was asking for your opinion, why did you put it here?
its recursion. Dude, nobody was asking your opinion, why did you put it here?
how you are sure that this will give right answer.. can u explain it more
Hello, mango_lassi. Your solution for B is so simple. Can you care to explain?
Thank you :)
https://codeforces.com/contest/1285/submission/68502173
Solution for B:
Yasser's Score = sum of Ai's
Adel'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")
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.
Calculate prefix and suffix sum of array
if 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"
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.
When would the system testing start?
it's too late to start system test........
https://codeforces.com/contest/1285/submission/68549930 can anybody explain why is this giving wrong answer?
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 thanINT_MAX
, the correctmin
will greater thanINT_MAX
.For example: If $$$X=10000600009=100003^2$$$ ($$$100003$$$ is a prime number), your solution outputs
4 2147483647
, correct answer is10000600009 1
.thank you so much. so basically i missed out on 1100 points because of that
The contest was great. But I'm anxious for system test and it's too late.
More like: good number in base 10
Anyone feels that C was easier than B
Yup, C was indeed easier than B
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
I solve C without much thinking and even though i know B need kadane's algo still i couldn't solve
see my solution for B,I just took care of the condition which requires not to select whole array as subarray. here
Good D problem.
TripleM5da Tell me the truth. You started the system test late to add the case that breaks my problem F. :P
You'd think so but surprisingly me and mohammedehab2002 were able to handle most heuristics almost right before the contest.
TripleM5da Try to break this one: 68691230
Can someone give me a hint for problem F?
Just saw a WA on 159! Time to leave earth!
Can anyone hack https://codeforces.com/contest/1285/submission/68545833 ?
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
take [20 30 -10 50 60] 20+30-10+50+60 = 10+5-12+7-10+20+30-10+50+60
After several tries on F, passed in the last second!!! ...
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 ?
Quite strange.The TLE code shown is accepted. I think, you must tag admin in this case.Maybe he can help.
Nice and balanced problem set.
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!!!
problem D had really bad pretest.
I agree.
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 - Вкусные покупки
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 - Вкусные покупки
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;
toif((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?
please explain problem f classical
After seeing today's solution div3 A's reaction will be like this->
Please help!! I got WA in test case 7 in Problem C. The testcase is
999999999989
In my computer the output is 999999999989 1
But in judge output is 1 1
My submission 68590352
my submission in contest time also got WA for same problem 68547513
Initialise mi with 3e18 or any greater value in your code.
is it problem with LONG_MAX ?