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

Привет, Codeforces!

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

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

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

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

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

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

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

Место Участник Задач решено Штраф
1 Anadi 7 266
2 HIR180 6 129
3 mrscherry 6 152
4 Vergara 6 158
5 Jeel_Vaishnav 6 185

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

Место Участник Число взломов
1 teapotd 100:-4
2 vlad.raw 52:-5
3 MarcosK 32
4 tataky 28:-5
5 knotValid 23
Было сделано 721 успешных и 668 неудачных взломов.

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

Задача Участник Штраф
A Dalgerok 0:01
B Nazikk 0:03
C neal 0:03
D tamref 0:14
E shadowatyy 0:13
F killer_god 0:34
G lxrvelory 1:03

UPD: В задаче D обнаружена серьёзная ошибка, из-за которой некоторые некорректные решения могут приниматься как корректные. Мы исследуем количество пользователей, чьи решения были оценены неправильно, и работаем над исправлением чекера. Приносим извинения за эту ошибку. Решение о рейтинговости раунда будет опубликовано позже.

UPD2: После обсуждения проблемы мы пришли к следующему решению:

Те, кто сначала получил AC, а потом WA, не подвергнутся изменению рейтинга. Для всех остальных (те, кто получили правильный вердикт) контест будет рейтинговым.

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

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

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

2 hours for 7 problems seem to be too less. Any chance extending the time to 2.30 hours? Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems. C'mon beloved Codeforces! Give a thought.. :)

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

    "Specially for Educational Round, which should focus on having participants with low-mid ratings attempt more problems".

    Not really that's what Div. 3 rounds are for.

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

      Div3 rounds (both frequency and problem difficulty level) are inconsistent, Edu Rounds are still the best way to get introduced with ideas that can be used in broader extent.

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

    Most of the div2 people solve at most 5 of them anyway. Having 2h for 7 problems is good enough, since it gives a challenge for the better contestants too

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

      I'm saying just for education rounds though, the idea is to Educate, so why not give an extra half an hour?! That will surely benefit lots of programmers like me who are not yet to the level but trying to attempt and solve more problems than they usually do. There're lots of other div2 rounds where better contestants can be challenged by 2 hours time limit.

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

        Pretty sure the meaning of "Educational" rounds was lost a long time ago.

        Back when they started, educational rounds had classic problems which highlighted ideas and techniques that contestans should learn.

        Nowadays they are just normal contests with different rules ¯\_(ツ)_/¯

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

    that's a good idea but maybe 2 hours make us want to try faster .. for me at my best I would solve 3 problems in less than 2 hours so it won't make that difference but it could for others so I agree with you

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

Hoping to get some plus ratings in this round :p

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

Раунды awoo и команды — единственное, что может скрасить серый понедельник, спасибо

upd. топ-10 пранков, вышедших из под контроля

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

Lower, or lower and equal to 2100?

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

Hi, guys, is it rated for me too?

I am participating after a long time and I have heard that some changes have been done in the divisions — div1,2 and 3. What are the rating ranges in these divisions and will my rating be affected if I participate in this contest? Thank you.

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

An Educational round after several bad contests, time to get new high rating.

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

69 ( ͡° ͜ʖ ͡°)

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

what is test 5 on E???????????????????

Why can't we see the test cases?

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

Why in E d can be>n?

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

There was an error in problem D which caused some incorrect solutions to get accepted. We will investigate the number of users who were affected by this issue and decide whether the round is rated.

