**عيد سعيد(Happy Eid), Codeforces!**

I'm glad to invite you to Codeforces Round #788 (Div. 2), which will be held on 06.05.2022 17:35 (Московское время).

This round is rated for the participants with rating lower than 2100.

You will be given **6 problems** and **2 hours** to solve them. All problems were prepared by me, Hemose and ZerooCool.

I would like to thank:

Monogon, for a lot of things (awesome coordination, helping in preparation, rejecting only not interesting tasks and a lot of useful discussions).

I_Love_Slim for teaching us

~~BLABIZO~~useful concepts.Our army of testers YahiaSherif, DeadlyPillow, TheScrasse, Bakry, IsaacMoris, TeaTime, magnus.hegdahl, generic_placeholder_name, NemanjaSo2005, Abdelrahman_Etman, TheSawan, gojira, Priyam2k, Urvuk3, Menna-Allah05, Khater.

MikeMirzayanov, for the amazing Codeforces and Polygon platforms.

The statements are short and we have tried to make the pretests strong. I encourage you to read all the problems.

For people who don't like stories, you will find all the stories written in italic you can skip them safely.

We are sincerely looking forward to your participation. We hope everyone will enjoy it.

Good luck and see you in the standings!

**UPD: The score distribution is 500-1000-1750-2250-2750-3000.**

**UPD: We hope you liked the problems, here is the Editorial**

GUC gang!

Eid mubarak everyone.

GUC orzAs a tester, I'd like to say that no java coders were hurt in the making of this contest.

As a tester, I will give you hints to the problems

So happy to see you here our coach . you are a source of pride

Why is there > 100 upvote on a rick roll link?

As a participant, I'll give you solutions to all the hints

I deleted youtube!

These hints are very useful, thank you

Why there is a Huge jump from B to C ?

As a possible contestant if time permits, I would like to present my sincerest congratulations and best wishes to the GUC team for the kind endeavors.

Heartbeat

This is the first Egyptian round after a long time! Our congratulations!

The pharaohs are back

Eid ul Fitr Mubarak to you and your family.Score distribution? (:

As a GUCian, I'd like to say that those people are wonderful. Hope it will be a nice contest!

EID Mubarak

Eid Mubarak

distribution?

Egyptian round? Long time no see)

Hemose is back yayy! :D

congratulations Bakry qualifying to ioi

https://www.facebook.com/eoi.eg/photos/a.288097731292115/4626081414160370/

Thanks :D

Looking forward to participate! Eid Mubarak

Coders(>1600 rated) : Finally we can participate ;-;

.

As a GUCIAN tester, I am proud of you and your great round.)

Pharaohs' Contest is back OwO

Excited about this round

"You cannot vote twice. You have already voted for this topic before."x10

We're so proud of u guys. Keep going and make us proud in ICPC too , ISA

GUC on fire

Maybe Egyptian round is full of Bitwise and Math problem

hahaha:)It's my first time to participate the div 2 contest unofficially.

EID Mubarak

Never give any contest for increasing your rating. Just give it to learn something new, and rating will definitely increase sometime.

GUC on The TOP of STANDINGS <3

thank you problems author

As this is an egyptian round, being the egyptian king I must perform great in this round. Hoping for good fat +ve delta.

how did u get out of the sarcophagus?

3id s3id!

i hope be pupil in this round

why you practice so many problems，but still newbi？

Because in a long period in my training I was solving easy problems and I did not benefit from them, and another reason was that I had to solve problems from training beginners in order to help them solve them because I am mentor

wow, I really hope you could be more and more exctllent! As for me, I just learn algorithm for three months, ans I hope I can be a master one day! Best wishes for you!

thanks

how cool man

will try to solve atleast 3 questions today.

Eid Mubarak(⦁ᴗ⦁)

As an Arab contestant, I am always glad to see Egyptian rounds on CodeForces. Well done GUC, keep it up guys!

Good luck everyone

"For people who don't like stories, you will find all the stories written in italic you can skip them safely." — Whoa cool!

Good luck everyone!

Wish you all a great rating gain.

Eid Mubarak to everyoneEID MUBARAK & GOOD LUCK !!

Eid mubarak everyone.

All the best!! :)

MemeI enjoy problem E but I hate problem D!

n lines would make these many triangles = 2 * (n)^2 / 3

what is the the proof?

I did it like this :- we can have 3 directions for lines to draw ,each time we draw a line in one direction then it intersects all the lines in other two direction and thus creates 2*X more equilateral triangle where X is the total number of lines in other two directions.

Does GNU C++17 7.3.0 allow __int128? I met this compilation error:

I think it need 64bit compiler

GNU G++20 11.2.0 (64 bit, winlibs)is fineDang, I think I was really close to solving E for the first time. It's a pity I now have to wait for system test to end in order to test my solution :(

Points of C should be 1500

Problem C was a modification of 1534C - Little Alawn's Puzzle

yes that problem came to my mind too when I saw problem C.Btw your pfp is cute

true ^_^

I just don't know why D had so tight constraints and the fact that I used some random optimization was able to pass the pretest is insane.

