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
BLABIZOuseful concepts.Our army of testers YahiaSherif, TripleM5da, 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.
NEAR for supporting this round, details can be found in this post.
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 ❤️❤️❤️
As 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
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 ;-;
"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
As this is an egyptian round, being the egyptian king I must perform great in this round. Hoping for good fat +ve delta.
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
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 everyone
I 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 fine
Dang, 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 :(
Problem C was a modification of 1534C - Головоломка маленького Алана
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! :)
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 nodex, if its depth is even (depth of root is 0), assignxandx | (1 << N)to it and the path linking it to its parent node, otherwise assignx | (1 << N)andx.that logic is so clear..! I didn't even figure out the root can be fixed as 1 << N.. thanks for given clue..!
Can you tell me how to solve the problem you mentioned in the comments(How many area can be divided by n lines in a infinite plane)?
I was recently asked this question in an interview. I was not able to give optimal solution. Please help me out.
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.me/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?
Deleted
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.
Deleted
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.
You 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.
Obviously You are a cheater buddy
sus
I already start hearing complain about mass cheating during interview and programming contest.
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
ok
So how can you AC E even faster than you AC C ? It is nonsense
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
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
Just realized that I got WA in problem C cause i forgot to mod the answer by 10^9+7 :')
To not keep you waiting, the ratings are updated preliminarily. In a few days, I will remove cheaters and update the ratings again!
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.