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 pikmike for coordinating the round, dorijanlendvaj, aryanc403, Ari, ZeroAmbition, 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.

I hope so! And the tasks will be easier than others in early contests

Trying to make enough money to afford MIT. I see you. Only a few ten thousand dollars left np

[hashtag]deferredgang

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

It would be more difficult to solve...

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 ❤️

Good Luck for All Egyptians :)

Hope to become newbie after this round.

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

Very nice First Arabic round for Me

Expected suitable problems .

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.

could you elaborate ?

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.

when sum get's equal i subtracted min(ar[0],ar[n-1]) from maximum subarray sum

Try this:

NO?

3 0 0 100

answer will be no, right??

yes

my code was working even for this case

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?

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/68528340

Note: this is pending system tests, might still be wrong

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

~~xorforces~~lcmforces, 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 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 :(for problem B wouldn't your sol is O(n^2)

No its O(n). Search for

Kadanes algorithm for maximum subarray sum. :)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 ?

No i calculate once for a[0 ... n-1] and once for a[1 ... n]

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

Oh no! Made a blunder.

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.

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.

Hey, my number theory is weak, Can you suggest me some good resources?

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.

it felt that this was the easiest Div2 contest I have ever participate but still... :')

wait till you get a surprise WA in sys tests lol, i know i will

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?

Why did you reply him, dude? Nobody was adking for 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 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`

.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.

Wow，8000 passed pretest, good number

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

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

Good D problem.

DeadPillow 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

mostheuristicsalmostright before the contest.DeadPillow 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!

I saw 163.. add me too...

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

Never use INT_MAX as infinity....today i realised it is smaller than 10^12

After several tries on F, passed in the last second!!! ...

System test: What? What did you say?

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 ?

MikeMirzayanov

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.

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/68510565

Thanks :)

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.

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 - Just Eat It!

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 - Just Eat It!

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?

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?

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

999999999989In my computer the output is

999999999989 1But in judge output is

1 1My 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?