because it's one time sqrt(N) initialization.

I've solved it with binary search, without any initialization (preprocessing). You can see my code 156115088.

why don't you consider the points where three lines intersect and will create 6 equilateral triangles in a hexagon?

In E we can choose any vertex to be root, right? And max xor will always be n, where n is number of vertices?

Yes

Yes. I think you mean E?

yes, E, my bad :)

I really enjoyed this round, thx to everyone who participated to make this contest! :)

Pretest 4 in problem B is a mystery for myself :)

Me too, but I made some changes i thought it will not do anything, i passed :)

Was F digit dp?

yup, slightly modified tho

In my opinion, I think problem D is more like a math puzzle than a cp problem.

In programming contest ICPC style are many full math problems, with many theorems, it's a good way to train for it. However, I think it's more an Ad Hoc problem than a full math problem. And you need binary search too

No idea with Problem E & F after solving A~D in ~1h :(

E is also a math puzzle, like D :)

I solved a similar problem which asked how many area can be divided by $$$n$$$ lines in a infinite plane before. So I came up with that idea for D immediately. But no clue for E hh, maybe need more practice.

We can't avoid the Nth bit appear in the final cost. So the answer of maximum cost is

`1 << N`

. assign this number to root node. Then for any other node`x`

, if its depth is even (depth of root is 0), assign`x`

and`x | (1 << N)`

to it and the path linking it to its parent node, otherwise assign`x | (1 << N)`

and`x`

.that logic is so clear..! I didn't even figure out the root can be fixed as 1 << N.. thanks for given clue..!

I have only a few words to say about this: damn it i cant attach pictures

link

Although E and F were very nice

Q4 is Guessforces

A simple testcase could hack my solution of B, and I was so anxious that my analysis of the time complexity is wrong :(

looks you got TLE.

So am I...

my python code for Q4 was giving TLE but it was only O(1). Can someone tell me what’s the problem?

Damn you commented with the wrong account

Thanks for the strong pretests!!

Yeah very strong pretests : https://codeforces.com/contest/1670/submission/156081443

Glad that you provided so many samples in the questions...

Seriously bro? Look at question (Edit: C), I took wrong modulo and got wrong answer on Test 2 and was going to leave contest. In such problems, it better to give atleast 1 case where number is larger than the modulo

I suppose you meant problem C?

I didn't like the contest to be honest, and Here's my opinion:

A is a normal problem.

B is a bad problem and it has many details as a "B" problem.

C is a bit standard problem (but with checking some cases), I think it's an okay problem but its score should be like 1250 or at most 1500, not 1750

D seems a non-sense problem to me and it was guessable, I think since E-F aren't that hard, D should be a harder problem and not guessable to balance the round.

E has many details but it's a normal problem and I think its score should have been less than 2750.

I think F is easy for "F" and its score should have been less than 3000. I think it is a bit standard problem too.

what is the trick behind D, it got decent submissions! I couldn't find any pattern.

Every new line creates two triangles with each existing line.

just a clean drawing on a paper can help me lead to the solution?

There are three types of line depending on the orientation of the line, so let the number of each be x, y, z. The total number of triangles created by those lines is equal to $$$2(xy + yz + zx)$$$ which has to be greater or equal to n. To minimize the sum x + y + z, the difference between x, y, z has to be minimized (I think you can prove it via fixing one of the values), so the triplet should be in a form of (x, x, x), (x, x, x-1), or (x, x-1, x-1). Hope this makes sense

sum i.e (a + b + c) would yield maximum value only when their absolute difference is minimum right i.e just do (a + b + c)/3 and distribute the remainders among them!

But how I would reach the conclusion that our total number of triangles is 2(a*b + b*c + c*a)? Can you give me some thinking approach?

Consider the intersections of these three types of lines. It is easy to see that if two lines are of different types, they will intersect as they are not parallel, and also each intersection of two lines creates two triangles. Now you might wonder what would happen if three lines intersect at the same hexagon. You can consider it as three separate intersections that each contribute two triangles, making in total 6 triangles, so we can count the number triangles as two times the number of pairs of lines that are from different types, thus, $$$2(xy + yz + zx)$$$.

Man you are awesome. Loved the approach!

Well I used the given image and Paint. That works too.

If you think "A problem has too many details", then you may solve it in a wrong way.

I said "B" has many details not "A".

I said "One" not "The first".

Oh Okay, I meant details in the statement not in the solution.

My opinion is "B" and "A" problems should have little details in the statement and be simple. For example the easy problems in "ARC" has difficulty like div2A,B but they're simple in their statement.

He has a point. The statement is way too long and can be simplifed. The entire part about special characters is useless and can be replaced by giving input as a binary string instead.

Probably shorter way to write the statementYou are given a binary string $$$s$$$ of length $$$n$$$.

In one operation you will perform the following:

How many distinct binary strings can be made by performing the operation some times?

E surely doesn't have much details.

It has details in the statement, I mean many things got mixed together and then we have this problem.

For example, nodes have weight and edges also have weights, A path can start at a node and ends at an edge and also it can end at a node.

I'm not against that type of problems but I just like the problems to be more natural.

+1 to every point

Is the technique used for solving F pretty well known? I couldn't get the part where they are generating bits and maintaining a difference as they go over each bit position. Can someone explain what they (almost all solvers?) are trying to do?

Mr_Solution If C is a bit standard problem, Where can I find/practice those types of problems?

They should have kept round 786 on Eid ;)

