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

Автор majk, 5 лет назад, перевод, По-русски

Всем привет!

В 20.07.2019 18:35 (Московское время) состоится Codeforces Global Round 4.

Это четвертый раунд из серии Codeforces Global Rounds, которая проводится при поддержке XTX Markets. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.

У вас будет 150 минут на решение 8 задач. Разбалловка 500-750-1250-1750-2000-(1500+1500)+3250+4000.

Призы в этом раунде:

  • 30 лучших участников получат футболки.
  • 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.

Призы в серии из 6 раундов в 2019 году:

  • За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
  • Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
  • Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.

Задачи раунда разработаны мной.

Я хочу поблагодарить:

UPD: Раунд закончен. Надеюсь, что вам задачи понравились! Прошу прощения за проблему с задачей Е.

UPD2: Разбор

UPD3: Поздравляем:

  1. ainta
  2. Radewoosh
  3. tzuyu_chou
  4. LHiC
  5. Benq

UPD4: Результаты после четырех раундов.

  • Проголосовать: нравится
  • +875
  • Проголосовать: не нравится

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

What about ISeeDS? He has feelings too

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

And, of course, Accepted_ as a welcome guest of any contest

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

And, wish that wrong_answer stays away

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

Sounds great!But hope for no reading comprehension problems....

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

An old comment from the setter of the contest :)

For those who don't want to click
»
5 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Tourist is coming soon

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

Global Round = div1 + div2 + div3 = div6

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

8 problems and just 150 minutes is it enough????

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

    Generally, educational rounds have 7 problems and 120 minutes of time. So comparatively it is enough.

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

      Are you compare the educational with global round ?? educational is for div2 and global round for all division

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

        For div3 also... (you can check contest history)

        and for div1 users if you add 2-3 easy problems in contest, it doesn't change anything for them.

        Required time for contest depends more on difficulty level than number of questions.

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

      And also this round needs to test the abilities of people range from beginners to masters so it definitely needs to have enough time for all the people to solve the problems.

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

    No, of course not. We need 300 minutes.

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

Btw, did anyone notice that majk is setting a global round and a local round these days?

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

Although we are Chinese,we still try to join in every Global Round.

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

    But there isn't a "Codeforces Global Round 1" in your contest history.

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

    Most rounds is a bit late for Chinese,hope the contest can be earlier,and we won't stay up late and feel sleepy the next day.

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

      I agree with your suggestion. I hope that in the future contests in Codeforces could start earlier, maybe 20:35 or 21:05 UTC+8 will work, so that we don't have to stay up very late and feel sleepy the next day.

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

      Most rounds are a bit early for people like me on the US west coast.

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

Global round 3 is good go for global round 4

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

Wish you a job promotion :-)

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

Thanks MikeMirzayanov also for updating and adding amazing features in CODEFORCES regularly.

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

No one is talking about Memory_Limit_Exceeded. That's sad

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

i hope that will be funny:)

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

I hope that the meaning of all the problems are easy to understand.

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

It could be the last contest which is rated for Div.1, and the last big global round before IOI 2019 Azerbaijan.
I hope everyone's good luck, as a participant of IOI 2019.

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

Hope this will not happen :3

kkkkk

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

have a good contes :)

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

i hope i become yellow after this

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

What about UKE,OLE,_Wrong_Answer_

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

hope i InvincibleMario one day

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

Did anyone notice 'alice' and 'bob' in the blog tags? Be ready for some good game theory problems.

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

    :3 Meanwhile, the problem will be like:

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

      They start the game by drawing convex polygon in which the area of it doesn't exceed X squared units and is at least Y squared units, if a player can't draw a convex polygon without crossing an already drawn convex he loses, determine the winning player if both played optimally.

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

        This problem is really easy. Solution:

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

majk come back with a contest after Good Bye 2018

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

Hope I will be either retired.coder.1 or WHITE2302 . I don't want to be grey anymore.

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

