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

Привет, Codeforces!

В 28.11.2018 17:35 (Московское время) состоится Educational Codeforces Round 55 (рейтинговый для Див. 2).

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Михаил MikeMirzayanov Мирзаянов, Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров и Иван BledDest Андросов.

Удачи в раунде! Успешных решений!

А вот сообщение от наших друзей из Harbour.Space:

Hello Codeforces!

We are excited to announce that the Hello Muscat Programming Bootcamp registration is open! The camp will take place from March 9th to March 15th, 2019, and our early bird discount of 15% is going until December 15th!

This next edition in our Hello Programming Bootcamp will run in parallel with the traditional Moscow ICPC Workshop — both Bootcamps’ contests will be identical, and contestants will be able to see their position in the General Leaderboard. Every day, both camps will be competing simultaneously, 4,000 kilometers from each other!

REGISTER FOR THE BOOTCAMP

We would also like to remind you that the deadline for applying to the Master’s in Robotics programme scholarship will close November 30th, so we encourage you to check out the website to see the all the requirements and apply!

APPLY HERE

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

Место Участник Задач решено Штраф
1 I_love_Tanya_Romanova 7 157
2 theodor.moroianu 7 330
3 halyavin 7 361
4 Radewoosh 6 158
5 palayutm2001 6 190

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 halyavin 131:-8
2 zdw1999 55:-4
3 MarcosK 42:-1
4 ismagilov.code 64:-48
5 garipov.roma 48:-24

Было сделано 1354 успешных и 1065 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A I_love_Tanya_Romanova 0:02
B Dalgerok 0:04
C I_love_Tanya_Romanova 0:08
D hitman623 0:15
E lqs2015 0:11
F ko_osaga 0:47
G RomaWhite 0:08

UPD2: Разбор опубликован

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

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

Yoo!! Another comment by harrypotter0

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

It's been so long since MikeMirzayanov appeared as a problem setter(except div. 3) :)

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

Can something be done please to avoid clashing with the SRM?

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

Good

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

(int) Round 55 Div. 2 = 28 November :D

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

Судя по организаторам, раунд будет очень даже хорош

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

We haven't seen div3 for long time.

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

Everytime I said "Hope we all have a good rank and I want to become expert"then got a bad rank,so I say hope everyone enjoy this contest this time :D

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

Yoo!! Another contest by Pik Mike How To lomk Him ? we Didint have Div3 For Long Time And Is It Rated ? that isn’t something to be happy about

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

Clashes with Carlsen vs Caruana tie-break

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

challenging problems are today.

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

How to solve G??

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

    Make a flow network and represent each edge as a vertex. Connect each "edge" to the source with capcacity the weight of the edge. Connect every vertex V of the graph to the sink with capacity a[V]. Finally connect each "edge" with the 2 vertices it connects with capacity Infinity. The answer is sum of weights of all edges — min cut in this network.

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

      Can someone elaborate why this works and what's the intuition behind it?

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

        Think of it like this. Initially we have taken all "edges" to form our subgraph. If we cut an edge connecting source to "edge" it means we don't take the "edge" in our subgraph, similarly if we cut an edge from vertex to sink we don't take the vertex in our subgraph. If an edge is present in our subgraph then the 2 vertices it connects must be in our subgraph too. If an edge is not present in our subgraph then atleast 1 of the 2 vertices it connects must be out of our subgraph. In this network any cut will fullfill these rules(try to see why this is true) and to maximize the answer we just need to find the min-cut.

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

        I can help you with that :P. In fact, the book "Algorithm Design" by Jon Kleinberg, Eva Tardos can be truly revealing about that.

        Go to page 396(Chapter 7 Network Flow). This problem is known in the literature as "Project Selection". Enjoy.

        PD: The book i pointed to you is amazing, there are other non straight forward applications. My suggestion: Read other chapters as well.

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

Is Dinic's algorithm enough for problem G? Seems the complexity should be something like O(n3).

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

    No, in this case graph has special structure. All path from s to t has length 3, so there won't be n phases of using BFS, so it has the other complexity. As I understand this is something like O(nm).

    Bonus: i am not sure, but as i understand if you use scaling complexity is better

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

halyavin is here.

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

that's not fair I actually wasted 15 min on A because i cant understand the second test case until the Global announcement.... maybe I would have solved C I'm just putting final touches on my solution

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

Really good contest, tricky A though :D

Can anyone share their approach for G? I saw G started getting accepted solutions much before E and F started getting accepted.

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

    Make a flow network and represent each edge as a vertex. Connect each "edge" to the source with capcacity the weight of the edge. Connect every vertex V of the graph to the sink with capacity a[V]. Finally connect each "edge" with the 2 vertices it connects with capacity Infinity. The answer is sum of weights of all edges — min cut in this network.

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

    yeah tricky with false test explaining

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