I am really sorry :( Both bugs (in D and G) were mine.

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

i submit code for problem D with just cout << 0 << endl; and get AC but good vertices in my code ans simple test 1 are different why??

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

NO!!! Plz be rated!!!! It's my first time to be MASTER!!! :(

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

Please don't unrate this contest.

Could we rejudge problem D or some accepted incorrect solutions?

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

    I don't think so...

    I myself didn't solve D, but there might be some guys with little bugs, who would have solved this problem after getting WA.

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

      How does correct checker guarantee that you will get WA for the little bug? The little bug is the most common reason for hacking

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

        It mustn't be that little you're thinking...

        Not everyone solve problem D in on try. But getting AC in pretest means don't working on it anymore.

        And the pretests was really weak, the guy posted above (alireza_kaviani) got AC with outputing only 0.

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

Spoiler Alert:

In D, is it true to:

1- Find MST.

2- If n  -  1  <  =  k then we have reached the answer, otherwise, erase edges starting from leaves until the number of remaining edges equals k.

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

    I think it needs to be tree that grants minimum distances from the node 1 (like, dijkstra-tree)

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

    Shouldn't it be shortest path tree rather than MST?

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

    Apply Dijkstra from source 1. Get tree with n-1 edges. Start removing leaves edges from that tree. Too bad I had a small bug in Dijkstra and could not submit on time.

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

      @MatPhySC what if # of edges in optimal paths is greather than K, dijkstra tree should answer less edges than the solution

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

        If I understood your question correctly than if K >= N-1 then answer will be Dijkstra tree because all vertices are good

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

          Sorry, poor english, but what i mean is that even when all vertices in Dijkstra tree are good, there could be another ones that belong to some other Dijkstra tree and they are also good edges

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

          consider this case: 3 3 3 1 2 2 1 3 1 2 3 1

          if i understood your solution, it should give 2 1 2

          however, 3rd edge is also good, at least the way i get the problem

          UD: i got it now, it's good vertices, not good edges

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

    Wrong solution:

    Consider the following case - 3 3 2 1 2 2 2 3 2 1 3 3

    Answer is — 2 1 3

    Answer from MST - 2 1 2

    Minimum distance from 1 to 3 is 3 units. MST gives 4 units distance from 1 to 3, so 3 is no more a good vertex.

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

    This will fail. Consider this tree. 1 2 1 1 3 1 1 4 1 2 4 1 There are multiple MST. But taking any MST other then 1,2,3rd edges. Will give WA.

    MST does not guarantee that all edges are at the minimum distance from vertex 1.

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

    Thank you all!.

    Beautiful problem BTW :D

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

    I don't think MST works. I got AC on this problem with SPT(shortest path tree). and maximum number of good vertices is min(n-1, k).

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

What is test 3 in D?

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

First time I wrote a buggy segment tree. :(

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

when I wondering how this guy passed D in 31 ms  lol, lmao

I bet a lot of contestant will fail on D :|

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

I am sorry to be saying this but in my opinion it would be extremely unfair to declare this round as unrated because there would be many people who might not have done 'D' and have performed well in today's contest. If some incorrect solutions were accepted then it may as well be considered as a case of weak test cases. I urge you to consider the plight of many like me who believed they did well in today's contest and would be stranded disappointed if it is made unrated. PS Edit1: To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.

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

    feel about those coders who cannot improve his D solution to get actual AC solution. because of he/she already get AC.

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

      I can understand that but that's also the case in many contests when your pretests get passed and your main tests fail. I understand that either decision would be unfair to some but it comes down to which one is more on the fairer side. It comes down to 1 question vs 1 contest and I believe that making it unrated would be more unfair.

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

        My solution on D is actually failing on pretest 2 but during contest it passed Now consider if the checker was correct i would have checked my code again and solved it after getting a WA.

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

    To all those who down voted this I am sorry to have hurt your feelings. I do respect your opinion and I totally accept that either of the scenarios I suggested would have been unfair. But the final decision taken by the contest makers is fair in everyone's eyes and no one loses out so I believe it is for the best.

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

make it unrated omfg !!

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

    thats what you wont say when you did a heck good job today (or at least you think so). and the guys who got a crappy AC for that problem will get their ratings back to what they should have in the next contest or two ei?

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

    you didn't submit any solution for D lol

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

When will we know if our submission for D is correct or not?

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

Why can't simple dfs + 2 multiset pass problem E?

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

    I passed with a simple DFS and a vector of maps.

    Perhaps you got some bugs? Personally I wasted 30 minutes for not realizing I overwrote queries instead of accumulating those lol.

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

    Mine passaed 45632893 (After the contest and the code is probably bad)

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

rated plz!

Just fix the problem(s) of specialjudge.

And those best hackers will get everything done. ;)

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

In system test, the code that pretest is passed can be wrong, naturally. I think there is no reason that this round will be unrated. Moreover, this round is educational round and hacking can't be attempted in the contest. So this round wasn't influenced by something wrong.

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

    If our solution failed on pretests we will have time to make that solution correct. But now we can't do anything. So if round gets rated it will be unfair for all participants whose solution failed on D because of bug in checker. So round should be unrated.

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

      if your solution is this:  then you obviously know your solution is wrong.

      and if its something different, how is it different then having very easy pretests if it passes sample correctly?

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

        My solution is not even close to this. And we can't assume all 36/37 pretests are like samples (in running contest).

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

      Same would be the case when pretests are weak. but we don't make it unrated in that case.

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

If it is little amount of people of whom they were affected, I think the round should be rated, because nothing bad as participating and then get, 0 rating changes :D

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

Let's hit the unrated button.

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

PikMike said this in Discord server...

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

It seems that the special judge of problem D is incorrect. So I'm thinking about something like ummmmm.. unrated? In fact, I just wanna complain about the awful quality. Please check your contest more carefully.

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

Let's make it unrated

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

Ппц лажанклись :)

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