Why no one has made an account with a nickname "Idleness_limit_exceeded"? :c

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

How Global Round's rating distribution executes? Do Div1 and Div2 contestants get seperate rating? How likely Div2 contestants increase rating? Thanks!

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

TimeLimitExceed and TimeLimitExceeded will be sad if they shrink to TLE

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

I think TLE is abbreviation for --> tourist limit exceed please don't gimme negative feedback I am just joking

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

an AK-king jqdai0815

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

Why arsijo again?

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

    why not ? because of just one mistake he did before ? i'm afraid for you ;

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

У вас тех полетел

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

Should I do it? I am new in programming.

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

Everything is gonna be Okay

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

madhav_1999 will become master today! — Prokhar

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

Could you please postpone the contest 15 minute later ?

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

And hopefully the round won't become Unrated.

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

Is there a page with current standings?

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

I hope that the contest will be good,funny and interesting like the announcement .

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

gl hf

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

i have to stay up late

i look like the panda in my photo

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

When this "prior to round" happen????? Only 15 minutes left......

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

speedforces strikes again again

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

    Now that the round is over, I feel I should comment on that. We considered both D and E to be tricky problems, even some very good testers had problems with them. Perhaps C and D turned out to be a bit easier that anticipaded.

    F on the other hand, was a different beast. I originally proposed a completely different problem — with in my opinion a cute observation. However, it was geometry and testers almost went on a riot because of the implementation difficulty.

    About $$$10$$$ days before the contest I came up with the problem that is now $$$F1$$$, but the testers saw it as too easy, even easier than D or E — and the gap between $$$F$$$ and $$$G$$$ was afwul.

    So I realised then that we can increase $$$m$$$ and it adds to the problem. Suddenly, it was too difficult and it was the gap between E and F that was brutal. With the contest fast approaching and the tester's ranks dwindling, we realised that the safest way to mitigate was to split F.

    Some small gap still remained though, but I'd say that the ratio of ACs on adjacent problems around $$$4$$$ is fine (after all, it has to reduce from couple thousand to only a few in around $$$6$$$ problems). Please try to understand that it is sometimes quite difficult to judge the difficulty based on a small sample of testers. Additionally, if you find out two days before contest it is going to be speedforces, the best solution is typically to keep it that way rather than to perform some ninja fixes.

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

What happened just now? My rank changed from 900+ to 400+ and to 900+ again...

[Edit] Got it.

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

Спасибо за хороший раунд) Нет, он хороший не потому что у меня получилось решать задачи, потому что задачи были интересными) Побольше бы таких раундов

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

i am suffering subsequence string phobia.

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

" The round is still rated. " ?????? What the f**k ??????

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

    My friend locked his problem E but he can't change his code after rejudged and already lost his rating

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

      You seem to care a lot about your friend! I think HE can ask organizers to make it unrated just for him.

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

    Why unrated after rejudged? I can't understand.

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

    The round is always UNRATED or at the edge of UNRATED if arsijo is the coordinator.

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

How to solve G?

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

    Actually, I didn't get pretest passed in this problem, but I have an idea.

    Solution 1
    You can replace the problem to a new problem as follows by using euler tour method:

    • Initially, there is an array $$$a = $$${$$$a_1, a_2, ..., a_N$$$} and $$$b = $$${$$$b_1, b_2, ..., b_N$$$}.
    • Query type 1: Add $$$a_l$$$, $$$a_{l+1}$$$, $$$a_{l+2}$$$, ..., $$$a{r}$$$ by $$$x$$$.
    • Query type 2: Get the maximum value among {$$$|a_l| * |b_l|, |a_{l+1} * b_{l+1}|, ..., |a_r * b_r|$$$}.

    To solve this new problem, you can use sqrt decomposition by query.
    Let's think about to solve from query $$$1$$$ to $$$B$$$ with $$$O(N + B^2 log B)$$$ complexity.

    • You can divide at most $$$2 * B + 2$$$ subsegments, that the value of $$$a_i$$$ that increased in add query is the same in subsegment.
    • Add query: Just add $$$x$$$ in proper subsegments. Complexity $$$O(B)$$$ for each query.
    • Get-maximum query: Use Convex-Hull Trick and binary search. The convex-hull can calculate with precount. Complexity: $$$O(N)$$$ for precount, $$$O(B log B)$$$ for each query.

    Since you should process $$$B$$$ queries, The total complexity that takes to calculate all answer in query [$1, B$] is $$$O(N + B^{2}logB)$$$.

    So, how to solve in not only query $$$[1, B]$$$, but also $$$[B + 1, 2B]$$$, $$$[2B + 1, 3B]$$$, $$$[3B + 1, 4B]$$$, and so on?
    You can find the value of $$$a_i$$$ when query $$$B, 2B, 3B, 4B, ..., $$$ has just finished, by using cumulative sum method. Since the value of $$$b_i$$$ does not change, you can also solve in query $$$[B + 1, 2B]$$$ and so on, as same as query $$$[1, B]$$$.

    If the backet size $$$B$$$ is nearly $$$\frac{B^{0.5}}{log_{2}B}$$$, the total complexity will be $$$O(B^{1.5} * sqrt(log_{2}B))$$$.

    Solution 2
    Since the constraints is $$$n \leq 200,000$$$, $$$q \leq 100,000$$$ and the time limit is 5sec, since the process is very light, I think that even straight-forward brute force $$$O(NQ)$$$ which is very very very very fast may pass.
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E?

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

    If you consider two first and two last characters of the string, you are able to find one in first two and one in last two that match. Add them to your palindrome.

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

    Hint: Since no two characters are adjacent, and there are only 3 characters in the alphabet, there exists a character in the first two characters of the string that equals a character in the last two characters of the string.

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

    Since no consecutive letters are the same, you can make any even-length palindrome into a longer odd-length palindrome. So let's fix the middle of the palindrome, how about s[n/2]. Then you can show that from the midpoint, you never have to go more than two spaces to the left, or two spaces to the right to find two letters that are the same.

    So at worst, it will take 4 spaces to add 2 letters to your palindrome.

    Be careful of n=4 case (may need to try other midpoint).

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

How to solve E

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

E's solution is cute, although the problem is a little contrived.

EDIT: The key is pigeonhole principle. Take the last two and first two letters, there must be two letters that are equal (and not adjacent, since no two adjacent are the same). Take these two and recurse. If there are fewer than four characters, just take any one.

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

    Can you share your cute solution :)

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

    really kyot solution

    i overcomplicated the problem :\

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

    Am I the only one to try solving problem without that "no repeated letters" thing for 15-20 minutes before realizing that problem is totally different?

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

      Just scroll down, I solved it without knowing that.

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

        How? And can you prove your solution?

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

          I can't prove it, but it makes sense.

          My solution optimizes the $$$O(N^2)$$$ dp solution using next and before arrays and limiting the search on the first point the answer reaches the needed length.

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

Good tasks, thanks)

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

My girl friend is beautiful, smart, kind, rich, humourous and never blame anything on me!

I consider her a perfect girl friend.

Unfortunately, I discover that SHE is actually a man.

That's my point on the checker of the problem E.

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

