Ahmed_Hosssam's blog

Codeforces Round #788 (Div. 2)
By Ahmed_Hosssam, 3 years ago, In English
عيد سعيد(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:

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

  • Vote: I like it
  • +565
  • Vote: I do not like it

Comments Comments (135)
| Write comment?
»
3 years ago, # |
  Vote: I like it +76 Vote: I do not like it

GUC gang!

→ Reply
»
3 years ago, # |
  Vote: I like it +108 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +150 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Eid ul Fitr Mubarak to you and your family.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Score distribution? (:

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

EID Mubarak

→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Eid Mubarak

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

distribution?

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Egyptian round? Long time no see)

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Hemose is back yayy! :D

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

congratulations Bakry qualifying to ioi

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

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Looking forward to participate! Eid Mubarak

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +30 Vote: I do not like it
As a GUCIAN tester, I am proud of you and your great round.
→ Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

GUC on fire

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe Egyptian round is full of Bitwise and Math problem hahaha :)

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

EID Mubarak

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

3id s3id!

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

i hope be pupil in this round

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why you practice so many problems，but still newbi？

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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!

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how cool man

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Eid Mubarak(⦁ᴗ⦁)

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Good luck everyone

→ Reply
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Good luck everyone!

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Wish you all a great rating gain.

→ Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Eid Mubarak to everyone

→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I enjoy problem E but I hate problem D!

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      what is the the proof?

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Can't compile file:
program.cpp: In function 'int main()':
program.cpp:266:17: error: template argument 1 is invalid
  vector<__int128> limit(60, 0);
→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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 :(

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Problem C was a modification of 1534C - Головоломка маленького Алана

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Was F digit dp?

→ Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E is also a math puzzle, like D :)

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

link

Although E and F were very nice

→ Reply
»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Q4 is Guessforces

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Damn you commented with the wrong account

    → Reply
»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Thanks for the strong pretests!!

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    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

    → Reply
»
3 years ago, # |
← Rev. 92   Vote: I like it +16 Vote: I do not like it

Deleted

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Every new line creates two triangles with each existing line.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +15 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it +10 Vote: I do not like it

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

              → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

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

          → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 6   Vote: I like it +5 Vote: I do not like it

      Deleted

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I said "One" not "The first".

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +36 Vote: I do not like it

      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 statement
      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    E surely doesn't have much details.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      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.

      → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    +1 to every point

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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?

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

They should have kept round 786 on Eid ;)

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 6   Vote: I like it +6 Vote: I do not like it

    I already start hearing complain about mass cheating during interview and programming contest.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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!

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oeis may help you

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +43 Vote: I do not like it

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 :(

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the logic for problem A ?

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +73 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply