Hi all!

This weekend, at Sep/23/2018 16:05 (Moscow time) we will hold Codeforces Round 512. It is based on problems of Technocup 2019 Elimination Round 1 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2019 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The Elimination Round authors are Ajosteen, BledDest and adedalic. Thanks to FCB1234 who authored the last problem for div. 1 round and arsijo for his help in coordination. This round would also be not possible without the help of our testers: winger, Um_nik, AlexFetisov, Denisson, thank you so much!

Have fun!

Div. 2 and the Elimination Round will feature 7 problems, preliminary costs are

250 — 500 — 750 — 1500 — 2000 — 2500 — 3000.

Div. 1 will feature 5 problems, preliminary costs are 500 — 1000 — 1500 — 2000 — 2500.

The round is over, congratulations to the winners!

Technocup 2019 - Elimination Round 1

Codeforces Round #512 (Div. 1, based on Technocup 2019 Elimination Round 1)

Codeforces Round #512 (Div. 2, based on Technocup 2019 Elimination Round 1)

The analysis is published.

Clashes with open cup. Please delay the contest.

I have more downvotes than upvotes of this blog

Unfortunately we can't postpone the round, because it is an Elimination Round for Technocup and was scheduled long before.

y u do dis :'( please come up with a solution... both contests are so interesting...

You can delay only div1 + div2 rounds. Students can't participate in main round.

I don't want delay.

It's clashing with AtCoder Beginner Contest 110 too. :(

Just do both lmao.

Just before September CookOff On CodeChef — Two Consecutive Contests + SundayYou didn't mention anything about the number of problems. Can you edit that please? Edited, thanks

Round 2^9 :D

First power of two round since 2014!

Next in 2026!

Cf community is a very strange.

There are gonna be statements in English for the Div.1 and Div.2 editions, right?

yes

A bad time for Chinese students.

Better than contests that started at 11:35p.m.

But most high school students can't use computers between 10 and 10:30. So I think it is better to race earlier or later.

But I don't think so. Codeforces is not only for high students.

May I ask why high school students there can't use computers between 10 and 10:30? Just curious.

Because most Chinese high school students will leave school at 10 pm, they need to go home to continue the competition.

But I can register the competition because we have a holiday for Mid-Autumn Festival.

Umm so you have to go to school on weekends...?

Can't they use computers at home?

Yes.Sometimes.

It is mid-autumn and you are at school?

This world needs one more cp platform for Сhinese, Japanese, Vietnamese and Australians.

btw MikeMirzayanov can earn a lot of money by trading his cf system and installing it with Full Construction for anyone who could pay him some amount of money, so that person could hold contests there and get donations.

Another good time for Chinese Oier to enjoy the contest!

But ...... many of HE->OIers doesn't have a holiday in Middle Autumn Festival...