Я считаю контест должен быть рейтинговым , так как человек осознанно отправлял свое решение . Я не думаю что человек , который отправил cout << 0 ; и затем не написал адекватное решение , решил бы эту задачу .

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

    Но кто — то просто набагал в реализации, а престесты это не выявили

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

I feel that the contest should not be rated. Any opinions?

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

please make it unrated

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

I'm wondering why my bruteforce solution on problem E could get Accepted... Can anyone explain why?

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

    Don't worry fam, it's no longer accepted now :)

    The answer to "why" it was accepted before is because pretests are never perfect.

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

Принципе те кто норм решали д так ее и решили так что можно делать рейт

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

Please keep it rated !!

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

please rated

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

So many people wanting the contest to be unrated are people who just did bad, not people who were affected by D.

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

OK ,The contest must be UNRATED!! ;)

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

I solved problems A, B, C, D and F. I was really happy with my results and now my D got wrong answer on test 1 (after the contest). I have A, B, C, F problems accepted, which worth less than A, B, C, D because solving A, B, C, D is faster than solving A, B, C, F. A similar problem was at round 485 (the queue froze during the contest): http://codeforces.com/contest/987 I lost 166 rating points there, I can't believe this is happening again. Instead of gaining points, I will lose :( Please make it unrated.

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

    If you got wa on even sample who is to blame really?

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

      I never check the 1st example, I don't get penalty if I get WA on test 1. And why would I check after it got AC?

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

please rated

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

I messed up, got stock on C god please make this unrated

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

Am feeling kinda stupid.... Anyways how to solve E ?

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

    Whenever you enter or exit any node, update BIT. I got that idea but implemented it with set instead of BIT during contest.

    solution: http://codeforces.com/contest/1076/submission/45630591

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

    You can do a simple DFS throughout the entire tree, starting at node 1 (i.e. root).

    Before starting, let's denote accumulated as an integer storing the sum of all added values for the current node. We'll get on with the way it worked below.

    When we start traversing from node z with depth depth, we'll do all these things:

    • Taken all queries that have z as subtree root, and add the x values of all those queries into accumulated.
    • Obviously, these queries don't apply for the entire subtree of z (only those with distance not larger than d). Therefore, we'll use a global array deactivated[] (more info in next steps). For each query with maximum depth allowed of d, add x into deactivated[depth+d+1]. Of course, since d ≤ 109, if depth+d+1 surpasses the maximum depth of the entire tree, ignore it.
    • As a result, we'll have to subtract queries from ascendants' query that no longer affect the current node. To do this, we simply subtract deactivated[depth] from accumulated.

    Then, accumulated will be the answer for vertex z. Store it and start running DFS like usual. When done traversing, remember to undo all the above steps before leaving the function.

    My submission, for further clarity: 45624305

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

We discussed the issue and came up with the following decision:

Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated.

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

    very well

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

      Please make it rated for those who use cout << 0

      It is clear that someone might get lucky enough to try it and get AC

      But it does not makes sense that many people were able to do it.

      It is clear that they clearly discussed the hack among themselves.

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

    Can you explain what was the issue clearly? Incase if the WA was on hidden pretest then maybe next time make it unrated for everyone having WA after final system tests too in all rounds?

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

      For some solutions in problem D that should be rejected the checking program answered that they are accepted.

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

      The checker wasn't correct,

      It outputs ac if you just printed less than or equal to K distinct numbers from what i understand(even if you print 0).

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

    What about the people who are getting +ve rating change even after being affected by WA in D? It doesn't make sense to make it unrated for them.

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

    Make it like those who got accepted earlier and get WA now won't be affected by rating changes if their delta is negative. P.S. My delta shows positive by predictor

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

    Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!

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

    Why different decisions for similar problem that happened in educational round 51?

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

    You should take the "unrated" users out of the rating pool entirely (i.e. make them unofficial). Rating deltas are comparative: if somebody gains rating, someone else is supposed to lose it. If you just make the users not affected by rating changes, you'll have some users who influence the ratings of others but don't get their ratings influenced themselves.

    I hope what I'm saying makes sense, I don't really know how to express my idea.

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

