Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

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

Раунд 1 VK Cup 2018 пройдет 10-го марта в 18:35 MSK (время в вашем часовом поясе). Соревнование "VK Cup 2018 — Раунд 1" предназначено для команд, прошедших из двух Квалификационных раундов. Лучшие 400 команд пройдут в раунд 2, вместе с командами, отобранными в Уайлд-кард раунде 1 неделей позже. Как обычно, параллельно пройдут два обычных раунда, по одному для каждого дивизиона, для тех, кто не может принять участие в VK Cup.

Я хотел бы поблагодарить KAN за приведение моих безумных идей к виду законченного набора задач, координацию и идею одной задачи, AlexFetisov, qwerty787788, winger, Errichto, Tommyr7 и misof за тестирование, MikeMirzayanov за платформы Codeforces и Polygon, а также VK за проведение соревнований. Также спасибо arsor за помощь с условиями на русском языке.

Все три раунда будут идти 2 часа, и все являются рейтинговыми. Раунды VK Cup и первого дивизиона будут иметь шесть задач, одинаковые в обоих раундах. Раунд второго дивизиона будет содержать пять задач. Стоимости задач будут объявлены перед раундом.

Главными героями раунда будут Алиса и Боб. Конечно, Ева попытается разрушить их планы.

Это мой первый раунд на Codeforces и, надеюсь, не последний. Желаю вам много посылок, крутых хаков и положительного изменения рейтинга.

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

VK Cup

Div.1

Div.2

Разбор тут.

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

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

" Wish you many submissions, high hacks and successful rating."

I am assuming there will be lot of hacks

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

Будет ли раунд рейтинговым для участников VK cup? Если да, то как будет изменён рейтинг участников команд, где >1 человека?

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

    Раньше всегда пересчитывался, видимо и в этот раз тоже. Каждой команде сопоставляется некий "рейтинг команды", по которому и пересчитывается изменение по обычным правилам.

    UPD. Это даже написано в анонсе Все три раунда будут идти 2 часа, и все являются рейтинговыми.

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

      Я понял, просто хотелось понять, как именно он будет считаться.

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

        http://codeforces.com/blog/entry/16986

        Если коротко, то:

        1. Высчитают рейтинг команды (его кстати можно увидеть в списке зарегистрированных участников)

        2. Рейтинг обоих участников изменится на одинаковую величину в зависимости от занятого места

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

Looking forward to the round)

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

Can the test in English?

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

When and where were the two qualification rounds held for VK Cup Round1 ??

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

The translation of "...Раунды VK Cup и первого дивизиона будут иметь шесть задач, одинаковые в обоих раундах." is somewhat awkward. A better one is: "...The VK Cup and Div. 1 contests share the same six problems while the Div. 2 contest consists of five problems.

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

The main heroes of this round will be Alice and Bob. Beware that Eve might attempt to foil their plans.

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

Hi, im confused with the round announcement, can anybody please answer below 2 questions,

1) Why there are 2 contests (#470, VK Cup) held at the same time ?

2) What does it mean "#470 based on VK Cup 2018 Round 1" ?

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

    '#470' and 'VK Cup' is basically the same.
    Because they'll have the same problems.
    That's why it's called "#470 based on VK Cup 2018 Round 1".
    And you can participate in #470 div.2.

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

Div. 1 will have six "identical" problems :O

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

    Yes, that is true. Solving all six of them is still quite a challenge.

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

(please read the 'for teams' part before downvoting!)

is it rated for teams?

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

What a sad time for Chinese :(

23:35 :(

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

    but i decide to attend the contest,because the contest is one of the most contest of Russian.so we can talk with the more expert students.

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

This is a good time of the contest for Russia. But unfortunately not for everyone.

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

I hope this contest will make me green !

UPD: I am green now :)

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

editorials ?

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

    Perhaps it would be better to publish them after contest, not before.

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

Div-1 will be six problems,but div-2 five problems. I think after five it will be more complex problem that is unsolvable for div-2.

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

Will the problems statements be in English? The registration page is showing me T&C in Russian

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

    No worries, the problems will also be in English. We'll check the registration page, thanks for reporting.

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

[deleted]

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

Will we see tourist tonight? Exciting!

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

I hope this contest will make me green once again...!!!!

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

"Wish you many submissions, high hacks and successful rating."

I wish you successful submissions, high hacks and many rating, too. :)

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

Excuse me, will the contest of Div.1 & 2 be Russian, too? (I know VK Cup Round 1 is only for Russians but what about the parallel Contests?)

UPD: My fault, Answered before: here

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

B > C

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

tourist is in the house!

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

CF-Predictor broke or something?

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

948B

In the second case, let X0 = 8. Alice picks prime 7 and announces X1 = 14 Bob picks prime 5 and announces X2 = 20.

Is the test case wrong?

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