Still not so bad..(at least much better than 11:35 for oiers..) (why don't you use self-studying in the evening?:D

May I ask how many problems are shared between divisions?

It's three in the previous contest.

i think three

hi numb

I think (div.1 A=div.2 C) ,(div.1 B=div.2 D) ... (div.1 E=div.2 G)

That's rather unlikely.

If div1 is a subset of div2, then div2 would have to solve 2 extra problems than div1 while having the same time amount.

My guess is div1 starts with div2D. Div1 version of this round wasn't there before, so I think a problem was added at some point.

Aren't 250 points for the first problem too less ?

Wait for question to pop up.

The question will have 2500+ submissions within 6-7 minutes, then :P

Personally speaking, I will prefer to solve this question at last.

I'm pretty sure that the optimal strategy is to always solve problems in increasing order of the time it takes to solve that problem. For example, if it takes you 1 minute to solve A and 3 minutes to solve B, if you solve A first you'll get 249+492=741 points, but if you solve B first you'll get 246+494=740 points.

I would love to follow this stratergy but after getting soln. It takes me 5 min to code and test (due to my slow typing speed.) So I prefer reading all questions before starting.

I agree with reading all problems before starting because there are many times where I get stuck on a problem believing "the ones after are harder" while I could've solve problem D way faster than problem C (or some other combinations). I failed a contest for not reading all the problems at the start before :(

Not exactly. I think it's more of decreasing order of . For example, if it takes you 2 minutes to solve A and 3 minutes to solve B. Solving A then B gives you 750 - 2 - 10 = 750 - 12 = 738 points while solving B then A gives you 750 - 5 - 6 = 750 - 11 = 739 points.

Yeah, i calculated something wrong. I'll check with a bunch of random inputs if your theory is correct.

EDIT: It works on 500 million random contests with 4 problems each and 43 million random contests with 6 problems each. I think you're right.(I made each problem worth 250*(random number between 0 and 3) more points than the one before it and made the time required to solve a problem a random number between 1 and (problem number)*10.)

Good job showing that you're a good scientist.

thumbs upI think you should also try to prove it with a contest of 2 problems. You'll have a better understanding of why that's the case.

This is going to be my first contest ever. Wish me luck, guys. :)

You are such a liar!!

`Thanks to Mike Mirzayanov for the platform...`

Don't be angry with downvotes, you don't want Mike to see that. Codeforces community tryin to help you by hiding this comment

Wish you all get failed system... Ok, that's a joke. Wish you all get high rating!

What will be the duration of the contest, <= 3 hours right? Otherwise it clashes with September Mega-Cookoff on CodeChef.If you go to the contests sections, you can see the duration of every contest (it's 2 hours btw!)

"Mega-Cookoff"

round 1000000000

dont try to hack my solution .. warna kanpatti sek dunga.

I prefer a hack rather than system failure. Since it gives me a chance to correct myself. I always pray that if my solution lacks something, then its better that it gets hacked.

nice thoughts /.. but still dont try to hack mine .. else u will get fucked.

no u

I will hack you

upvote if u want to get upvotes.

who will give me the first upvote?

Um... Nobody?

Geometry forces

today was a bad day , my mind completely shut off on B :( can anyone explain once the contest is over ?

same here

Mine did too when I first read it so I was like "you know what? Convex hull!" lol

I got the convex hull out of the 4 points they gave us on the input and then, for each point, I tried to add it to the convex hull. If this point is in the new convex hull, that means this point isn't originally inside the polygon given (or it wouldn't be in the convex hull).

I mean, I know there's probably a much easier solution, but that's what I came up with in a few minutes xD

I was also inspired by the convex hull algorithm. I walked from anti-clockwise around the corners of the rectangle. Then for a given point I checked if the cross product of the vector from one corner to the next and the vector from one corner to the point was non-negative. If this is true for all corners the point is inside the rectangle.

Div2 B Write equation of each line then divide rwctangle based on x coordinates and check if y lies below or above the line segments. Also do the case when n-d<d.

Each line on the rectangle can be written as y = x + c or y = -x + c. Finding c for all 4 lines is trivial, as well as <= or >=. For every coordinate see if the inequality is true for all 4 equations.

Look at the picture:

These red lines are covering all of the points of the rectangle.

Now focus on the topmost red line. What is common for all the points that lie on that line?

All of the points on the top line can be descibed by this equality:

y-x= 2.By the way, in general I know only about 4 equations which are useful in these types of problems:

Horizontal line

Vertical line:

Diagonal line from top left to bottom right

Diagonal line from bottom left to top right

Diagonal lines are more difficult of course =)

I need to constantly remind myself that I can add and subtract coordinates and get something meaningful out of it :)

Since the coordinates are small , iterate through all the coordinates which lies on or inside the rectangle and mark them as 1. Now if the point lies outside the rectangle then the value of that point would be 0.

if i'am submit two time accepted to same problems, why i'am take point to the last submit?????

So why you submit it twice if you get ac

