Блог пользователя Igorfardoc

Автор Igorfardoc, история, 3 года назад, перевод, По-русски

Привет, Codeforces!

Мы с Vladithur рады представить вам наш Codeforces Round 769 (Div. 2), который пройдет в Jan/30/2022 17:35 (Moscow time). Этот раунд будет рейтинговым для участников, чей рейтинг ниже, чем 2100.

Мы хотим выразить огромную благодарность:

У вас будет 2 часа на решение 5 задач, одна из которых поделена на 2 подзадачи.

Разбалловка 500 — 1000 — 1500 — 2000 — (1500 — 1500)

Мы постарались сделать четкие условия и сильные претесты к задачам, и надеемся, что они вам понравятся, и вы поднимите свой рейтинг!

Удачи!

Также мы бы хотели запустить тренд оценивания задач из раунда. Нам кажется, что это даст полезный фидбэк авторам и сделает будущие соревнования еще лучше. Поэтому, пожалуйста, оцените каждую задачу после конца раунда.

Задача A
Задача B
Задача C
Задача D
Задача E1
Задача E2

UPD: Разбор здесь.

UPD2: Поздравляем победителей!

Div. 1 + Div. 2:

  1. kotatsugame
  2. tute7627 и jiangly
  3. -
  4. I_Iove_chtholly
  5. Alan_girlfriend

Div. 2:

  1. I_Iove_chtholly
  2. Alan_girlfriend
  3. Wlxsohandsome
  4. 778
  5. i_will_be_less_than_blue
  • Проголосовать: нравится
  • +394
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

As a tester, I like all problems!

»
3 года назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

I can say that all the problems are very interesting to solve and the authors have done a great job inventing them.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +53 Проголосовать: не нравится

By the way, does dkirienko help you?

If the answer is "yes" — is it meaning that participant can solve all problems using Python? :)

Spoiler
»
3 года назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

Is the round going to be Starcraft-themed? :P

»
3 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Hope all of you will get good rating after this round .

»
3 года назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

Love the idea of per-problem feedback prompts! Although I wonder why people already started voting — are those testers or trolls? :P

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +38 Проголосовать: не нравится

    Some of them are testers, and some of them are trolls, I think. But, I really hope they will revote after the round.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +96 Проголосовать: не нравится

      I think it would be better if you have given this feedback voting option in editorial blog instead of announcement blog, Anyway it's a great initiative.

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

        I believe there are people like me who rarely open editorials.

        They should've just added the voting section after the end of the contest by editing the blog.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      And some of them — I believe — has a superpower to foresee the future

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    trollforces

»
3 года назад, # |
Rev. 5   Проголосовать: нравится +24 Проголосовать: не нравится

So please, vote for each problem after the round's end.

you should have waited round to end for putting votes, now alot people will vote but forget to re-vote

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +108 Проголосовать: не нравится

The people who vote for the Bad problem even before they see the problem are the same people who always ruin beautiful things!

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

It is sad to see that some people have already voted "a bad problem" . Anyway, I wish everyone good luck for the contest!

»
3 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

As a tester I think there should be a section to ask for contribution.

»
3 года назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Hello, I am a beginner who recently joined codeforces. Will there be a division 3 contest anytime soon? Thanks.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    You should try participating in div 2 as well. Because div3 is a rarer thing than div2 :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    This is a normal and reasonable question, and I can't understand why there are so many downvotes. I doubt some users just downvote it blindly because there are already some downvotes and it's tempting to add more.

»
3 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I don't understand why is it possible to evaluate problems before the round, it would be good update later , but why now?

  • »
    »
    3 года назад, # ^ |
    Rev. 6   Проголосовать: нравится +19 Проголосовать: не нравится

    So, may be it is a good idea, but I actually do not see much of a difference, because there will always be trolls, and you will not get rid of them by moving the evaluation to the update or to the editorial. As for decent people, I think they will revote after the round, if at first they chose the wrong option.

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

nobody reads tags expect me

»
3 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

As a tester, I do read tags!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

DELETED

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    I think it doesn't. This contest is held on 30/1 14:35 UTC, while COCI contest #4 is held on 29/1 14:00 UTC. Correct me if I'm wrong.

»
3 года назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Hope to get +69.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What about The people who vote for the Bad problem even before they see the problem!! what are u doing?!

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I appreciate the idea of collecting the feedback regarding individual problems. But I'm getting the feel that this way of collecting the feedback might lead to a lot of false statistics. The round hasn't started yet and already you can realize some surprising data.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    I agree that it may collect false statistics, but regardless, it's a good step forward. Sometimes there are just bad problems, you can't deny that. And, I appreciate the effort of the authors to step forward and give chance for feedback. This says that the authors are careful and I hope we'll finally have some good problems, not just edge-case work.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Indeed it is a pretty nice initiative to provide a platform for some constructive feedback wrt to problem set. I'm just suggesting some points of improvement to ensure some sort of validity in the poll results. Like opening the poll after the contest ends to begin with.