Not so many Pretest :(

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

We had an issue with the problem E. The rejudge changed ~10 AC submission to WA in pretests. Since only ~10 people were involved in this issue, we do not see a reason to make this round unrated. If you have another opinion, you are welcome to share it.

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

Thanks to Pretest XD

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

    I saw you hacked A. Can you tell me please what was the hack for it ?

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

      That would have hacked me because I misread the problem and thought that you can capture the 1 to have a total coalition size of 6, which would enable you to capture the 3s.

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

first four problems were not THAT hard as in previous contests

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

pretests too strong barely 10 hacks total

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

Oh, nice problem G, I've seen very similar things only a million times and it always ensured me at least one hour of fun coding and debugging, so happy to be given another chance.

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

    Isn't problem F nice as well? Or I guess all the fun with it was too short for you to feel the excitement?

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

I would like to thank:

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

In Problem A, for testcase: 2 6 2

shouldn't the answer be 1 1 as the question mentions "If Alice's party has enough people to create a coalition on her own, she can invite no parties." i got an "unsuccessful hacking verdict" defender's output was: 2 1 2

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

    2 1 2 is also correct. You don't have to minimize number of parties.

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

      Yes but as i said the question mentions "If Alice's party has enough people to create a coalition on her own, she can invite no parties."

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

    I feel that mate. I got that twice

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

    Both outputs are correct. Multiple solutions possible.

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

    That's a good point, my solution also gives "2 1 2" but it passed system test... Maybe the intended meaning of "she can invite no parties" is "it is allowed that she doesn't invite any parties".

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

no two consecutive characters are the same

FML, I solved E for general strings

UPD: got TLE

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

Just little FYI from a noob coder if anyone doesn't know already..."str = str + xyz" takes waayyyyyy too much time compared to "str.push_back(xyz)"... got to learn that the hard way today :(

Well at least learned something :D

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

    You can also do the following: str += xyz

    str += something in strings is much faster than str = str + something for C++

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

      Well, += just adds to the end of the string (I assume that it just push_backs), while str = str + xyz has to copy the whole string, then append, and then save that value in the original variable.

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

      Thanks! Noted.

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

    Another noob coder here... took me three TLEs to realize the thing.

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

Imo score distribution wasn't good enough (maybe it's just for me). I spent 1:30 for B, 0:15 for C and 0:30 for D.

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

Just look at this submission: 57419391

Brute force wins again!

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

Every time I finished the code dugging, the game had just ended. What a pity!

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

I only now noticed abs in G. Can't even read :(

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

What is the reason for the low constraint at problem D? It could be solved even with $$$10^6$$$ limit

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

In problem E, will there ever be a case where answer is IMPOSSIBLE?

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

    No.

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

I think some people just guested problem C after seing samples

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

    Right. No idea why it's true xd.

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

      Call the vertical segment white if it's white from the left/black from the right. Note that if segment is white then all others in the same row also white. Same for horizontal

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

      4 choices for top-left square. Two choices for the rest along the top and the left. Only 1 choice for the remaining squares. i.e. if you choose the top row and the left column every other square is forced to be a single orientation.

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

Problem C has best samples ever

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

    It would have been better if only one test case w=2 and h=2 was given. Then most of them who solved it just by test case would have to think of proof(including me lol).

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

E has got three greedy tags and two string tags...

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

It it just me, or prob.A's statement is TOO HARD to read? (you can check my submissions)

I'm not familiar with the Parliamentary System in some western countries :(

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

ovvo

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

In D, If n is prime, then the answer is a circular graph. Otherwise, create a circular graph at first and then create extra edges by connecting nodes with degree 2 to make the number of edges a prime number.

Is this the only solution?

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