it was a terrible decision to keep thinking about problem B.. I should have tried problem C :(

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

Lol Div2B harder than Div2C/D

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

Really nice problems this round, looking forward to see the tutorial.

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

How to solve div2-B ?

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

    Iterate over X0 and prime P that divides X0 (note that there are at most 7 such primes) Than you form X1. Than iterate over primes that are less than X1 and find X2. If X2 is same as input X2 than X0 is the answer.

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

    I'm not sure if my approach was optimal, but here it is always. First, we can use Sieve of Eratosthenes to quickly compute all the primes strictly smaller than N (our given number). Now, we know the number X2 must have been the result of multiplying a prime. So, for each prime smaller than N that N % i == 0, we can compute a number (N — prime). This number is our lower bound for X1, because if we picked, lets say prime P, in order for the next multiple of prime P to be N we must add 1 to the previous multiple of P. Therefore, our X1 must lie between (N — prime + 1) and N. We can simply try all primes less than N and compute their next multiple bigger or equal than than (N — prime + 1) via binary search. Our answer is then the minimum of (Next_Multiple — Current_Prime + 1), using the same rule to find (N — prime + 1). If Next_Multiple is equal to Current_Prime, then take the minimum of the current answer and Current_Prime.

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

Can anyone share hack for C ?

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

    I hacked 3 Div2C solutions in my room by forcing TLE with the max test of the form

    100000
    1000000000 1000000000... 1000000000
    1 1 1 1 .... 1
    

    Naive solutions fail this case.

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

Как решать D?

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

Original C, never coulda come up with such task.

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

TIL (x-y)%z != x-y%z.

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

Hate the availability of the CF last minutes. We suppose that 80% solutions on problem D are wrong. Test by Petruchcho:

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

Hack test for D?

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

How to solve Div-1 D Picking Strings? I've no clue how to approach this...

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

    Note that you can interchange between Bs and Cs. Also you can convert B to A...AB. However you can never create more As to the right of last B. Combine these facts and you'll see that you just need the count of Bs and Cs and the length of longest suffix that is all As.

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

    B->AC->AAB->AAAC->C

    C->AB->AAC->AAAB->B

    when B ~ C

    A->BB

    B->AB

    AAA->''

    before B we can make A, add 'kill' AAA, so we can make any number of A

    so when we take substring we interested in count of B and count of last A

    and then where some easy cases (you can look in my code, after system testing)

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

      Thanks. I did realize A->BB, B->AB and AAA->'', but did not know how to proceed after that. Is it just some case by case analysis like A can generate even Bs and B can generate odd Bs?

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

Bob isn't smart. Don't be like Bob.

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

I hate problem D. Stupid casework.

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

    Can you explain the solution?

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

      Note that you can interchange between Bs and Cs. Also you can convert B to A...AB. However you can never create more As to the right of last B. Combine these facts and you'll see that you just need the count of Bs and Cs and the length of longest suffix that is all As.

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

      firstly you can convert B to C and viceversa. Now (|B|+|C|)%2 is invaraint and also it cannot decrease.If |B|+|C| is same in both,then longest suffix consisting only of A in both should be same length.

      If |B|+|C| is not same.then two cases.
      1.if more A's in first string suffix then it is possible.
      2.If same A's then there should be non B or C in 1st string for it to be possible

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

    Yes, and pretests are checking for random cases. If you're lucky, you will get WA immedeately, if you're unlucky you'll get it after the contest. I think pretests should either check all the cases or almost none of them like in topcoder.

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

      CF would be better off without pretests if they're just random. I can write random tests myself, thankyouverymuch.

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

    Me solving D

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

    It completely ruined my contest :/

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

    I am sorry you feel that way. I am especially not happy that you came back to CF after such a long time and got beaten this way.

    I've read the discussion about the problem D and hacks in general, and I have sympathy for the cries. I fell victim to pretests a few times as well. Most notably, on AIM Tech Round 4, where I got WA on systests because std::random_device was deterministic on MinGW. That night I though I don't have what it takes to be red and would never become one.

    The problem was initially suggested as somewhere between Div1A and Div1B. During testing we realised that some of the cases are really difficult to spot, and hence it navigated all the way to Div1C (I purposefully do not call it D, as the intention was that Div1 has an extra problem at the beginning, not at the end). The idea was to put the main cases in the pretests, but leave the tricky one for systest and or hacks.

    Depending on whether I would notice the tricky case in D myself or not, and was hacked or not, I might have been upset too. It was an unusual problem, but I don't consider it to be a mistake the put the problem in the set.

    Sure, some people took the risk. They locked the problem that evidently had a lot of cases without having a proof that their code is correct. Later they realised that there was a case they didn't cover, either by noticing it in someone else's code, or getting hacked themselves. Risks sometimes don't pay off.

    Some people were lucky to get hacked early enough. Everyone was, however, able to look at the scoreboard 20 minutes before end of contest and see that it is full of hacks. If you have twenty minutes left and are nowhere near finishing E or F, a reasonable strategy is to revisit problem D, perhaps try to come up with a more formal proof or write a brute force solution to compare with.

    I view competitive programming a challenging leisure activity that gives us a balanced mix of two feelings — frustration that I cannot solve a problem, and happiness that I was able to solve one. It's okay to be upset if you do badly, it's okay to be mad at the problemsetter who caused this. You'll do better in next contest.

    Remember that there is also another goal of CP for many people, and that is to prepare themselves for future employment. In the software engineering world, you also have pretests and system tests. The difference is that you sometimes get a wrong answer on systest few years after submission. And the consequences may be much more severe than a few rating points.

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

      but leave the tricky one for systest and or hacks.

      What for? I hate hacks because it depends on your room. For example, some rooms doesn't have any wrong solutions of the problem B, but in some another rooms there are teams who have made 4-6 hacks on it. It's like extra problem for them. I also think that making weak pretests are very bad idea for div1+div2 contests because people from div2 often submit naive solutions and it will make a lot of hacks and disbalance in scorboard.

      If you have twenty minutes left and are nowhere near finishing E or F, a reasonable strategy is to revisit problem D

      Another problems also have weak pretests. I saw how a lot of people passed pretest of problem F and it was very quickly. So I thought it's real to solve it faster than 15 minutes. But it was not true because these solutions were wrong. I tried to solve it and my solution of problem D was hacked 30 seconds before the end of contest.

      I think hacks are the best way for tasks when autor's test can't cover all cases for all solutions(for example tasks with hash), but hacks should not be in every problem.

      on AIM Tech Round 4, where I got WA on systests

      Unfortunately, a lot of rounds on codeforces have weak pretests and a lot of hacks recently. But I think it's not a reason to make weak pretests again and again.

      Anyway, I think problems were intresting and with good pretests this round would be very good. Thank you for the round and I hope next your round will have less hacks.

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

      Hi majk, I completely understand that. I did not mean offence to you. I made that comment out of frustration. Thank you for hosting a contest :)

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

        No offense taken. I'm glad for the discussion!

        Wish you luck in next contests!

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

      Everyone was, however, able to look at the scoreboard 20 minutes before end of contest and see that it is full of hacks.

      It's especially convenient to click on some participant having 6 successful hacks to see which problems he hacked and look at an infinitely loading page with their list. Codeforces hacking system is 20th century artifact. To be honest, I'd send more money to codeforces crowdfunding campaign being guaranteed that hacking system will be rewritten using some modern technologies.

      On the subject: making so much random in the last solvable (ha-ha) task is definitely the best way to ruin the contest. You are saying people can stress test their solutions with a bruteforce — OK, so they should agree that the contest is imbalanced as hell as don't try to solve the last two tasks, which were supposed to arrange participants at the top?

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

        With your first paragraph you're barking up the wrong tree here. To be honest, I've not seen any complaints about the Flash interface. Note that I'm not implying that they don't exist nor am I saying that it is ideal. I'm positive that it's not productive to complain about it on a random post three layers deep in discussion of a random round that intentionally used both of the ways of gaining points to decide the ranking. I have not noticed you saying the above in a more appropriate discussion. Perhaps you would gain more support over there and things could actually happen. I know that I would join the bid.

        Regarding your second paragraph — I already know that some of the tasks were more difficult that they should have been (even though having a task with 3 or fewer correct submissions is not that uncommon) and I will do my best to avoid that situation next time.

        they should agree that the contest is imbalanced as hell as don't try to solve the last two tasks

        No, I am saying I hoped they would adjust their strategy to the circumstances and assess how to act to maximise their score. If on task E you got nowhere 20 minutes prior to the end of contest, it may be a good idea to do something else. Perhaps hack other people.

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

          Answered on PM. On Flash — it's been told many times, nothing happened and nothing is going to.

          About the strategy — I've done exactly what you are saying. But it turned out I'm so stupid that couldn't fix my solution till the end of the contest even having the bruteforce and 20 minutes. I've spent another half an hour after the contest to make it work.

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

      The main problem with D is that most cases are not difficult to spot. It seems like the solution is: reduce it to BC-s followed by A-s, the number of B/C-s monotonically increases by 2-s in operation 1, the number of A-s monotonically decreases by 3-s in operation 4, then check how these operations can affect the other number. This translates to a lot of conditions, but the rules they check can be described very clearly, it doesn't look like case bashing at all if you think and then code, as I did.

      Then there's the special case I missed: a string containing the right number of A-s at the end and no B/C-s, changed to something containing B/C-s.

      Note that I started with D and solved it fairly quickly; failing the first problem I tried cost me quite a lot in score. That E/F were practically unsolvable and I didn't expect there would be many hacks (see above: I didn't see D as casework) didn't help.

      a reasonable strategy is to revisit problem D, perhaps try to come up with a more formal proof or write a brute force solution to compare with

      I had a formal proof shortly after the contest started. The problem is you can miss something no matter how many times you go through the same thought process because, well, it's the same thought process. I had something of a bruteforce (bruter force, O(N2)). Writing a test generator, fully bruteforce solution, stresstesting, finding this bug by picking random cases and fixing it takes a lot of time, probably more than 20 minutes. I sure didn't manage it that fast.

      Some problems have a small element of randomness. Some problems are nasty and have a huge element of randomness, either because you need to think weird to find a solution or because there's something that's very easy to miss. Some problems are geometry. There isn't always a way to do better other than farming luck in advance...

      Anyway, the choice of pretests for F is much worse. If a bogo-algorithm works (bogosort: randomly permute while not sorted) on the first 95 tests, then you should make test 96 one of the pretests or use no pretests. This way, you don't have people making blind submissions.

      The difference is that you sometimes get a wrong answer on systest few years after submission.

      If you can conceal your failure for years, that's pretty damn successful. That's not comparable to systests, but to someone running stresstests for fun and noticing an obscure bug nobody thought about a week after a contest.

      Or you can be sufficiently powerful, in which case you get a taxpayer-funded bailout. But I digress.

      I find my real world experience isn't nearly as harsh as people say. Not in the sense that failure is terminal. "Your submission to a vendor test didn't do well? Here are some statistics, compared to your previous submissions; we're accepting submissions again in a month." "A wild bug has appeared! We should fix it ASAP and get back to what we were doing." The various catches in (not only programming) competitions are unique in that regard. Competitions are harsh compared to ["real world" activity here] and so few people do them precisely because of that harshness.

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