D-Forces

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

It's my first chance to become master, I'd like to see it rated, but if the wrong make the contest unfair seriously, it should be unrated.

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

Can someone explain to me what I messed up?

http://codeforces.com/contest/1076/submission/45631931

It's just a dfs + 2 multisets. I must have looked over this more than 20 times. (I also put the updates to active/spent before and after the recursion, but that didn't do anything.)

Thanks in advance.

nvm solved, made stupid bug

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

Can someone explain me why this solution for problem A will fail ? http://codeforces.com/contest/1076/submission/45621631

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

    3 baz

    Your answer is ba when my answer is az.

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

    Deleting biggest one is not the solution check it 5 abcad

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

    Consider this case:

    3 bac

    Your code output "ba", while the correct answer is "ac".

    So, what you have to do is not removing the largest char in the string, instead you have to remove the first char s[i] such that s[i]>s[i+1], as this will result in smaller string.

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

Can someone explain me why I'm wrong? I made a submission to count number of good vertexes and with 50000 edges, one can't have more than 50001 good vertexes.

45607996 // the original one, from the contest 45632353 // the modified one

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

    The edges you give aren't necessarily connected. So you could have tree fragments everywhere. You have to do a dfs to get the edges and make sure they can actually reach the 1 node. (I might be wrong.)

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

      I'm using Dijkstra starting from vertex 1, so the graph is connected for sure

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

I submitted problem D 3 times.

In the second time, I get AC but the system said WA.

When rejudge, My second submission is changed (it exactly the same solution of prolem A). I think this is a bug of Codeforecs. Could you consider my case?

Submission number: 45627317

Before rejudge, WA on test case 3.

After rejudge, WA on test case 1, and the code is totally changed :( why ?

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

is your standing in the leaderboard affected by how many accomplished hacks do you have?

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

Please don't unrated, I probably become specialist after this round TAT.

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

    Looked at your code — if you use the cin/cout speedup for C++, never mix them with printf/scanf — the streams are desynchronized so the output may not come out in the same order as you expect it to. That's what is happening here.

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

    You should look up what things do before you use them :)

    That #define timesave ios_base::sync_with_stdio(false); cin.tie(0);, isn't some magic fairy dust that you just sprinkle over your program to make it faster. It has some effects.

    To be more specific, ios_base::sync_with_stdio(false) means (as the name suggests) that you are disabling syncing between io with streams (the kind you do with cin and cout) and standard io (the kind you do with scanf, printf etc). You disable the sync, yet in your code you use both methods of io (you use cout for the "No" case and printf for other cases) and then expect them to be synced up.

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

Why “Those who got accepted earlier and get WA now won't be affected by rating changes” ? Why don’t we consider those are Accepted at the time it’s correct and ignore all submissons after that? This contest’s rule is ACM/ICPC, right? In ACM, it’s also rejudge as the way I mentioned. There is no ACM/ICPC contest skip a Accepted submission to judge final submisson in this case!

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

    The thing is that people could check their source once more if they knew that's wrong, but everyone usually stops at the AC verdict

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

    He meant, "those who got accepted due to the bug, and the same submissions got WA after rejudging".

    And for that, it's certain enough to say why it should be unrated (at least) for them.

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

      Thanks, bro. I know his mean now.

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

      Isn't is unfair to those who are getting positive delta but it will be unrated for them.

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

      Can you please proof the problem C ?

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

        It's a pure mathematical problem.

        According to the given formula, we can figure out , thus .

        You can draw the graph of the equation , and figure out a few things:

        • If d = 0, obviously a = b = 0.
        • If d < 4, no solution can be found.
        • If d ≥ 4, the function d = f(a) is a monotone function. Thus, you can binary search the value a, and b can simply be obtained as d - a. Keep in mind that your precision has to be right to fit the output's relative/maximum error criteria.
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

          For the last case (d ≥ 4) no need for binary search, instead, solve the equation which is actually a2 - d * a + d = 0. After that, b = d - a.

          Simple.

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

            I feel freaking odd to deny solving this simple quadratic equation and binary searching the answer during contest time :D

            Well, whatever that works :D

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