What an amazing Round Thank you to all the Problem Setters and Testers

Your account seems suspicious. How you were only solving one to two problems in Div2 and in matter of days you are solving 5 problems today. You should be reported.

Does that make any sense ? I solved all on my own or is it a preassumption a newbie cannot do problems beyond Div2 A.

Ohkk so what happened in last Div3 and Div2 rounds

Ran out of brain if that is what makes you feel better

Ran out of brain in 5 consecutive contests. Common that doesn't happen to anyone, just accept it.

@Mike will decide who is and who is not

Obviously You are a cheater buddy

sus

Ok let me tell you something. If you can't solve more than 3 problems on Div3, how tf do you expect us to believe you solved today dive2 D,E. They are like 1800+ rating problems. Only a newbie(like you described yourself) would not know how unlikely this is.

People like you are what ruining Codeforces. Keep this up, and Indians will have cheating reputation and no one would believe us. I already start hearing complain about Indians mass cheating during interview and programming contest. This would make it much harder to get jobs in India or in the US(I'm sure people wouldn't tell this to our face, but we will face more scrutiny)

I'd imagine IITers know better, but apparently it seems like it'd make it even easier for you to cheat since you could pass around solutions among your peers.

Your expectations are none of my business but you have no right to accuse me without proof . You have around 250 subs for E tell me one which matches with my submission

cheaters stink

"Some people are mad because you're not suffering the way they expected you to do"So how can you AC E even faster than you AC C ? It is nonsense

Hey if someone is doing nonsense things it is you First of all in C I forgot to add if child == parent then continue which meant infinite loop and my VS code where my code hanged afterwards so i had to restart wasted around 10-15 minutes there , then i got WA answer so i decided to go for a slight different approach although i preserved the original components Btw a almost 80% similar problem appeared in one of LATOKEN rounds last year so it isn’t a completely new problem E problem is fairly simple if one you assign 2^p to root node it isn’t that hard and a standard problem Btw who you are to talk about me when you yourself in your life only gave 1 contest

Solved 4 again . What would you say now ?

Get lost and hope someone taught in your childhood that bullying is bad

Hope you never go through this experience again

very true , some strict step must be taken against such cheaters otherwise they will make honest ppl suffer .

In problem D, I figure out that drawing lines gives you {+0, +2, +4, +4, +6, +8, +8, +10, +12, +12, +14, ...} more equilateral triangles. With this pattern, it is easy to binary search the minimum number of lines needed to make at least n equilateral triangles.

ohh noice ! i have a differnt approach for D!! as we can see there are only 3 differnt slopes of the lines possible and any two lines with different slopes will intersect for sure hence every two lines with different slopes will intersect and will give rise to 2 equilateral triangles ,now its not dificult to see that if i have x lines then i should make lines with differnt slopes in such a way that differnce between there fequency is as small as possible to maximize the intersections and thus triangles ... with this i moved forward , precomputed all the required values and then its just lower_bound!

oeis may help you

Weak Pretests in Question BGot TLE on TC29 in system testing. What a waste!!

my python code for Q4 was giving TLE but it was only O(1). Can someone tell me what’s the problem?

Slow input/output, Trying using a fast i/o template.

156110044 is it anti-anti-cheat approach? :D

A wise man, xQc once said "Cheeto"

Earlier I noticed just how many people got TLE on problem B at test 29.

Turns out that test 29 was actually my test...

Sorry guys :(

s.. sir...what is the logic for problem A ?

Move all the negative sign to the left

Okay got it thanks

Just realized that I got WA in problem C cause i forgot to mod the answer by 10^9+7 :')

What is wrong with problem B in the second testcase? I am not able to read the input.

To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!

https://codeforces.com/contest/1670/submission/156220559 This is submission link of my code for B problem . Why i am Getting TLE in this solution? Can anyone tell me.

You should use fast I/O code to get input\output faster.. put the fast I/O lines in your main function before getting any input.

Example :Thanks It works learned New Concept!!!!!!

I'm curious what is the rejected problem is. Maybe revealing it after this contest end is nice.

Hi, I have been accused of cheating on problem B of this round. It doesn't make any sense because it was a trivial solution. I do see that the people mentioned do have similar solutions (one of them has even contacted me a few minutes back), but since it's just one line of code that gives the solution and the chance of that being similar is fairly high. Is there anything I could do to reverse this? There are no "pre-published" resources, but I request you to take a look this verdict once again.

Thanks.

Hi, I have been accused of cheating on problem B of this round. It doesn't make any sense because it was a trivial solution. I do see that the people mentioned do have similar solution , but since it's just one line of code that gives the solution and the chance of that being similar is fairly high. Is there anything I could do to reverse this? There are no "pre-published" resources, but I request you to take a look this verdict once again.

Thanks.