Is Dinic's algorithm enough for Problem G? It seems that the complexity is something like O(n3).

By the way, I got accepted with Dinic's after I got accepted with Ford-Fulkerson. Would someone tell me which submission the system will use to judge?

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

    The last submission will be judged

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

    If the first passes it will be considered. Else the second

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

    The earliest submitted solution to get AC on systests will be considered.

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

      That's sounds reasonable. Moreover, if the first one failed the systests while the second one passed, will I get penalty for the first one?

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

      That's odd though. On "normal" codeforces rounds, only the LAST submission to pass the pretests in judged on systests and that one submission will matter towards your score.

      How come it's different for "educational" rounds?

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

        Educational system is a modification to icpc system, not the cf one. Over there all the submissions after AC don't count, the same is here.

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

How to solve D?

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

    Fix the two vertices with lowest a as the ends of the diameter. Put all vertices with a >= 2 between them. Then check if you can put the remaining vertices (they have degree 1) on them.

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

    First, if sum(a)<2*(n-1) then you can't build a connected graph at all. Otherwise you need to build a tree that is maximally close to just a path. My approach was like this: first, build a path from vertices with degree 2+, then add a vertex with degree 1 (if there are any) to the first and last vertices of that path. Add other leaves anywhere respecting degree constraints.

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

Will I get a penalty if I hack unsuccessfully?

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

    No.

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

      And what if I hack successfully? Will I get a extra bonus or only the one who is hacked will lose his "accepted"?

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

        You can indirectly get an extra bonus: if you hack someone that is higher than you in standings and he falls below you, you get a better position in final standings and a bit more rank.

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

          Many thanks~ However, I think I should go to bed now because it is already 1: 30 in China now...

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

          Would that really matter though? There will be system test to eliminate those wrong answers if nobody hacked them anyway right?

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

            In Educational rounds the systest consists of the hack inputs used during the open hacking phase. If the input needed to hack the code is very specific, it's possible that it passes the other hacking inputs and thus the systests.

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

              I'm still sort of confused about the Educational rounds. Will there be a system test phase after the open hacking phase? Or the contest just finishes once the open hacking phase finishes?

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

              I see, that makes a lot of sense!

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

      thanks~

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

could anyone please tell me what is this hell -> Diagnostics detected issues [cpp.clang++-diagnose]? only due to this i could not submit my B problem. although my code is working fine on my system.

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

how to solve C??

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

f1e1de2f61dd0f3d85883b478bf0f57f353e0ea7
May God save me.

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

HELP ME PLS!!!

PROBLEM E

This submission 46340090 Wrong answer on test 11,

but on any other compiler 11 test — ok (and on my local machine).

I do not understand why and I think that the problem is in the cf compiler,

help pls.

//11 test//

input:

18 1

3 3 1 3 1 1 3 4 2 2 2 1 2 1 4 1 4 3

ans:

9

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

Can anyone tell me why this code has been blowing up with undefined behaviour on Codefroces servers ?. It works fine on my machine and ideone.com . My Submission

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