Те, кто сначала получил AC, а потом WA, не подвергнутся изменению рейтинга. Для всех остальных (те, кто получили правильный вердикт) контест будет рейтинговым. Здравствуйте, но по моему мнению делать раунд не рейтинговым для тех у кого + рейтинг как то неправильно, я бы пересмотрел решение с вашей стороны.

Hello, but in my opinion, to make the round not rated for those who have + rating as something wrong, I would reconsider the decision on your part.

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

if i did't got accepted, my rank will up. and now my rank won't up. sad :'(

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

if i did't got accepted, my rank will up. and now my rank won't up. sad :'(

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

And persons that haven't try the quest D? Is unrated or rated?

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

Yo yo dudes, come on, the ones who got affected should have their rating increased if it shows +, and nothing if it shows -.

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

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

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

just another [partial unrated educational round rated for div 2]

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

I got AC earlier and got WA now. But despite that, can I still get rated since CF-Predictor seems to indicate I will still get a positive rating increase.

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

If I got D accepted with a wrong solution, but still managed to gain some rating after my D got WA, I do not see the point of why my rating should't increase.

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

How to solve C?

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

I spent a lot of time for D problem. And i have a nice score . Why my contest won't be rated. I don't do

printf(0);

I do bfs but my solution get wrong answer after rejudge. Please help me!!!.

It is not fair.

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

    You are so right. Why do you ban from contest. Don't accept question but it should be rated for all.

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

Can anybody proof me B problem, pleace

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

    If n is even, then the smallest prime divisor is 2. After subtracting 2 from it, n is still even, so the smallest prime divisor will keep being 2. Therefore, the answer is how many times you can subtract 2 from n, which is n / 2.

    If n isn't even, find the smallest prime divisor d. You do one subtraction and get to n — d. Now, d is most certainly odd, therefore n — d is even, so the answer for n — d (as described above) is (n — d) / 2. Counting the subtraction of d from the start, the total answer is (n — d) / 2 + 1.

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

"Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated."

Please make this only for those who are getting negative rating changes.

Making this unrated for those who are getting positive rating changes even with WA on D is unfair.

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

"Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated."

This is unfair for the users with positive rating changes even with WA on D. Please see if there is an alternate solution for this issue.

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

Atleast make it rated for those getting +ve rating change, no matter if they were affected by D or not.

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

this contest should be rated for all those who got correct the 4th one but failed later..but still are getting their ratings better than before and unrated for the ones whose ratings would be decreased due to the 4th question.

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

Can anyone tell me how to solve problem D ?

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

    run dijkstra from vertex 1 to all other ones

    that gives you a tree of shortest paths

    all you need to do is remove leaf by leaf untill you have k+1 vertices (and k edges)

    it clearly maximizes the number of 'good vertices' and is always valid as well

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

Can anyone gives me a hint on problem E?

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

Can anybody please proof the problem C mathmatically. It would be greatly appriciated. Thanks :)

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • Consider a * b = a + b = d

    • we can get 2 equations for a , a = (a+b) / b = d / b and a = (a * b) — b = d-b

    • d / b = (d — b) -> b^2 — bd + d = 0

    so , we can use quadratic equation to get b , then a = d/b But if there is no valid answer from quadratic equation then answer is N

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

    We know:

    1) (a + b) ^ 2 = (a ^ 2) + (b ^ 2) + 2 * a * b

    2) (a — b) ^ 2 = (a ^ 2) + (b ^ 2) — 2 * a * b

    So we can calculate (a — b) ^ 2 as follows:

    1) (a — b) ^ 2 = (a + b) ^ 2 — 4 * a * b

    We know also that a + b = d & a * b = d.

    let A = d ^ 2 — 4 * a * d

    So we have (a — b) ^ 2 = A

    Now, in order for the problem to have answer, A must be positive. In case where A is negative simply output 'N'. In case it is positive, find it's square root and name it c.

    now we have to equations:

    1) a + b = d

    2) a — b = c

    So a = (d + c) / 2 & b = d — a

    After calculating the values for a & b check them. The problem wants a & b to be non-negative real numbers. So if either of them is negative then output 'N' and else output the numbers.

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

    By Vieta's formulas, we know that the sum of roots of the second degree polynomial ax2 + bx + c is equal to while their product is equal to . So if such numbers exist they will be roots of the polynomial x2 - dx + d.

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