Lol, what a moron I am. In F "while(1) try random permutation" almost works. If I'm not mistaken except for cases where one tree has high degree vertex only. So I fixed case when first tree has it. But didn't notice I need to consider case when second one has it xD.

EDIT: Ok, there is third case when two trees have high degree vertices xD. It seems it is pretty hard. So I was not close, no regret.

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

    'Only 5 minutes left. I can't solve F. I'll just do while(CLOCKS_PER_SEC * 3.8 > clock()) and pray for AC.'

    "Pretest Passed"

    ???

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

Can anyone please help me understanding where this solution for problem div2 D — Perfect Security exceeds Time Limit?

I have implemented trie operations add, remove recursively, inserting indices (so as to remove issue of duplicate values, as java don't have multiset) in trie nodes, and finding index of min value in iterative manner. Complexity of this solution according to me is O(N*logN).

The only reason of TLE i can guess this time is that i used Java. (Have sometimes faced TL issue in past too :( while using Java).

Can anyone please help in pointing out ??

Thanks a lot..

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

    Solutions are not visible at the moment.

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

      Here's the solution

      Also, another implementation with O(Nlog^2N) Complexity (ordered set) here

      Edit: Solutions visible now

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

        You do not actually need the set in a trie node to store the indices, just storing the count is enough. That should speed it up a bit.
        Apart from that I don't see anything else to be improved... of course as you said it may be because of Java itself.

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

          I guess i should leave codeforces until i learn cpp, because today i spent over an hour to code this solution, only to get 2 TLEs, Let alone rating loss (Only gained yesterday).

          Anyways, Thanks a lot.

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

DIV 2C was Lazy Propagation, right?

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

    No i solved it without segment tree.

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

    DIV2C can be solved easily with using Binary Search.

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

    Lazy prop might work, but a priority queue and a variable might do the trick.

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

      cjtoribio, Can you please explain your solution?

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

        WHen you have a set of numbers and you only want to do two operations subtract to ALL, add one element. There is a technique i don't if it has a name but you just use an auxiliary number X and it will be your "floor". When you want to subtract A to all elements just add A to your floor. when you want to add an element B to the set add A+B since B is the value above the floor. For example you have set
        {}, X = 0
        you add 3 to the set (3 + 0)
        { 3 }, X = 0
        then you subtract 1 to all the numbers
        { 3 }, X = 1
        then you add number 4 (4 + X = 5)
        { 3, 5 }, X = 1
        then remove 2 to all
        { 3, 5 }, X = 3 (this array is virtually {0, 2}, which can be seen as A[i]-X)
        so if you want to remove all the numebers that are 0 or less just remove all numbers below the floor. all the remaining numbers are above the floor and you managed to subtract correctly from them. The ones that were removed you only subtract partially since they came under the floor.

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

          cjtoribio, Thanks for taking time in explaining me...
          P.S: Your solution is beautifully coded. :)
          Update1: Is there benefit of using priority queue over multiset?

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

            Honestly multiset does the job quite nicely, but c++ priority_queue is slightly faster, as it uses Fibonaccy Heap, which i have seen is better in practice, and also the code is simpler with pqueue. But i would say use whichever you feel confortable with.

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

    I used binary search and a Fenwick tree with interval updates and queries for element values. I didn't involve any lazy propagation, but did the horrible mistake to miss to change the type of the resulting array to be long[] (not int[]), and that's why I didn't pass the pretests, I think.

    Now I'm waiting for the system test to finish and to resubmit my updated code and if it gets accepted, then I'll declare myself as a total idiot.

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

    I solved it using Binary Search. For each day i, binary search on how many days it can melt 'fully' before it cannot melt temp[j] on the day j. We can binary search on the prefix sums of temp[j] to find this. Then, we can use a sweep-line trick to update ranges in our answer array. Update res[i]++ and res[e + 1]--, which e is the last day the current snow pile can 'fully' melt. But what about the remaining snow? We can just add this to the next day. So lets have another array add[] and update add[e + 1] += (remaining snow). Assuming sum is the current prefix sum of res[] on the i'th day, then the answer for each day is then sum * temp[i] + add[i];

    Keep in mind the case where the amount of snow on day i is less than temp[j]. Then, we can just do add[i] += a[i], where a[i] is the amount of snow built on day i because the pile will never make it past the day it was built on.

    AC Code: 36172821

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

    Calculate prefix sums of T and binary search with each V -> O(N log N) solution.

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

    we can do it using binary search + prefix sums , I don't think Lazy propagation helps here.

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

    I wrote something like partial sums.

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

    i use binary indexed tree + binary search ...

    but just binary Search is enough

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

    ll add = 0; for(int i = 1; i <= n; ++i){ s.insert(add + v[i]); add += t[i]; ll ans = 0; while(!s.empty() && *s.begin() <= add){; ans += *s.begin() - (add - t[i]); s.erase(s.begin()); } ans += (int)s.size() * 1ll * t[i]; printf("%lld ", ans); }

    Here's part of my code, I think it is pretty self-explanatory.

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

    Thanks everybody, interesting to see so many different solutions for this.

    I myself did use Lazy Propagation, which passed in 78ms, so I guess it was a good approach as well anyways.

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

Why i can't open another's solution?

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

Any clue on what was the 4th pretest in div2/C ?

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

Congrats majk for arranging one of the "Anti-tourist" (maybe) contests after so many days!!!

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

    anti tourist ? ?

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

    I think that majk successfully arranged an "Anti-algorithm" contest. This problem had much more emphasis on hacking, case-bashing, constant/log optimizing and not falling prey to weak pretests than any real problem solving. Congrats indeed.

    It's no surprise that tourist would do badly on such a contest. Moreover, strong participants have done very poorly on this contest as well. I can only hope that the next contest is back to normal.

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

I'm feeling kind of bad right now...

2 WAs in C due to typing the wrong variables, and cannot submit D (which I believe will pass the system test) in time because of the same type of mistakes...

Like today is not my day...

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

When I submit for problem B, I clicked the submit button twice, and there are 2 successful submissions.(36156723, 36156724) Because of the resubmission penalty, I got -50 penalty. I thought that there could be no submissions with exactly same code. Can I get my 50 points back? Please fix it.

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

Problem D (Div 2):

"Alice is smart. Be like Alice."

"Alice is smart. Really, be like Alice."

"Bob is not smart. Don't be like Bob."

"Did we mention that Bob isn't smart?"

"Since he is not so smart, he asks for your help."

And while reading the problem, I am like "Okay, I got it. Please stop." (!-_-)

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

    These sentences are useless and make the whole problem long and boring.....

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

I smashed my glasses in a rage after not being able to pass the samples of E after working on it for an hour(possible due to some small issues in my solution)

Codeforces didn't cost me an arm but it cost me my glasses(although it was 100% my fault).

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

    According to a few comments I've seen of yours, you really should control your temper, pal.

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

    You need to learn to fail.

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

    Wait, is that matthew99 overreacting to a Codeforces round? The guy who already posted a few times on Facebook about killing himself due to an unaccepted problem? How unexpected! Seriously, stop crying like a little girl after everything, you ain't the first or the last person to fail a contest.

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

      He didn't smash your glasses, so don't judge him arbitrarily.

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

        Did somebody under the nickname of "2018 find girlfriend" just tell me to SHUT UP AND EAT MY SHIT? This ain't no Minecraft server, cool boy, you can show your creativity without the use of swaggy words like those.

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

      He didn't smash your glasses, so don't judge him arbitrarily.

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

    next time buy a pair of plastic glasses like mine

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

      i got plastic glasses thinking they were harder to break but it didn't help, instead of the glass breaking the frame broke. LOL

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

    It basically feels like you figure out a solution of a problem and you can't code it in time,it feels annoying. But nonetheless,control your temper and learn why you fail.

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

    Honestly, I definitely understand.

    Even if I don't lose rating, I regret doing this contest in the strongest terms possible. There are many contests in Canada that are known for having unnecessary and irritating complications to tasks, but this is significantly worse than any of them. I think the first paragraph of this problem describes it quite well. Although I would much rather have my keyboard stolen than deal with strangely ordered problems, meticulous time limits (on A and C) or the programming equivalent (in terms of messiness and suffering) to coordinate bashing in math, otherwise known as D.

    I feel even worse for the students competing in VK cup, who had even more at stake than simply rating.

    Please let this be a lesson in what not to do when setting a CF contest.

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

    I was stuck in gray for 2 years and still have my glasses.

    just kidding to make you forget the failure

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

Is intended solution for F is random? I hope no...

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

    No. We have an deterministic solution, but intended to let O(N2) pass, as it was difficult enough. None of our random solutions succeeded, but some were able to pass quite a few tests.

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

      Was there some counterexample in pretest for random solutions for F? I think lots of pretest-passed solutions are quite straightforward random solutions.

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

        A tree with one node whose degree is n - 2 and a chain. The expected step is O(n2).

        And this problem can be solved combined with several random solutions.

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

    Can you please tell me what do you mean when you say the intended solution was random?

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

Easier way to do A beside DP + Prime Sieve + Segment Tree? Nearly 100 lines of codes and 30 minutes to code this one.

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

    Let's define the state of the game as (x,p) where x is the current number and p is the prime we used to achieve it. The states from which we might have come here are in the range:(x-p+1,x) and some prime divisor of them. Well, it it is always better to choose the biggest prime divisor(gives you the most possible states) and knowing that, we can just precompute the largest prime div of every number from 1 to X and get a N^0.75 solution.

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

    Let f(N) be the largest prime factor of N. Iterate from N - f(N) + 1 to N and for each composite number x, find the smallest x - f(x) + 1

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

How to solve E? I think, diagonalization is the key, because it is binomial coefficients, and power of diagonalization is easy to calculate. But multiplicating matrix on vector is done in O(N^2), how to optimize it?

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

    It's convolution (plus some multiplicative factors), so FFT is answer.

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

For div2D — Perfect Security

Is the solution through binary trie?. Where you store bits of P in reverse order and for each element of A select the one with minimum XOR in .

Couldn't implement it in time.

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

    Also, can someone share a standard implementation of binary trie? I could only think of implementing it through pointers and doubt, that is what people use in CP.

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

      I use pointers a lot of times, but you might also use a global vector and store the index of the child or -1 if no child in that letter.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      struct Trie
      {
          Trie()
          { 
              next[0] = next[1] = nullptr;
          }
          Trie* next[2];
          //Usefull info
      };
      
      Trie* root = new Trie();
      
    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      There was a greedy solution for this problem.

      See, we wanna find lexicographically smallest message, ryt.

      Formally, you should permute P in such a way that A1^P1 is smallest, A2^P2 is smallest while keeping A1^P1 at its minimum.

      You can prove by induction that the Pi should be selected in such a way that Ai^Pi is minimum. Now, we need a DS which support following operations.

      insert(x) — to insert a value. delete(x) — to remove this value. min(x) — find a value present such that x^val is minimum.

      Now, we will first insert all Pi into this DS, and for every Ai for i from 0 to N-1, ans[i] = min(x), remove ans[i] from this DS.

      Also, forgot to mention: This DS is famously known as Trie ;)

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

        It's correct solution, but it's not greedy. You just wrote definition of lexicographically smallest message.

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

          Why not greedy??

          while moving from start to end, We greedily choose an element which minimize xor for current position, update answer for current position and remove it from set.

          Correct me if I'm wrong.

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

          Yes, I just wrote the definition of lexicographically smallest message in a manner that it directly points to optimal strategy and correct solution of problem. :)

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

