When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×
By majk, 6 years ago, In English

The round 1 of VK Cup 2018 will take place on March 10 at 18:35 MSK (check your timezone). The contest "VK Cup 2018 — Round 1" is for teams qualified from two Qualification Rounds. The top 400 teams will advance to the Round 2, along with teams that qualify in the Wild Card Round 1 a week later. As usual, there will be two parallel rounds for those ineligible to participate in VK Cup, one for each division.

I'd like to thank KAN for steering my crazy ideas into a coherent unit, the coordination and also for suggesting one of the problems, AlexFetisov, qwerty787788, winger, Errichto, Tommyr7 and misof for testing the problems, MikeMirzayanov for building Codeforces and Polygon and VK for organising the contest.

All three rounds last 2 hours, and all are rated. The VK Cup and Div. 1 will have six identical problems while the Div. 2 contest will consist of five problems. The scoring distribution will be announced before the contest.

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

This is my first round on Codeforces and hopefully not the last. Wish you many submissions, high hacks and successful rating.

UPDATE: The scoring in Div.1 and VK Cup round 1 is 500-1000-1500-1750-2250-3000. For Div.2, it is 500-1000-1500-2000-2250.

UPDATE2: The round is finished. I hope you enjoyed it. Tune in a bit later for editorial.

UPDATE3: Congratulations to winners!

Div.1

Div.2

VK Cup

UPDATE4: Editorial

Announcement of VK Cup 2018 - Round 1
  • Vote: I like it
  • +251
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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

I am assuming there will be lot of hacks

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Looking forward to the round)

»
6 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Can the test in English?

»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    They were held for russian-speaking users only.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      But why orbitingflea and zhangzy can register? They're both Chinese.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        I know a lot of guys that they're not russian but they registered the contest...

        with just using a little bug(changing the page's language!):)

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        They passed qualification. I think they translated russian statements during it

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    The rounds are identical, but there are six different problems :)

»
6 years ago, # |
  Vote: I like it +130 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    '#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 years ago, # |
Rev. 3   Vote: I like it -8 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Cool!! Let's hope the problem statements will be identically short for both the Divisions :P

»
6 years ago, # |
  Vote: I like it -45 Vote: I do not like it

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