what can be the hacking input in problem B

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

    100 GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG

    169 GSGSGSGGSGSSSGSSGSGGGSGGGSSSGGSGSSSSSGGGGSSSSGGGSSGSGGSGGSGGSSGGGGSSGSSGSSSGSGGSSGGSSGGSSGSGSSGSSSSSSGSGSSGSSSGGSGSGGSSSSGSGGSGSSSSGSGGSSGGGSGGSGGSSSSGSSGSSSSSGGGGGGGSGS

    123 GSSSSGGGSSSGSGGSGGSGGGGGGSGSGGSGSGGGGGGGSSGGSGGGGSGGSGSSSSSSGGGSGGGGGGGSGGGSSGSSSGGGGSGGGSSGSSGSSGSSGGSGGSGSSSSGSSGGGGGGSSS

    183 GSSSSGGSSGSGSSGGGGGSGSSGGGSSSSGGGSSSGSGSSSSGSGGSGSGSGGSGGGSSSGSGSGSSSGSGSGSGGSGSGGGGGSSGSGGGGSGGGGSSGGGSSSGSGGGSGGSSSGSGSSSSSSSSSSGSSGSGSSGGSGSSSGGGSGSGSGSGSSSSGGGSGSGGGGGSGSSSSSGGSSG

    1000 SSGGSGSGSSSGSGSGSGSSGGSGSGGSSGSGGGSSSSGGSGSSSGSSSSSGGGSGSGSSSSGSGGSGGGSSSGSSSSGSSGSSSSGSSGGSGSSSSSSGGSGGGSSGSGSGSSGGSSGSSSGGGGSGSSSGSSGSSGGSSGGSGSGSGGSGGGSSGSGGSSSGSGGSSSSSSSGGSSGGGSSGGGGSGGGSGSGGGSGSSGSSGGSSSGGGGSSGGSGSGGSSGGGSGSSSGGSGSSGSSSSGSSSGSSSGGSGSSSSGSGGSSSGSSSGSSGSGGSSSSSGGGGGGGSSSGSSGSGGSGSGGGGSGGGGSGSGSGGGGGSGSSGGSSSSGGGSSSGGSSSSGGGSSSGGGGSGGGSGGGSSSGGSSSSSSSSGGGGSSGGGSSGSGGGGSGGSGSGGSGGSGGSGSGGSSSSGSGGSSSGGSSGGGSSGGGSGSSSSGGGSGGGSSSSSSGGSGGGSGGSGSSSSSSGGGSGSGSSGSSGGGGGGSGGGSGSGGSGGSSGGSSSGGSSGGSSSGSGGGGSGSGSSGSGSSSGGGGSSSGGGGSGSSGGGSGSSSGSSGSSGSGSGGGGGSGSGGGGGSSSSGSGSGGSSGSSSGSGSGGGGSGSGGGSGGSSGSGGSSGSSGSSSGGGSSSSSSSGGSGSGGSSSGGSSSSSGGSSSGGSSGSSGGSSGGGSGGGGGSGGGGGSSGSSSGGSGGGSSGGGSSSGGGSSGGGSGSGGGGSSGGSSSGSGSGSGGSSGGGGGSGGGGSGGSGGGSGGSGGGGGSSSSGGSSGGSSSSGGGSGSGSSGGSSSSGGSSSSGGSGSGGSSGSGSSSSSSSGGGGGGSGGSGGGSSSGGSGGGGSSSSSSSGGGSSGGSSSGGGSGGGSGGSSSGGSGGGGSSSGSSSGGSGSGSSGSGGGSGGGGSGSSSSSSSGSGSGSSSSSGSGGSSSSSGGGSGGSGGSSSGSGGSGSSGSGGGSGGSSGSGSSSSSSGSSGGSSGSGGGSGSSSGGGGGGGGGGGGGG

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

Another HackerForces contest!!!

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

Hello! idk if this is intended but I found out I could submit for practice before contest ended, this seemed really cool however when I get wrong answer I can see the test data!!! which means I can hack any code I want that gives Wrong Answer, is this the intention for the educational CF?

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

46340916

Why does Binarysearch WA for C?

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

For problem C I wrote code in c++ in ideone it ran for sample test cases well.But on submitting it is giving runtime error with "Exit Code is -1073741819" for the very first test case I don't know what the exit code means? Can anyone explain why and when that exit code occurs?

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

finally I still can't hack this 1965ms O(n^2) 46324307

50000*50000 just cost 2s.. amazing...

but I hacked another solution with java : 46336111

but in fact this solution's time cost is about 2400ms

so this tells us drop java and pick c++ now

just joking XD

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

Intended solution for F? I can only bound my solution with , where S is the sum of lengths of all strings (that also may be slightly wrong, to the better or worse), but the constant is incredibly low and I can't come up with a worstcase. It passed with 233ms or so.

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

    (I will use N to denote size of a trie)

    Don't know about intended; I did following DP: [subtree that we have to solve (N)][Depth of the first taken vertex on path from subtree root to the overall root(N)][how many vertices do we want to take in this subtree(K)]. So I have N * N * K states, and in order to solve the state I'm running knapsack over all sons of the vertex. Adding up those knapsacks for all vertices, we'll get N * K * K over whole tree (each vertex is a son of exactly one other vertex, and it will be considered in K * K possible transitions in knapsack), plus we have to run it N * K times for all possible combinations on two other dimensions of DP, which leads to the bound of N2 * K3 with a really low constant.

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

hi there i have a problem. recently, i got a message that said your round is going to be skipped. bu at the end, it said that if you think there is a problem, you can send a message here. i was getting +98 from this contest, so i think there was no reason to skip this round by my self. thanks.

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

When will tutorial be available?

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

python 6-lines AC solution to problem B

_, string = raw_input(), raw_input()
start, end, res = 0, 0, 0
for char in string:
    if char == "G": start += 1
    else: end, start = start, 0
    res = max(res, start + end + 1)
print min(res, string.count("G"))

https://codeforces.com/blog/entry/60059 for more

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

Где топ участников и топ взломщиков?

Ждем...

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

    Завтра ближе к обеду будет, из поезда что-то не получается сгенерировать

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

I tried to solve problem C with Binary Search but failed.. whats wrong with my algorithm? thx :)

here is my submission 46606310

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

I think there's some bug in the checker of problem D (Test case number 18). Diameter of the following code matches with the answer diameter, but it is still giving wrong answer with the comment " Given diameter is incorrect 388 389"

https://codeforces.com/contest/1082/submission/46993586

Please look into it. Thanks in advance.