why exactly did people try to submit solutions with cout << 0 anyway?

that feels just odd to me

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

Can someone please explain me why my answer is wrong for problem A in the shown test case? Input 1000 rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgurflfvnersfqkwnsmsh...............

Participant's output rkqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqavgqwbwkiwypcxclzhskvrjdxrgbanlngwymdlmgu................

Jury's answer kqggsabguejnkvqhflwqtndjqakicbgcirayhvustungfyjrvgvxdcpwaoyqmqrorxfjlmvqazvgqwbwkiwypcxclzhskvrjdxrgbanlngw..................

(why is 'r' being cut instead of 'z'?)

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

    Consider the simpler case:

    3
    bac 
    

    Output: ac

    Your code's output: ba

    You should delete the first character s[i] such as s[i] > s[i+1], not the largest character

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

Can anyone make me understand solution of D. Had a terrible round.

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

    My solution is based on dijkstra's algorithm from vertex 1. So while we're running dijkstra , i just pick the first K node(that is not 1) that we visit by dijkstra , if we were about to exceed K just break the loop. (FYI my dijkstra is implemented in a while loop with a priority_queue as the main data structure , you can see the submission from my profile.)

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

    Actually Dijkstra process built a shortest-path tree with N vertices from the graph. So we will build that tree, and repeat this N — k — 1 times: Find a vertex that is a leaf and delete it. This process make sure all the current vertex of the tree has as same shortest distance from vertex 1 as it was before the deletion, and the number of these vertices is largest. This can be done with dfs

    You can make the deletion simpler, by dfs the shortest-path tree and build a subtree of k edges. Here is my submission 45633192.

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

How to solve problem G ?

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

Was the contest unrated for all..as my rating has not been increased.

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

So we have just eliminated everyone affected by D... what?? This is just so stupid. Someone who has done E or F and whose rating might be +100 would be unfair for them!! Make it rated for those with +ve rating change please.

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

" Those who got accepted earlier and get WA now won't be affected by rating changes. For everyone else (for those who got correct verdict) the contest will be rated. " — What if the those contestants will get a higher rating if we skip D submissions of those users?

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

Эм, у меня упала D из-за Вашего бага. Но я хочу, чтобы у меня изменился рейтинг... Эм...

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

My rating still hasn't changed, is everything fine? I haven't touched D at all.

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

deleted

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

For those who got TLE on test 64 on D: When implementing Dijkstra, do not check edges from a vertex if it is already visited (in other words, if the distance from the PQ is greater than the one written in the distance array). A vertex can be pushed into the PQ O(V) times and it also can have O(V) outgoing edges, so it can be O(V^2) in the worst case. Furthermore, this can be repeated for multiple vertices and possibly reach O(V^3) in a complete graph.

The generator is:

#include <cstdio>
using namespace std;

int main()
{
	int n = 200003, m = 300000, k = 0;
	printf("%d %d %d\n", n, m, k);
	for (int i = 2; i <= 100000; i++)
		printf("%d %d %d\n", 1, i, i);
	for (int i = 2; i <= 100000; i++)
		printf("%d %d %d\n", i, 100001, (int)1e9 - 2 * i);
	for (int i = 0; i < 100002; i++)
		printf("%d %d %d\n", 100001, 100002 + i, (int)1e9);
}
»
5 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

This is unfair to me. Predictor was showing I will get +50 rating. But now this became unrated for me. This is unfair...ummmmmmmmm

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

Is there a way to look up what test was used to hack my solution, in case I want to debug?

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

Is there editorial?

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

Будет ли опубликован разбор?

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

For E is it possible to build some type of tour so that we can use segtree for range update and then push all the changes?

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

i was wondering how setters managed to change the rating based on a particular problem's verdict... is it a database sort or ??

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

Why TLE on Test Case 64? problem D

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

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

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

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

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

Спасибо за контест.

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

I think in "Meme Problem(C)" float and double will give different answers. Both the answers shall be considered valid since logic is same. If programmer is able to give any one of them it implies his/her logic is sound.