Problem G can be solved using sqrt decomposition. In the contest I chose a bad block size and didn't get AC. I'm so done right now.

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

    Using dfs order we can turn G in to the following range query problems:

    Given 2n number a[1], a[2], a[3], ..., a[n] and b[1], b[2], b[3], ..., b[n]. You have to query max(abs(a[i])*b[i]) for some l<=i<=r and add a positive number x to a[l], a[l+1], ..., a[r]. Note that b[i] is set from the begining.

    Now for each i from 1 to n, let w[i] be the sum of x added to a[i], then you have a graph of at most 2 lines representing the value of abs(a[i]+w[i])*b[i]. To get the answer for some query, just get max of all (a[i]+w[i])*b[i].

    To update and query fast, split the array in to blocks of size S. For each block you can represent the lines using a Lichao tree or using CHT. I "upsolved" using CHT, but maybe Lichao tree will work as well. For each update query, simply update all the elements from the left most and right most block, and rebuild the two blocks, for all the blocks in between, keep an array w[] to know the elements in the blocks have been added by how much, this take O(Slog(S)+N/S). For each get query, you can just do the same, get the elements from left most and right most block, query each of the inbetween block in O(log(S)), so this take O(S+N/S*log(S)). Also this approach can be used even if you want to add negative number to a[].

    Honestly I didn't think this would pass, and I hoped that it gets TLE. But it works, and I chose the wrong S, so I got TLE in the contest. This disappointed me very much on top of the also very dumb mistake I got in F2. Still the problems are very good. Codeforces rules are very punishing, so something like this is to be expected.

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

      For anyone interested in implementing this approach, S=100, 200, 300, even 400 will get AC. Just don't be bad like me and use 500 or something.

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

        Yeah, that sucks. I tried hard to cut the solutions with extra log factor — we had two such solutions and they all needed around 8 seconds on some cases.

        On the other side of the road, there was Java that also needed to pass.

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

        Needs more coke spilling

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

I was able to complete 4 questions in this challenge. I usually use ideone for compilation of my code . My code was copied by newbi/57387826, sos_123/57387881 . I was removed from this contest.This is quite unfair and strict actions should be taken against these contestants

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

    As stated in codeforces rules about third party code unintentional leakage is also a violation so be careful next time.

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

    I checked the submissions you mentioned. Both of them submitted the code before you.

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

      I didn't register for the competition so I had a late penality of 10 minutes . I had compiled it way before submitting it . You can look in both of their profiles lots of there submissions are skipped .

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

Could anyone explain why my submissions still at Pretest Passed? I solved 3 problems but my rating has been counted as 0 problems.

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

majk:

Also majk:

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

When t-shirt winners will announced?

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

    We are still investigating the issue. We will post the winners after we get the official results of the round.

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

Thanks checker for good check.

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

MikeMirzayanov, это теги в задаче G. Наверное надо пофиксить.

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

what is wrong in this solution of problem E.

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

Can anyone prove this statement, for every n such that there is a prime between n and 3n/2?

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

T-shirt winners!

We used these files to find the winners.

randgen.cpp
get_ranklist.py
List place Contest Rank Name
1 1178 1 ainta
2 1178 2 Radewoosh
3 1178 3 tzuyu_chou
4 1178 4 LHiC
5 1178 5 Benq
6 1178 6 Reyna
7 1178 7 maroonrk
8 1178 8 nhho
9 1178 9 mnbvmar
10 1178 10 yfzcsc
11 1178 11 isaf27
12 1178 12 MrDindows
13 1178 13 scott_wu
14 1178 14 DearMargaret
15 1178 15 Swistakk
16 1178 16 gop2024
17 1178 17 webmaster
18 1178 18 gepardo
19 1178 19 E869120
20 1178 20 dreamoon_love_AA
21 1178 21 Marcin_smu
22 1178 22 krijgertje
23 1178 23 Egor
24 1178 24 Elegia
25 1178 25 amethyst0
26 1178 26 kmjp
27 1178 26 G.Z.V.O.D.E.N
28 1178 28 aid
29 1178 29 dlalswp25
30 1178 30 tribute_to_Ukraine_2022
36 1178 35 sevenkplus
56 1178 56 Roundgod
76 1178 76 atoiz
110 1178 110 Ari
147 1178 147 tabasz
159 1178 159 asokol
169 1178 169 mohamad
174 1178 174 PinkRabbitAFO
184 1178 184 Anachor
189 1178 189 MarcotheFool
255 1178 255 Zayin
256 1178 256 rotavirus
284 1178 284 kektus
313 1178 313 Ferume
314 1178 314 Mikaeel
377 1178 377 3.14roca
401 1178 401 mghzs1997
403 1178 403 Kerim.K
449 1178 449 MonkeyKing
472 1178 471 ivanilos