Wonder how many people copied their Trie from 706D - Vasiliy's Multiset for the D1 C in this contest :)

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

Tourist's solution fails D. o_o

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

RIP ppppppppppppppp, you trolled yourself.

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

D WA99 <3

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

Am I the only one sick of pretests and hacks? They just make the standings unbalanced. I really admire CSA and Atcoder for dropping them.

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

    What's the point of having different websites if they're going to have similar contest format?

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

    you are not the only one..

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

    Pretests are good, hacks are not good.

    The hacking system is broken beyond belief. It is supposed to be meant for some user to go through and find some obscure bug in some other fellow's code, but it doesn't give nearly enough points (only 100!??!?!). So in most rounds, nobody ever hacks, because the time is better spent elsewhere.

    Then the rounds that actually have hacks are just a load of +4, +8, +11 everywhere because the pretests were insanely weak and someone didn't set the INF high enough or something. Then it's just luck of the people in your room, not skill-based at all.

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

      Hacks inflate the score. About pretests, some casework problems for example would be fitter more for a math contest than for a competitive programming one, but in a math contest you would get at least 6/7 points if you miss a case, here the whole problem...

      I don't see the point in them, for what? To add unpredictability? You can just close the standings 30 minutes until the end for example. Compared to other subjects you have to code your solution here and nobody even care if your solution is correct but the code is buggy, isn't it a disadvantage already?

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

        Judge queue would be insanely long without pretests

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

          It's not a big deal, we can just put the basic fail cases in the beginning, do you often see submissions with WA99 for example?

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

        The biggest reason why I like pretests is because it teaches me to consider every case without being told, "oh, it passed everything". Obviously you would have to consider every case anyway with a direct accepted verdict, but the stakes are higher with pretests, which is a good thing for me.

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

      It depends what you consider to be programming. One of the things I admire the most about full feedback programming is that simple mistakes usually don't cost you much.

      Please don't tell me you believe that someone who doesn't understand the problem at all deserves the same amount of points as someone who used int instead of long long or made an array of 100000 instead of 200000.

      P.S. There are some contests called Trudeau Logic Evaluation on DMOJ that you will enjoy. There are many math, geometry and implementation problems for you to do and only one pretest, which is the sample. Have fun!

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

        Trudeau Logic Evaluation is not as evil as COCI with systest, don't be disingenuous

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

          >Only relative error.

          >needs unsigned long long >MLE on systests

          >Get TLE on systests if you use cin instead of scanf

          >200000 instead of 200001

          >Mod 10^9+9 instead of 10^9+7, pretests don't require you to mod

          >Bounds changed from N=300000 to N=5000 after the contest

          and best of all.....

          >Making test data after the contest and forcing everyone to wait for 2 days before systests.

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

        Trudeau Logic? What is it about, straight white men get -1000 points privilege penalty? If you defeat other contestants, they win?

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

      Generally, I agree with you, but the main reason why I don't like hacks is that it gives a particular advantage for people who were hacked: they have an opportunity to improve their solution, pass system tests and earn at least some points for the problem. Meanwhile, there can be others with exactly same solution who were not so lucky to be hacked, their solution will fail not giving them any points at all.

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

    Since a long time, I have the opinion that the pretest system is un necessarily extremely harsh at times.

    There are situations where I have declared wrong array size, and lost as much as 1600 +  points in multiple contests for it.

    Sometimes, this is not good.

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

