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

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

Всем привет!

Скоро состоится Codeforces Global Round 6, время начала: 17.12.2019 18:05 (Московское время).

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

Соревнование продлится 2 часа 30 минут, вас ожидает 8 задач, при этом одна из задач будет представлена в двух версиях. Разбалловка 500-750-1250-1750-2000-2500-3500-4000.

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

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

Призы в серии из 6 раундов в 2019 году (текущие результаты):

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

Задачи этого раунда придуманы и подготовлены мной. После раунда я буду доступен в Discord для обсуждения задач.

Я благодарю следующим людям:

Присоединяйтесь!

UPDATE: Раунд окончен! Надеюсь, что он вам понравился, несмотря на то, что последние задачи оказались сложнее, чем мы думали. Системное тестирование скоро начнется.

UPDATE 2: Разбор

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

  1. webmaster
  2. sunset
  3. tourist
  4. whzzt
  5. hos.lyric
  6. eatmore

UPDATE 4: Финальные результаты всех Глобалов в 2019 году

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

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

I am always waiting for such a DIV1 + DIV2 round :)

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

Hoping to see a colour change.

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

Once upon a time there were instant editorials after the end of contests.

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

Can some red coder suggest how a person (not very good at maths) can reach that level?

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

Я думаю это будет крутой Раунд :) Помню прошлые и надеюсь что этот будет еще лучше) PS: И сложнее))

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

 Me Everytime

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

Anyone noticed the blog tag “Alice” and “Bob”?

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

This round for disha :- my high school crush Hoping to get better rating

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

Missed 2 of them because of my final exams. Tomorrow I have my finals in algorithm design. This time, to skip this contest would be to not study. Therefore I must do the contest, of course, only because I want to study.

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

So we have tourist and wxhtxdy both registered for the round, it will be fun stalking the standings page.

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

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

Why can't comments be sent in Chinese?

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

hope to see dark blue in the profile today.

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

А когда объявят разбалловку задач?

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

Distribution ?

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

attending university classes makes my iq lower by 20 but I will try

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

Speedforces!!

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -27 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

What was the solution to problem E, although I got a AC, I still feel that a lot of solutions will fail systest including mine.

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

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

E is easier than D...

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

What is pretest 2 of B?

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

How to solve D?

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

god damn it I needed 2 more minutes to submit C

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

nvm

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

Could you guys show me some hints for D? <3

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

Problem D --> Splitwise Algorithm Was easily available on internet. This is sad lol.

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

50 minutes of debugging for a frickin number of line in output for problem D. at least i found out the mistake last sec.

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

How to solve B in cpp?

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

Does anyone have a test case for problem E that will fail the basic solution?

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

    The reason for so many fails on test case 11 is the handling of the order of events. If you kept track of number of bonuses to a resource, there is a possibility of adding and subtracting the same resource in a single query i.e., a bonus (a,b,c) just ends up replacing the exact same. Only if I had swapped 2 lines...

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

Am I the only one who treated D as a graph problem and keep finding patterns?

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

Can someone explain me how to solve D with realisation moments. I've got, that if we have edges like a -> b; b -> c, we can make them a -> c and remove a -> b and b -> c.But how to code it?

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

I am so unlucky problem C i solved in last minute when i was submitting my solution 10 sec was left but unfortunately i failed. Feeling unhappy.

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

How to solve D?

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

https://mirror.codeforces.com/contest/1266/submission/67110424 Can someone tell at what test case my code is failing for D. I tried many, all succeeded, but it gives WA in pretest 5

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

Out of curiosity — how many people proved their solutions of D and E?

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

Are the tests weak for E or this testcase isn't possible? ~~~~~ 3 1 1 1 3 1 1 2 2 1 3 3 1 1 ~~~~~

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

How to solve C for r,c >= 2 ?

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

It was really difficult round :( Grandmaster for 3 days (P.S. D was quite interesting, though)

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

Hello, dear majk, it seems to me that you would be good at doing olympiads for mathematicians!

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

PROBLEM D: just find out balance for each person: for each line of input:

input u, v ,d 
balance[u] -=d
balance[v] +=d

balance is negative : he must give money

balance is positive : he must take money

every giver returning money to taker eliminates one giver or taker. no need to sort.

67119475

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

Greedy $$$\mathcal{O}(m^2)$$$ solution for D passed the system tests but failed to this test:

100000 99999
1 2 1
2 3 2
3 4 3
4 5 4
5 6 5
. . .
99999 100000 99999

This is sad because I have similar solution which got TL5.

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

D is neat because it both is a real life problem and can be solved with a real life approach.

E is however weird. It just feels like you just do what it tells you to do.

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

Hi everyone, here is the list of T-shirt winners!

List place Contest Rank Name
1 1266 1 webmaster
2 1266 2 sunset
3 1266 3 tourist
4 1266 4 whzzt
5 1266 5 hos.lyric
6 1266 6 eatmore
7 1266 7 Um_nik
8 1266 8 neal
9 1266 9 zyb
10 1266 10 Endagorion
11 1266 11 _h_
12 1266 12 300iq
13 1266 13 Petr
14 1266 14 Amoo_Safar
15 1266 15 maroonrk
16 1266 16 betrue12
17 1266 17 ainta
18 1266 18 ecnerwala
19 1266 19 KAN
20 1266 20 kdh9949
21 1266 21 Kostroma
22 1266 22 aid
23 1266 23 Maksim1744
24 1266 24 gamegame
25 1266 25 receed
26 1266 26 amethyst0
27 1266 27 icecuber
28 1266 28 BigBag
29 1266 29 snuke
30 1266 30 PedyD
33 1266 33 LJC00118
57 1266 57 ehnryx
71 1266 70 nuip
93 1266 93 tempura0224
127 1266 127 yhchang3
142 1266 142 schtamas
168 1266 168 sarkar
181 1266 181 sidhant
235 1266 235 Wild_Hamster
237 1266 237 jschr
284 1266 284 Flying_streaky_pork
314 1266 314 aryanc403
325 1266 325 Deemo
344 1266 343 jiwansandhu
391 1266 391 qx4ever
420 1266 419 tubone
427 1266 427 Lgq_3de5
453 1266 453 peterr
461 1266 461 unnoticable_guy
482 1266 482 Superuzir
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +66 Проголосовать: не нравится

eatmore, can you explain your approach on H? It's different from my solution, and I only managed to hack it via massaging the stress test.

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

    My solution is using simulation with memoization. I don't know its time complexity. My implementation can probably be optimized, but I didn't have time to do it during the contest.

    It works like this: there is a map, where the key is the current vertex and the current state of some set of vertices. The set is such that, starting from the current state, the token will enter each vertex in the set at least once before entering a vertex that is not in the set. The value is the vertex that is reached and the new state.

    This approach should work really well on structured graphs, like red edge from $$$i$$$ to $$$1$$$ and blue edge from $$$i$$$ to $$$i+1$$$ for all $$$i$$$.

    I think that my solution can be adapted to solve your bonus problem as well.

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

Div1+Div2 rounds are always fun to give <3

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

1266B - Dice Tower teaches me that i need to read problem's statement carefully.

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

If someone wants to feel some pain.

My Solution to E in the contest at the very last minute Submission.

Later, when I found the bug. Submission

Goes in the corner
»
6 лет назад, скрыть # |
 
Проголосовать: нравится -65 Проголосовать: не нравится

Why can't comments be sent in Chinese?

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

congrats neal !!!

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

why my dp solution get Wrong answer for problem A.

here https://mirror.codeforces.com/contest/1266/submission/67097431