»
3 года назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +71 Проголосовать: не нравится

I suggest putting the voting buttons in the editorial. People should provide feedback only after they have seen the solution.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +33 Проголосовать: не нравится

    After being inspired by this I think we will have a huge benefit if we can vote for every single problem after we solved it (maybe there can be some rating restriction for example rating >= 1400). Thus, every problem except its rating difficulty will also have a number that corresponds to its pleasure to be solved and whether it's a good or a bad problem. I think this way both problem solvers and authors can take advantage of this.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Great initiative!

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

new challenge for all contestants........good luck

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Interesting delete line.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Which is more easy problem A or problem E?
I am new on codeforces. Plz tell me.

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Good luck!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Wow! The authors of the round have avatars from Starcraft 2. We should participate!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wowwwwwwwwwwwwwwwwww how can you add the likes?

»
3 года назад, # |
  Проголосовать: нравится -32 Проголосовать: не нравится

as a !tester , i am here to farm contribution.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am not sure the categories for evaluating problems are right. Quite often the problems I fail to solve (or fail to solve without reading the editorial) are the most interesting (best?) problems.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping for a contest which do not contain problems like previous Div2 C

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Good timing of the Australian Open Final, has ended 20 minutes before the contest.

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Good luck everyone

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ALL the best guys..

»
3 года назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

bitforces.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If I do multiple submissions, and all are passed then my score depends on my first submission or last submission

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

great round, loved the problems!

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Hint for task C?

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I have no idea why my solution to B passed pretests :OO

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

The fact that C=E1 in scoring distribution is strange for me.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

back to mathforces :(

also thanks for very not misleading scoring of the last task

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Is C Ad-Hoc?

»
3 года назад, # |
Rev. 3   Проголосовать: нравится -24 Проголосовать: не нравится

DELETED

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +50 Проголосовать: не нравится

    Which of the problems have endless corner cases?

    • A: The edge cases are literally in the samples.

    • B: No edges cases needed here since (n — 1) ^ largest bit always works.

    • C: Not sure if there is a casework soln to this, but my solution just iterates on the value the final element will take and then you just need to check the smallest value $$$\geq a$$$ that is a submask of this element. I don't think anything is casework heavy here.

    • D: My solution uses one nice observation + range queries, maybe the other solution is case work heavy which is unfortunate since range query structures shouldn't be required for a Div2D.

    • E1: No case work here, just find distances and calculate the answer using a weird sort of prefix maximums / decreasing suffix maximum.

    • E2: No clue, didn't solve it, but I doubt you're referring to this problem.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      There could be many different solutions for a single problem. If one takes the wrong direction, then that person might be stuck in many corner cases. I'm initially referring to my case solution for C but I'm also talking about things generally.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        This is interesting. One of the things I hate about myself is that I find it hard to discard an idea, so I end up checking a lot of cases and overcomplicating problems unnecessarily and most of the time I will fail anyway. Checking the straightforward editorial for C after struggling is beautiful. I don't think the 4 cases about the bit values is something to be considered painful casework. My conclusion is that, most of the time, you should blame yourself. Writing simple solutions is part of practice.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится

          Yes, you are absolutely right. It took me some time to realize the importance of avoiding getting stuck in one direction. In most cases the problem should have a clean solution which doesn't require too many cases.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +29 Проголосовать: не нравится

      Why is range queries bad for div2D?

»
3 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

How to solve D without range query data structures?

Btw I really like the monotonic observation. Its such an obvious fact that as we increase the number of elements the gcd will not increase, but it really did not strike me in relation to the problem.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

    I kept a multiset of ban positions for each indices. For instance, a suffix gcd equals to $$$3$$$ at position $$$5$$$ bans position $$$7$$$.

    When we actually update a gcd, we maintain the set. Such updates will not be many as each time at least one of the gcds lose a factor.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    I think the key observation is that given a[i], there can be at most around log2(a[i]) distinct gcds among gcd(a[i]), gcd(a[i — 1], a[i]), ..., gcd(a[0], ..., a[i]).

    So, combined with the monotonic observation, it's fine to maintain a partitioning of [0, i] into intervals, one for each distinct gcd. So in log2(i) time you can find the earliest position j such that gcd(a[j], ..., a[i]) is equal to its length. I guess you could also binary search but that's unnecessary.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Could you elaborate on how you would generate and maintain such a partitioning though? I can think of a way to do this in $$$O(n \cdot \sqrt{max(a)} + n \cdot \log(max(a)) \cdot \log\log(max(a)))$$$ but this is too slow. I basically can't figure out how to eliminate factorization for newly added factors from $$$a_i$$$.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Sqrt decomp go brr

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

There were so many submissions by unrated accounts around the same time. Were the solutions of first 4 problem leaked or something ?

»
3 года назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

bit operation contest. lacked variety of problems...

»
3 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I love problem D

Spoiler
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Realized just after the contest that, replacing a for loop with while(bs) will work like magic

    Nice problem :)