Somehow I managed to AC only problem B div2 today

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

Defeat Accepted.

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

hmm, for DIV2 difficult level D < C < B !!!

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

Success rate on F: 0 out of 26, mostly failed on test 96.

Ebin :DDD

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

402nd place... Brutal...

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

In Div1D, why are there so many tests that only consist of As?

36162982

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

I could not solve B and it cost me my first ever (maybe also last) chance to become CM.

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

    Dude, see my graph. You will be like me lmao xD

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

    You might need to slightly reevaluate your priorities. We are in surprisingly similar situations (I solved B in pretests, and if it passed sys tests, I would have become CM, but it didn't and now I am almost exactly the same rating as you, and I have an exam on Monday, so while it isn't Friday, it's similar), but after my performance on this contest, my first thought wasn't disappointment, it was just "My consistency with solving Div2C/D during contest has been increasing a lot; I'll become CM on the next contest".

    Perhaps you have something going on in your life that you can't compete on CF anymore, but if that's the case, the fact that you are not CM is almost completely irrelevant to anything. If you don't have any such thing, then compete again. If you're good enough to get within 10 points of CM, you're surely good enough to do well on a contest again.

    But I would seriously rethink your motivations for doing competitive programming if you are making noticeable sacrifices in other areas of your life. Ask yourself if your end goal for competitive programming will really be more helpful than, say, focusing on your grades, and try to be completely honest with yourself. You may find that doing competitive programming is worth sacrificing grades, but you also might find that the opposite is true.

    Just some friendly advice from someone in a similar situation.

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

      Thanks for your kind and honest opinion. I often say these to other people. But reality is a little different. I do enjoy competitive programming but i know that there will be a time soon in the future when i have to quit and focus on my livelihood. But I wanted to become CM as soon as possible for a different reason (not related to programming). The fact is sometimes you can change a system when you go a higher position. I want to do something like that for my situation.

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

how i get pretests path then got TLE on test 5 which was in pretests there are some people who get time limit on test 5 then got it accepted it was not fair sir

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

Is it just me or are others also getting a penalty for getting WA on sample tc? I'm pretty sure this is not supposed to happen.

I have lost 100 points on my C due to WA on pretest 2 which was sample 2. Can someone please look into this as this is affecting ratings of everyone.

Observation: WA on pretest 1 doesn't add a penalty.

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

    Only WA 1 does not give you penalty. No matter, how many there are pretests.

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

    Didn't see this was already answered. :)

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

      Why did they keep it for pretest 1 only? Does not make sense to me. Shouldn't it work for all samples because that was their original intention.

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

        I guess the reasoning behind keeping it for pretest 1 is that it automatically takes care of compilation errors and doesn't penalize one for them. Also people who use file input/output locally get a run-time error on pretest 1 itself and are not penalized

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

Why does my div2 C 36170685 code fail on test 9?

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

Today something will happen that has never happened I believe in the history of codeforces.

I am just waiting for the next round now. :)

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