is it rated for teams?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +109 Vote: I do not like it

    Yes!

    Are you sure you don't want some downvotes? Maybe just one?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +95 Vote: I do not like it

      No thanks!

      i have a lot of them :(

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -64 Vote: I do not like it

        Are the downvotes rated?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          I think you are in a good position now to see for yourself. :P

          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Haha, yes. But I was just pulling OP’s leg — I guess kids are too bored with that joke.

»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What a sad time for Chinese :(

23:35 :(

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the time is quite good in your timezone?
    It'll be 21:35 if I'm right...

»
6 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I hope this contest will make me green !

UPD: I am green now :)

»
6 years ago, # |
  Vote: I like it -35 Vote: I do not like it

editorials ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +199 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted]

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Will we see tourist tonight? Exciting!

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

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

»
6 years ago, # |
Rev. 4   Vote: I like it -13 Vote: I do not like it

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 years ago, # |
  Vote: I like it +12 Vote: I do not like it

B > C

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

tourist is in the house!

»
6 years ago, # |
  Vote: I like it +31 Vote: I do not like it

CF-Predictor broke or something?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    announces X1 = 14 Bob picks prime 5
    then x2 = 15

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Lol Div2B harder than Div2C/D

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2-B ?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Why would you assume the the first prime divides X0?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        I don't

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          You say iterate over X0 and prime P that divides X0. Why does P has to divide X0? According to the problem statement any P less than X0 is a valid option.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I came up with exact solution after 10 mins the contest ended :(

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone share hack for C ?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +19 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +47 Vote: I do not like it

Original C, never coulda come up with such task.

»
6 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Hack test for D?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +224 Vote: I do not like it

I hate problem D. Stupid casework.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the solution?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        difference of length of longest suffix should be divisible by 3.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +10 Vote: I do not like it

          Yeah sorry.But only when |B|+|C| is same.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +126 Vote: I do not like it

    Me solving D

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It completely ruined my contest :/

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Yeah, this sentiment should be common.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        Wish you luck in next contests!

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 4   Vote: I like it +36 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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 years ago, # |
Rev. 2   Vote: I like it +60 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    '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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Solutions are not visible at the moment.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Here's the solution

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

      Edit: Solutions visible now

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DIV 2C was Lazy Propagation, right?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    No i solved it without segment tree.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    DIV2C can be solved easily with using Binary Search.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      cjtoribio, Can you please explain your solution?

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 years ago, # ^ |
    Rev. 3   Vote: I like it +3 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 6   Vote: I like it +6 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wrote something like partial sums.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i use binary indexed tree + binary search ...

    but just binary Search is enough

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why i can't open another's solution?

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +72 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    anti tourist ? ?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +79 Vote: I do not like it

    50 points are returned.

»
6 years ago, # |
  Vote: I like it +77 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +134 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    You need to learn to fail.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +179 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it -35 Vote: I do not like it

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

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +71 Vote: I do not like it

        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 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    next time buy a pair of plastic glasses like mine

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    just kidding to make you forget the failure

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I meant "Does intended solution use randomized algorithm?". Forgive my hastiness and English :P

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      struct Trie
      {
          Trie()
          { 
              next[0] = next[1] = nullptr;
          }
          Trie* next[2];
          //Usefull info
      };
      
      Trie* root = new Trie();
      
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +19 Vote: I do not like it

          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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Seeing many people implementing Tries made me wonder: am I the only one directly using the built-in multiset in C++ for that problem? (provided that my late source code would get AC)

    Btw here is my intended solution.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for giving me another problem which can be solved with trie.

»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Tourist's solution fails D. o_o

»
6 years ago, # |
Rev. 2   Vote: I like it +51 Vote: I do not like it

RIP ppppppppppppppp, you trolled yourself.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Did he get banned? Have never seen that before, CF is usually accommodating of trolls :)

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Only got comments deleted. (I didn't pay attention to the exact number of p-s.)

»
6 years ago, # |
  Vote: I like it +51 Vote: I do not like it

D WA99 <3

»
6 years ago, # |
  Vote: I like it +76 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +54 Vote: I do not like it

      They have different problem styles.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        In retrospect, I think the hack system needs a revamp. But I don't mind the pretest system.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you are not the only one..

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it +26 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Judge queue would be insanely long without pretests

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          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 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          Rev. 2   Vote: I like it +5 Vote: I do not like it

          >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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            At least we have pretests :). COCI has sample as pretests.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it -20 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Somehow I managed to AC only problem B div2 today

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Defeat Accepted.

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

Ebin :DDD

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

402nd place... Brutal...

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

36162982

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I lost my cool in the end. It's fucking depressing.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Did you throw your mouse or something?

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          I use my laptop and it has no mouse. But maybe I would have. I have a test today (it is 2 am here almost and my exam is at 11 am) and i sacrificed everything for today. but it just didn't happen. I will be 10 short in the end.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Didn't see this was already answered. :)

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Additionally If you have wrong Input/Output format, you fail to pretest 1.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Everyone has his/her bad days. I share the same with him. But a man like him, I know will conquer the next one. :)

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, I know that and this is the reason why I wrote that I am waiting for the next round now.

      Tourist will be at the top again soon. :)

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Everyone has his/her bad contests.

      FTFY

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    He would probably slip down from #1 (after a long time).

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It actually has happened before. But honestly speaking we should stop this sensationalising tendency of ours.

»
6 years ago, # |
  Vote: I like it -19 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Problem D is quite similar to Vasily's multiset in cf. you just need to change some of the conditions and you are ready to go.

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        6 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The memory inside strings isn't global.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        "global space is initialized with 0".I don't think it is necessarily true for STL.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        same problem ..vai

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Really enjoyed the problems today. :)

»
6 years ago, # |
  Vote: I like it -24 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    for the first time since i join CF.

    our lord and our savior Tourist get rekt

  • »
    »
    6 years ago, # ^ |
    Rev. 3   Vote: I like it +36 Vote: I do not like it

    tourist is just went for tourism , He will back soon :)

    I wait for The Return of Tourist

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +92 Vote: I do not like it

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +103 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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 years ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

 When I noticed tourist is not the leader!!

»
6 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

Here is my submission.

Who can help me find the bug?

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it -30 Vote: I do not like it

It's amazing to see the fall of tourist.

»
6 years ago, # |
  Vote: I like it +53 Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      But now the same code is getting AC. Why?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D was beautiful, respect to majk for it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

it feels so good

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +8 Vote: I do not like it
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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