»
3 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

bitforces

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very cool contest and interesting tasks!!!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Read at this bc I can't delete this comment: https://codeforces.net/blog/entry/99442#comment-882354

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +20 Проголосовать: не нравится

More cheat today.

@ MikeMirzayanov

we need to ban the cheat accounts,this kind of account makes imfair to cp

What's more , I find that most of accounts which submitted their code in 01:59 of E were suspect of cheat.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How is this wrong for E1? I maintained an Euler tour and segment tree. If I want to connect node 1 to node x. So max distance here will be max((max distance in the subtree of node x — dis[x] + i), max in the remaining tree excluding the subtree). Finally I take min ans for each x. Can someone pls give a counter example where this fails?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    Here is a case where your code will fail(if I have understood it correctly)

    9

    1 2

    2 3

    3 4

    4 5

    5 6

    6 7

    4 8

    8 9

    The correct answer for x = 1 is 3, but by yout logic it's 4

»
3 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Is this even possible to create a solution for D that exceeds time limit?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In question B ,if we take input 6,then according to editorial solution answer will be {3 2 1 0 4 5} but the optimal ans is {2 3 1 0 4 5}.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    The problem asks us to minimize the maximum xor among pairs of adjacent elements. Both 3 2 1 0 4 5 and 2 3 1 0 4 5 have the same maximum xor of 0 ^ 4 = 4, so I don't think it really matters.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good contest

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

During the contest when I was solving problem c, I got the intuition that we can solve this in a total of three steps in these sequence 1. either increase a or b by some amount. 2. take the OR. 3. increase the b to match the value with the second step value. Although I was not able to prove it during the contest. I submitted it just based on some gut feeling. So I just want to know is this the case with other people too? or do you guys first prove your solution and then submit it?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

MikeMirzayanov I'm not really sure where to put this, but I received these two messages:

Attention!

Your solution 144568353 for the problem 1632D significantly coincides with solutions Weierstrass/144555583, codebuster_10/144561876, 876pol/144568353, Winterfrost/144569022, xiaoququsd/144572170, Kanheyalal/144572862, dimss/144575074, Kawaii/144576113, matouzouken/144576356. 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.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

Attention!

Your solution 144557728 for the problem 1632C significantly coincides with solutions Weierstrass/144543081, codebuster_10/144548751, Kawaii/144549603, matouzouken/144551794, Winterfrost/144556519, 876pol/144557728, xiaoququsd/144562448, dimss/144563984, Kanheyalal/144564250. 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.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I wrote the code for both these submissions locally on vscode and I don't know any of the people mentioned in the message. Also, the codes don't seem that similar in the first place.

However, just to be sure, the code for 1632C is fairly short and is just a false positive. I had also submitted a couple WA submissions before this one, so its not like I copied it off of someone.

I got the code for the sparse table in 1632D from https://brilliant.org/wiki/sparse-table/, and the rest of the code is also short and is just two pointers.

(also, sorry for tagging you)

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Why their is positive Plag check, submissions are not even similar at all ? MikeMirzayanov Please see to it. I ran both my submissions locally and use my own template, any of the given submissions does not seem to be similar to mine at all.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also received this message, and I think our codes are completely different (I even didn't use any existing templates).

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

wow how many cheaters were removed? I should have got only +7 delta at the end of contest but now got +22

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    SO CRAZY that one out of four accounts were cheaters in last round.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I think that a good way to anti the cheater is to solve the problem faster than them. So whether they are cheating is unmeaningful.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In the third problem, isn't b' the same as a'|b. But, it doesn't give me the correct solution. If anyone could explain.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi I am a newbie and would appreciate some assistance here. My submission fails with verdict Wrong answer on test 2. However when I click on my submission number I can only see test case 1 which is succeeding. My question is how can I see test case 2 ?

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    During the competition you will not be able to see private test cases. However, after the competition, you can resubmit your code and you will be allowed to see them.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I have a trouble understanding problem D example test case 3:

input
7
2 12 4 8 18 3 6
output
0 1 1 1 2 2 2 

I expect that for prefix (2 12 4 8) we will need only 2 replacements, but it's 1 according to example

Specifically, I see two separate pairs: GCD(2, 12) = 2 and GCD(4, 8) = 2. I expect that we will need to replace one value in each pair

Can you help me?

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi MikeMirzayanov, My id has been hacked and someone has submitted fraudulent copied solutions from my account. They have even changed the email address of the account to something random and I can't even recover it. I am sending this message from an existing session. Dm'ed you the details. Please help.