I have just noticed queryquerynk's submissions. He submitted D just 2 mins after his B, and passed at the first time. His D is not easy to code so fast like that, and also had different coding style from B. Seem like he did this round with a friend? Was that a kind of cheating?

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

why got WA on div2 A... Logic seems ok to me...if there is adjacent S to W I printed NO http://codeforces.com/contest/948/submission/36177886

Only problem seems i am checking an empty string...but it doesn't have 'SW' match any way

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

    You are checking a[i + 1][j], but i + 1 can be > n. Another example is a[i — 1][j], that can be an empty string.

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

      yes an empty string.... not =='S'...doesn't empty string means ..we get 0....anything is other than 'S'..shouldn't print no..

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

        You are trying to get the part of the array, that havent been initalized. It can be anything, like 'a', 'Z', '\0'. It is not guaranteed that it will be 0. In the normal situation, it would result RE, but sometimes STL work weird :D

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

          well..i bet it's either my f''ing luck...or codeforces is initializing them with 'S' cause i don't think global variable gets initiazied with 'S'.. what do u think??

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

    can u please explain this majk...... & MikeMirzayanov ?

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

I would like to report a very strange behavior that I faced today. My solution 36155783 for 948A - Protect Sheep passed pretests and had verdict "Wrong answer on test 13" in final system tests. Later, I was surprised to find that the wrong answer has been caused because of absence of boundary checks, link to my AC code 36177781. My question is global space is supposed to be initialized with 0, and I manually filled the first row with "0"s. Then how is it possible that a 'S' is there in the out-of-boundary space to cause the wrong answer or am I mistaking something or is it a compiler bug ? Thanks in advance.

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

    Row 0 is a empty string and column c+1 is also empty

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

      Yes, but how can there be a possible 'SW' match? There must not be any 'S' present over there in the out of boundary space, since global space is initialized with 0 ??

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

    I would politely like to mention majk and MikeMirzayanov here. I would be really grateful if you kindly come forward to explain this behavior to me. Thanks in advance.

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

    It's simple UB.

    You read string s and concat with '0'. So length of s[i] is C + 1. But you trying to access item s[C + 1] which is out of range. This is certain UB.

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

      Well, definitely it is. But I think you missed the other fact that I mentioned. In global space, everything is supposed to be initialized with 0. In fact, I have used this fact to solve many problems till today. So, my question is how may there arise an occurrence of existence of an 'S' in the out of bound space then ?

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

        In global space everything is 0 — correct. So s[0] is empty string. So when you access s[0][i] you've got UB again.

        UB means that there really no way to predict behavior. If you've got this you potentionaly can get change other variable in other space, you can get elephant in your room (Can't remember who said this). I once get exception in other cpp file just cause UB.

        If you want determined behaviour use at() function. It's supposed to throw out_of_range exception.

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

    use 2D array of char instead of using 1D array of string

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