I'm don't know that, I'm doubt about case, It's stupid one for me

is pretest passing ac ?

yes, passing the pretest

What is test 5 of B div 1 :(. Failed on it 3 times and can't find the mistake.

I used the int version of popcount... wasted over 1 hour and 5 submissions

DAMNNN ITTTTTTT THAT WAS MY MISTAKE TOO

Could've been something like

Nope, it's that I USED THE INT VERSION OF POPCOUNT

I was trying to solve E wth I smoked today

What is pretest 4 of Div. 1 D? T_T

something like

6

17 17 73 73 163 163

answer should be 262158769.

Thanks this hacks my code.

Can anyone explain Div1-B? I thought that for (l,r) to be good sum(l,r) has to be even and >= max element of (l,r). I couldn't do anything with this fact though. How can I approach this kind of counting problems?

My approach -

Considering the count of 1 bits as elements in the array.

Sufficient condition -

good sum(l,r) has to be even and sum(l,r)/2 >= max element of (l,r). And log2(1e18)<63.

Then iterate until sum(l,r)<=126.

Rest of r with even sum is good. At max 126 iterations.

Time Complexity — O(126*n).

Upd — 128 is loose upperbound. 64 is enough.

I don't understand why you have taken 63, isn't 60 good enough? I used 60 and got the wrong answer on pretest 8 for whole contest

Only statement on this case.

"Take a loose upper bound. But it should not be large enough so to give TLE."

I will try to explain my approach, though I failed on test 5 for unknown reasons: - For a certain r, you will store all "records" from right to left, which are new maximum numbers. You can see there are at most 60 values of this. Then you can simply binary search in this range for the rightmost index x that sum(x, i) >= 2 * bits. Then prefix sum in this range is easy.

i failed on test 5 too and it turned out i was taking input as integers instead of long long (i was thinking the number of bits will fit into int)

I failed on test 5 BECAUSE I USED __BUILTIN_POPCOUNT() INSTEAD OF LL. Gah screw me

oof

At least you got accepted man, I'm gonna go down to expert and then work my way back up now.

As you said, you have to have:

This is easy to prove, since your basic operation is decrementing one from two numbers in the interval (meaning that some of their bits cancel each other out).

But we notice that max(l, r) <= 64, and the value of every element is at least one, so you can:

code: 43313078

You will have to brute force until 128.

Well not really since max(l,r) is also counted in sum(l,r) so even if the other elements in the range are 1s your sum will exceed 2*max(l,r) after 65 elements or so.

Got it.

I took loose upper bound.

I will pray that I don't get TLE and pretest cases are strong enough.

You don't, since , so it's enough that the interval is longer than 64, since then .

Thank you all very much!

can you help understand this plz .. we are calculating for each number how many 1 in the binary representation right ? but why does it matter that the sum of 1 is even

if we have 15 and 6 the sum of 1 is 6 which is even but xor isn't 0

Cases where there are only two elements have one extra condition: Number of ones in

a_{l}== Number of ones ina_{r}doesnt that mean max element should equal or be less than half of sum of (1)

I don't understand what you mean by that.

if we have a number that has 8 ones in its binary representation and other 7 numbers that has only one one (lol one one) isnt that the same issue of the two numbers

If I understand correctly what you are asking, this array will not be good, as the number with 8 ones can't have 0 ones even after xoring with all the other numbers. The condition that the numbers should be equal only applies where the subarray you're checking has 2 elements only.

what is the solution for Div2 D ?

Geometry forces. WTF?

A — too much troll problem. If a person couldnt solve problem A, what's he doing here? Why add such tasks in the competition?

Easy task was there so that more and more people will have to compete because they have already solved problem A.

He didn't solve A, but he solved B, C, D :)) rarai

LOL

B solution https://www.geeksforgeeks.org/check-whether-given-point-lies-inside-rectangle-not/

That's overkill.

Just pointing out the solution being copyable

I think this is my worst performance ever, fell ashamed about this stupid bugs I had :(

At least you failed while being in div1, something i can't say about me.

Happened to me too :(

What is wrong with the following solution for div1D?

For each prime I can choose element of order

por orderp- 1. Sort all primes and consider them from biggest to smallest if:pis more than once than choose elements of orderpand orderp- 1pis only once and our current answer is not divisible than p, than take element of orderppis only once and our current answer is divisble by p than take element of orderp- 1.I think you can set

x_{i}= 1,a_{i}= 0,b_{i}= 0, which essentially provides you with a unique first generator state. I think the result for (p_{i}) = (5, 3, 3, 3) is 31.Got it. Thanks.

I passed this test but still got WA on pretest 4 though. Do you have any other tricky tests?

Perhaps (

p_{i}) = (2, 2), giving 3 in result?I got that case correct too :\

UPD : Someone posted a testcase above that hacked my code

http://codeforces.com/blog/entry/61992?#comment-460279

Is Div1D just making copies of

pintopandp- 1 and taking LCM of everything, or is that wrong?Codeforces? More like Mathforces.

Thanks codeforces for wasted an hour of mine for not specifying that "the segments should span the whole sequence" in Problem C

"Note that each digit of sequence should belong to exactly one segment."( T T ) . maybe the worst round I have ever had

hi how does one do problem D from Div 2? i was thinking along the lines of the shoelace method but didnt really manage to get far with that idea.

AFAIK let it's height be h, and base length be b, now 1/2*b*h = n*m/k , so if 2*n*m%k != 0, then print "NO"

else note than you can always get one value of b less than n and one value of h less than m just by dividing gcd's and simple manipulatins

Why b * h is an integer ?

since area of the triangle in coordinate form is

1/2*sum(x1*(y2-y3)) = 1/2*b*h

and the left side (after removing 2's) is indeed an integer

If you have a triangle with points A, B, C; its area can be computed using cross product as 0.5*abs(AB X AC), where AB and AC are vectors going from A to B and C respectively. Since the points have integer coordinates, then b*h in 0.5*(b*h) must be integer.

You can construct the triangle using the points (0,0), (a,0) and (0,b) for some values of a and b. The first thing to check is when you simplify the fraction by diving by gcds if the denominator is greater than 2 there is no solution. You can see this because of the shoelace method you mentioned. The key to finding a and b is when you divide by gcds first divide n and k by gcd(n,k) then take this new value of k and divide m and k by gcd(m,k). Then if in the end if your k is 2 your new values of n and m will work for a and b. If the new k is 1 you have to multiply one of these results by 2.

How to solve div2E (div1B) ?

What is wrong with this solution for Div2 D 43333417

we aren't not allowed to see other's submissions until system pending is done.

But maybe you're missing the case when n*m isn't divisble by k, but 2*n*m is .

Oops, didn't know about that.

I checked for that case. My code got WA on pretest 10. Thanks for your response

Does anyone have any idea what pretest 8 for Div 2E is?

is cf predictor broken? I know I'm not that good in div1 but I feel like being in the 2/3 place should not be a rating drop for barely above 1900 (I noticed people around me also had rating drops despite being like 1910)

I feel like recently it's broken. 1 contest it predicted me having +112 when in reality, it's a mere +55. The second time not as broken, still, +102 turns into a +124.

how to change the username which is shown to others?

you must wait until the new year

really?

Yes. This is kind of a Codeforces tradition — you have 10 first days every new year to have

onechance to change your username.(i.e. this option will be available in 10 first days only, and you can use it only once per year)

Ok,thanks

WTF??!! 2 GEOM TASKS?? OMG F****G GEOMFORCES

can i get the test cases of div-2 B??

I can't approach div1C by anything. Can somebody help me ?

If you move boxes i ... i + k to positions x + i ... x + i + k, it costs:

We want to choose the

xthat minimizes this. Note that the function is convex. We also have:Where

comp(x,y) = 1 ifx≤y, and - 1 otherwise.Since the function is convex, therefore the difference is increasing, and

cost(x+ 1,i,k) -cost(x,i,k) only changes whenx= (a_{j}-j) for somej, we can just binary search the indexjwhere whenx= (a_{j}-j), the change first turns positive. This is the minimum ofcost(x,i,k). Then, we just need to calculatecost(a_{j}-j,i,k).To do both, we store in a segment tree two values. For an interval [

x,y] in the tree, we store:On the left side of

j, the absolute value does nothing, and on its right side, it multiplies by - 1. Therefore, we can easily calculate the cost.My solution is O(n log(n)^2), but a O(n log(n)) solution can be easily achieved by doing the binary search inside the segment tree.

Code: 43339602

I have been wrongly plargarised!! I have used following reference.

https://www.geeksforgeeks.org/check-whether-given-point-lies-inside-rectangle-not/ The problem is trivial. Please, consider my rating. Attention!

Your solution 43312547 for the problem 1058B significantly coincides with solutions saketag007/43299916, gsoc18/43312547. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

I have been wrongly plargarised1!! I have used following reference.

https://www.geeksforgeeks.org/check-whether-given-point-lies-inside-rectangle-not/ The problem is trivial. Please, consider my rating. Attention!

Your solution 43312547 for the problem 1058B significantly coincides with solutions saketag007/43299916, gsoc18/43312547. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.

Thank you for the round, I really like the problems! Although I have no idea about Div.2 DEF, but thank you for the round!

Hi, This is regarding solution 43335491 for the problem 1058D - Вася и треугольник , I have solved this question on my own ......I also matched my solution with 43330317 yes we have same variables declared due to which this misunderstanding took place and I m wrongly penalised....but as you can see there is a lot difference in my templates and him....which I always use. This is just a coincindence and I am Innocent. Kindly consider my submission. Thank you.

Even with the different templates the main code is the same and that's definitive proof it's plagiarism

I noticed that my solution to the problem B was similar to someone.I just took the idea from here https://www.geeksforgeeks.org/check-whether-given-point-lies-inside-rectangle-not/, didn't copy the code exactly . Please rejudge my solution ...

Submission 43333246

What those weird loops are for? Cheat detection evasion? The user did that regularly on their submissions.

I think it is

I do hope actions will be taken against them, if they are indeed cheating

My code is giving correct answer on local compiler but giving false answer on codeforces compiler. My whole contest went bad due to this error. Atleast my rating should be reverted back. 43309972

I checked test case 10 on codeblocks compiler as well as codechef IDE. Both of them are giving output as "Yes". My code is completely correct but still got WA.

"Atleast my rating should be reverted back" "My code is completely correct"

Stop with the trash attitude, you made a mistake, just own it.

Here, i modified your code and it got accepted: https://codeforces.com/contest/1058/submission/43347029

You had undefined behavior when accessing prefix_sum[pos] when pos = -1, so the output is never guaranteed to be the same.

I didn't know there was undefined beahviour because as I said online compilers as well as codeblocks was giving me the correct answer, that's why I though my code was correct.

If my code was wrong which you very correctly pointed out that it is, I wouldn't have written this comment. Thanks for your help.

I've solved div1 A

And I have a question, can anyone help me?

My solution of div1A used a valuable called "y1" , but I forgot to "define y1 _____y1".

And I passed the samples, pretests and main tests.

Why?

Here is a link of my solution :

![](http://codeforces.com/contest/1053/submission/43301181)

UPD: My question has already been solved.

I solved Div1C at 01:59:36, but Codeforces was down at that time... This is my first time to solve Div1C during a contest... QAQ

When there will be a list of those who have passed to the final?

Div.1 and Div.2 top 1 are both Chinese! They are sooo good at math (and coding)!