Really enjoyed the problems today. :)

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

I am waiting for the new song by Petr, "The Fall of Tourist"

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

401st place? Really? When I was 403rd it wasn't so hard:D

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

Can anyone please tell me why my soln. gives wa on pt 20

http://codeforces.com/contest/948/submission/36157645

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

    When you check adjacent tiles, you are sometimes accessing out of bounds array elements. This is causing undefined behavior.

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

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

    That's a pity. Hope tourist will come back again! :)

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

    I always believe that old rating formula was much better than new rating formula. Before this round everyone agree that he is the best in CF — but he falls to the 4th place just because he fails a single round? In one round everything can happen. It puts too much weight on the newest round.

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

      I like the volatile formula. Imagine being gone for two months, then doing well on a contest, only to find you gained 15 rating...

      Nobody really assigns that much weight to ratings anyway. Everyone still agrees tourist is the best in cf.

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

 When I noticed tourist is not the leader!!

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

Hi, I got "WA 8" on div.2 D.

Here is my submission.

Who can help me find the bug?

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

    OMG, I know why!

    When using the multiset, the "erase" function does not act like the set.

    Example:
    multiset b;
    b := {3,3,3,5,6,6,7} // just a example, do not mind the grammar..
    b.erase(3);
    And then : b := {5,6,6,7}

    erase a number in the multiset will actually erase all of them.

    It's my first time to use multiset. Maybe I still have some problems. But finally I learned something useful.

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

A competitor in Grade 8(djqtxdy) became Grandmaster after beating tourist in last night's round!

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

It's amazing to see the fall of tourist.

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

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

948A — Protect Sheep

The code that i submitted during contest got WA on case 49.But the same code got AC when i submitted it after contest.

AC http://codeforces.com/contest/948/submission/36177413 WA http://codeforces.com/contest/948/submission/36157981

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

    Maybe because you defined the array "a" in the main function.

    Arrays defined in functions may not be initialized.

    Try memset(a,0,sizeof a); Or you can define arrays out of main function (they'll be initialized by 0).

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

      But now the same code is getting AC. Why?

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        if(a[i][j-1]=='S' || ...
        

        When j = 1 you compare 'S' and not initialized value. Not initialized value is usualy a random value. So the result of this compare is random too. When you are lucky your random solution gets AC :)

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

Problem D was beautiful, respect to majk for it

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

it feels so good

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

Could anyone find out what is wrong with my program for Div. 2 D? I used a trie like the editorial, but I seem to be off by one for some answers and I have no idea why. Could someone help me out? thanks 36214710

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

    Update: I seem to have fixed it by removing "remove node" function and lowering the node count while traversing the trie. Still not sure why the original function didn't work, though.

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

Only tourist can lose 290 points and still have 300+ points above Legendary Grandmaster line.