majk's blog

Good Bye 2018
By majk, 6 years ago, In English

The end of the December is fast approaching and it is time for the best last contest of the year! The Good Bye 2018 round will take place on Sunday, December 30, 2018 at 14:35 UTC.

As the people who already engaged in discussions about the ultimate problem suspect, I am the problem writer. As such, I'd like to thank to:

The round will last for 2:30 hours and you will be given 8 problems for both divisions. There will be an interactive problem.

You have the last opportunity to reach Your rating goals for 2018. Good luck!

UPD: The top 3 participants eligible for ICPC 2019/20 season can win a great prize.

UPD2: The scoring distribution is 500-1000-1750-2250-3000-3000-3750-4000.

UPD3: Round is finished. I hope you enjoyed the contest! I am really sorry for the duck-up in problem G. I'll share more details once the important things (systest, editorial ...) are taken care of. The systest might be slightly delayed because of that.

UPD4: Editorial

UPD5: We apologize for the issue with problem G. We are still investigating this issue. Verdicts “Idleness limit exceeded” may be changed to other. We will write a full report about it later.

UPD6: The results are final, rating will be recalculated shortly. Congratulations to the winners:

  1. tourist
  2. eatmore
  3. Um_nik
  4. ecnerwala
  5. Radewoosh

UPD7: Some more information about problem G

Announcement of Good Bye 2018
  • Vote: I like it
  • +1032
  • Vote: I do not like it

Comments Comments (279)
| Write comment?
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

please, add Eve to the tags

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

    Are you crazy? Eve is a criminal!

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

      Eve makes the problems fun, she deserves to be in the main page.

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

      On the other hand, she adds Christmas-y feeling.

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

      Who is Eve?

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

I always enjoyed contests from majk. Hope to see something interesting for the last contest of the year!

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

Looking forward to it :))))

→ Reply
»
6 years ago, # |
  Vote: I like it -52 Vote: I do not like it

I am so sorry, but is it rated?

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

    Did you just missed this? "You have the last opportunity to reach Your rating goals for 2018. Good luck!"

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

      Oh, oh, oh I missed it men, I am so sorrrrry, Thank you very much, You are the best, You are better than tourist

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

        Are you doing this to win Most annoying person on CF by Um_nik? You are doing pretty well in it if you ask me.

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

Best birthday gift ever! Thanks, majk!

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

I don’t have good memory of goodbye 2017 hope this one overwrites that.

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

wait for the rating up！

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

Damn,

It might take CF 1 year to update the ratings.

→ Reply
»
6 years ago, # |
  Vote: I like it -29 Vote: I do not like it

"...you will be given 8 problems for both divisions." For (div. 2 and 1) or (div.2 and 3)?

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

Why is this post tagged with 'Alice' and 'Bob ? By the way, Happy new year in advance to everyone in Codeforces community.

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

    Because I often use Alice and Bob in the statements.

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

"You have the last opportunity to reach Your rating goals for 2018"

This makes me kinda sad. As I feel like I won't be able to reach it.

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

Here's a list of past Good Bye contests.

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

tfw my rating goal for 2018 was CM...

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

    nvm, thanks to magic my rating goal is a (temporary) reality

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

Happy New Year to all!

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

happy new year！

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

TinTin122 don't miss this!

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

kg16 try your luck on this :)!

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

so excited to back expert by end of 2018

→ Reply
»
6 years ago, # |
  Vote: I like it -28 Vote: I do not like it

if i dont get crapping expert this time i will do russian shooting

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

Just a little thought. Why dont codeforces make everyone automatically registered for every contest like codechef where we dont need to register for a contest ?

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

    Because there are rooms in codeforces for hacking. If everyone is assigned to a room there will be alot of rooms and most of them are empty.

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

Last contest of the year, Wishing a very good rating for everyone...

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

    Wow man, you're creating quite inspiring rating graph :). All the best for tomorrow's contest.

    → Reply
»
6 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Good to see an Indian Problem Setter. Random doubt, Is there any contest that is from an Indian User?

→ Reply
»
6 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Will this round be rated for div 3?

→ Reply
»
6 years ago, # |
  Vote: I like it -197 Vote: I do not like it

Upvote me, If you think, I can cross 1600 rating in Good bye 2018 contest.

Downvote me, If you think, I can't !

Be honest with your opinions, that will motivate me to do hard-work !

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

    Or just downvote him for spam comment.

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

    This contest was a quite challenging, enjoyable and memorable contest for me. I pushed myself so hard to reach that 1600 mark. I couldn't reach there but I ended up solving 4 problems.

    Thanks a lot ! your contest is pre-new year gift for me. majk

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

You can win if you want

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

best pat of the year

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

Everyone else on New Year's eve vs me

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

When verdict of problem will be accepted and when will be "Happy New Year"?

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

Hope to All high rating.

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

Happy new year,guys!(So what does the tag"Alice and Bob'...mean?)

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

Every time i see this blog, majk color keeps changing :D

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

    I am a fast learner!

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

      Not like it's helping your Atcoder rating.

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

        Are you competing today?

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

          Maybe, if there's time. Hard to say, everything's messy around holidays.

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

          And this is how it ends when I have people bugging me all the time during the contest.

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

2018 was a great year with lot of good contests hope this year be even better. thank to every one how prepared a contest and a special thanks to mike.

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

I hope that everyone can get high rating && change his/her handle's color by no magic.

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

First contest in cf history with more than 10000 registrations

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

I hope codeforces servers could handle the requests from this much contestants.

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


9000 and counting ...

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

DearMargaret ----> DearMargaret.

He doesn't want to achieve his goal anymore ?

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

Happy New Year! Fun & high rating for all of you:)

But I have to warn, that CF-Predictor doesn't support handle change. So if you change handle, the prediction is going to be completely wrong (for the first time only). As there are some people who changed handles, today's prediction is going to be a bit inaccurate for everyone.

Don't be upset, just enjoying the competition!

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

It's about time that I become a specialist.

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

It's biggest number of registrants ever

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

scoring distribution doesn't seem even

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

Good Luck! (:D)

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

\10000 Registration!/

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

Lets see if i can end this year with pupil

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

I suspect huge queues...

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

I freaked out when I opened the registrations page — lots of grandmasters :o. But then I realized they have just changed their colors :P

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

I already reached my 2018th goal (min 1600), but, damn ,this contest seems to be like a chocolate candy , cant keep my fingers from touching it. I hope for everyone steep positive slope in this contest.

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

however,good luck to the server!! Total: 10312

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

Will the CF servers be able to hold 10000 participants?

let's hope for a smooth one this year boys.

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

Been Newbie throughout 2018, time to pull out all I've got, to, at the very least become Pupil. I know the Purple, Orange, Red and Black Reds be like "Seriously, someone fighting to reach green??"

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

All the best to legend Petr

hope he does screencast for it too

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

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

Will the fake colors be disabled for hacking purposes? majk, gotta ping real fast, sorry.

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

tourist is here.

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

tourist joined. Let the battle begins!

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

11444 candidates registered...

It'll be a fierce contest.

Best of Luck Guys...

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

Finally, I find a contest announcement with no one asking whether it is rated.

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

Problem B: "As everyone knows, the world is a two-dimensional plane."

So the earth is flat?

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

CF Servers failed :( Denial of Judgement

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

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

Petr hasn't solved problems A and B yet :O :O :O

He tries to get AC problem H, but solving problems A and B will take just 3-4 minutes for him.

UPD: Finished. He didn't solve them, neither he solved H :(((

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

.

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

After reading first 5 problems GoodByeExpert :(

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    No need for Expert ;) You are already Grandmaster!

    \ps Actually same here :((( Also after reading first 5 problems "MathForces confirmed!".

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

Hacks for B?

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

problem c was nice :D , how to solve D ?

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

    n!+((ans for n-1)-1)*n) Don't know why it works though.

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

      How did you get this? :D

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

        Observation ;)

        I was trying different methods to get 56 for n=4 using the answer of n=3 i.e 9. Coincidentally the first method I tried gave the correct answer for 10 and it passed :)

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

        A concatenation of 2 permutations will have the sum n*(n+1)/2 iff the suffix of the first permutation won't contain any elements from the prefix of the second. That mean that the prefix of the first permutation needs to have the same elements as the prefix of the second (when we are talking of some prefix i and suffix n-i). Now 2 consecutive permutations will satisfy this condition always except for one time when the suffix elements are sorted in decreasing order. For example: 1 3 5 4 2 , the next permutation will have some elements from {5,4,2} in the prefix. Now it's only the matter of implementation. For each prefix i add to the answer A(n,i) * ((n-i)!-1)

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

    It should be clear that we automatically get n! subarrays, from the permutations themselves.

    For a given permutation, look at the the length of the prefix that remains the same when going to the next permutation. For example, for n = 4 say the permutation 1324 appears at index i. from 1324 -> 1342, the length of the prefix that remains the same is 2 (because 13 stays the same). Then, this means that we get 2 more subarrays that work, i.e. the ones starting from i + 1 and i + 2.

    The answer will be n! plus the sum of the lengths of these prefixes. We can calculate that recursively, given by the formula in the other comment.

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

      So every subarray p which works is a permutation of numbers [1...n]? Can't there be some other subarrays?

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

        So, this part was really hand wavy, but I think that a given subarray can have at most one duplicate, and if that's true then it would follow that every subarray that works is a permutation of 1..n. Not at all sure whether that's true, though.

        EDIT: This is not true, as given in an example by DEGwer in the editorial comments. spacewalker's comment below is good justification though.

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

        It is... at least in this scenario.

        Every subarray is either a permutation of [1..n], or some suffix of a permutation, plus a prefix of the next permutation.

        Consider some permutation P, and divide it into parts R1 a R2 b R3 such that the length of R2 b R3 is maximal, and R2 b a R3 is decreasing. The next permutation algorithm tells us that the next one, Q is R1 b reverse(R2 a R3). Let's look at the subarrays based on where they start:

        So we end up with a range R1 a R2 b R3 | R1 b reverse(R2 a R3). (The divider indicates where Q starts.)

        • The subarray starts in R1 a. Then the prefix of P we don't hit is precisely the prefix of Q that does intersect with the subarray. So it's a permutation of [1..n].
        • The subarray starts in R2 b R3. If you simulate moving the subarray start through R2 b R3, you'll notice that the differences in sums of neighboring subarrays increase, then decrease. This means that the only time the sum will equal is when the start moves in Q.

        So either the subarray is a permutation of [1..n], or it doesn't have the right sum.

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

          Thanks for the full explanation. It explained well.

          P.S. At first I was tricked by your fake grey color :D

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

    We can calculate for each x, the number of permutations where suffix of length x is not sorted. All these permutations combined with prefix of ext permutation of length n-x will have all distinct elements.

    As out of all x! permutations only one will be sorted.
    This can be calculated as n! * (x! — 1) / (x!) for all x <= n-1
    and simply n! for x == n

    The sum of all these terms will be the answer.

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

    ( (  ×  i!  ×  ((n-i)!-1))) + n!

    → Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +12 Vote: I do not like it

This contest was the worst performance of mine ever.. what a great way to end the year :/ I really felt out of luck this time, spent an hour on D but couldn't guess that formula even though it seems I was close. Oh well.

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

Please don't tell E was erdos gallai + binary search

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

    But it was...

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    That's what I tried, but the only thing I don't quite get is the range to binary search over, since the set of values that work (within a particular parity) isn't monotonic. I'm pretty sure it's an interval, but I don't quite get how to find a value in that interval to pivot from.

    EDIT: nvm, seems like I'm misunderstanding what exactly you're binary searching on...

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

    So sad. I didn't know this theorem. However, it may be more difficult for me to prove it during the contest. Thanks for reminding, and I'll learn it later. Thanks majk for a nice contest!

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

what a problem D is!

how to solve D.

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

    The idea is: number the permutations p1, ..., pn!. Then, for each interval of length n, say [l, r], some part of it is in permutation pi and the rest in permutation pi + 1. Let's say that [l, m] is in pi, and [m + 1, r] is in pi + 1. Now, you need to make two observations: Between one permutation and the next, any prefix either is the same as the other, or changes in exactly one element. If pi and pi + 1 have the same prefix of length r - (m + 1) + 1, then [l, r] will have sum . Else, they will not.

    The second observation is that a prefix of length l will change every (n - l)! permutations, so in total, this prefix will change times (the  - 1 comes from the last permutation).

    Therefore, to solve this problem, you notice first that if some interval is completely contained in a permutation, its sum will equal . Then, iterate over all the sizes of prefix, and for each, add to your current answer . The result is the answer.

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

all math problems and i got hacked, gg

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

It was a year full of "well, I cannot prove it but seems a lot had solved it. let's try the intuitive solution. Damn! seems it worked".

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

Pretest 8 for B?

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

    I think the test case is that which some coordinates are located in same row or same column. (But it is not certain.)

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

    pretest 4 was more challenging

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

The difficulty of Problem D and E seem to be quite different. How to solve E?

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

any idea about test 18 problem E?

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

How to solve D: 1) Write bruteforce 2) output n*n!-bruteforce(n) 3) find this sequence in oeis 4) profit

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

Btw, is there a Hello 2019 where I can recover back?

1500 rating is not quite suitable for a Legendary grandmaster :D.

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

    Yes there is, you can find it by going to the contests page.

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

Very interesting problemset. Does anyone know how to pass 18th test of problem E?

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

    What did you do? My solution is a horrible bunch of formulas and pointers and simply put garbage. I haven't coded something so ugly in the past year or so. I just iterated through all possible values of x and checked them with erdos gallai theorem (which btw, was kind of given in the statement, and I find that even more stupid than the problem itself). I also thought of maybe binary searching and having all values of a given parity in a range, but since people kept getting WA, I assumed that this was a wrong approach (+ I didn't have a proof)

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

      I used the same approach. First I find minimum degree of graph with Erdos-Gallai theorem and then do a binary search to find the maximum degree.

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

      I did the same thing. Agree it's one of the trickiest things I coded in a while :(

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

        There is already a pseudocode available here which works in linear time.

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

          For my solution I needed a modified version of the algorithm (to compute bounds for the missing degree), so just plain code wouldn't help too much.

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

How to solve E

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

it cost me totally three papers to solve problem D

BTW,a nice contest :)

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

    large lao take me up，take me up！！！

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

Who thought it was a good idea to propose a stackexchange answer as a problem?

Reference

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

    The problem statement provided a reference to those algorithms.

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

    Before clicking your link I was expecting to see this :)

    I've still managed to spend more than an hour to get it to work, though :(

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

      why u didnt solve a and b , petr

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

        It's a combination of two things: I was hoping to get H right until the end of the contest, which would give more points; I was quite tired at the end of the contest, so I was basically staring at the statements and not understanding them (at least not immediately, and then I switched back to H).

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

      I also assumed G would be googlable, but I couldn't find this thread. I also solved D by googling the algo for next permutation and probably would've taken one extra hour to solve the problem otherwise (and with a complete proof, since it's not straight forward that you can only cut a sequence in the unaltered prefix)

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

        Problem D seemed quite solvable to me: I just wrote some random permutation such that the next one differs much from it, and looked at how much the sum differed from the expected sum at each point:

        prev:    2  8  3  7  6  5  4  1
next:    2  8  4  1  3  5  6  7
diff:    0  0 +1 -5 -8 -8 -6  0

        In another view:

        target sum is 36
              subarray                          sum  difference
2  8  3  7  6  5  4  1                           36      0
   8  3  7  6  5  4  1  2                        36      0
      3  7  6  5  4  1  2  8                     36      0
         7  6  5  4  1  2  8  4                  37     +1
            6  5  4  1  2  8  4  1               31     -5
               5  4  1  2  8  4  1  3            28     -8
                  4  1  2  8  4  1  3  5         28     -8
                     1  2  8  4  1  3  5  6      30     -6
                        2  8  4  1  3  5  6  7   36      0

        From such example, we can see that, for the whole suffix that changed, the differences are nonzero in the general case: the first one is positive, and all the following ones are negative.

        Next, there is a straightforward calculation of how many permutations differ from the previous one in the last k positions. And then summing that up.

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

      Nice find!

      I wonder though. The answer at StackExchange does not use the fact that all primes are of the form 4k + 3. It seems correct in the general case.

      So, how does the 4k + 3 help? When trying to solve problem G, I've found that law of quadratic reciprocity has a special case for numbers of the form 4k + 3, but couldn't make anything of it.

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

        It is explained in the editorial: finding square roots modulo primes of form 4k+3 is faster, so the interactor is faster this way.

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

          Thanks, didn't see the editorial is already published.

          So I was trying to find a solution using a special property, but the property was ultimately for the jury side of things. Aaargh.

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

    That's not just a stack exchange problem. It's even worse: a relatively well known theorem (erdos gallai) which as a matter of fact was directly linked by the wikipedia article from the statement. I also find the problem veeeery bad, and apart from the trivial idea once you know the theorem, I found the code quite disgusting.

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

    That's not the correct causality. We found out after the problem was set, but still saw some substance to the problem (you first need to understand which question to ask and why).

    UPD: I thought it was about problem G. Disregard.

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

      That's trivial for anyone who has a chance to understand the theorem in the first place, the hardest part is writing correct code.

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

super tricky problems hehe, tnx

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

For B, I just output: {tx, ty} = {(sum of all(a[i]) + sum of all(x[i]))/n , (sum of all(b[i]) + sum of all(y[i]))/n}
I feel confused after seeing big codes of others :|

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

    I just sorted {a[i], b[i]} and {x[i], y[i]} and output a[0] + x[n-1], b[0] + y[n-1]

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

      As soon as i saw, all of the x[i] + a[j] are equal, the first thing that came into my mind was, sum of all of it will be n*tx.

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

Actually, the best contest of 2018...

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

Today's problems were fun! Thanks to majk and coordinators!

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

Problems were very well explained. No ambiguity. It gave you time to think instead of wasting it trying to understand the problems.

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

Nice problems. Bad difficulty. 2.5k+ solved D and 300- solved E. It's really big step. What results are you expected for that problems?

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

    We knew the jump was big. We expected a bit more solutions on F, but E is roughly what we anticipated after the tester spent time on them. I originally thought that F is a nice and simple Div1A-B problem.

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

      What was the solution for F? My idea is: first check how much water/grass needs to be added to avoid getting stamina < 0 on lava (water preferred to grass, added as early as possible); start with all flying, then "convert" it to walking/swimming with cost 2/1 for all lava in order; swimming is preferred and gets converted from largest position to smallest, walking gets converted from smallest position to largest. Finally, ensure the stamina doesn't drop below 0 on grass/water by converting flying in the same way (this part is trivial).

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

        Yes, this greedy was my solution as well.

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

          ...WA on pretest 11

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

            I actually didn't find the conversion to flying to be that trivial. Maybe you have some issue there?

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

              I convert from flying. If there's a half-meter of water where the duck is currently flying and I'm processing a half-meter of lava, I make the duck swim the last possible half-meter of water (where it's currently flying) that's before that half-meter of lava. Otherwise, I make it walk on the first possible half-meter of grass where it's currently flying.

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

        Are you saying you have two passes of conversion? Not sure, but it doesn't sound right.

        Maybe for the second pass, you need some flying converted to swimming earlier. And previously, you converted water from largest position to smallest. It may have been profitable to move the converted part closer to the front, so that the second pass is cheaper.

        In my solution, I had to handle both passes you describe simultaneously. To look ahead, I first calculated two quantities from back to front: how much surplus energy we will need moving ahead, and how much grass will be available ahead for conversion (I convert to flying, not from flying). Still not sure whether I got everything right though.

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

          How would I convert flying to swimming earlier? I convert to swimming asap whenever possible. If by earlier you mean position-wise, that could just lead to a worse situation where I just removed some flying I could convert to swimming to add stamina for flying over early grass in the 2nd pass.

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

My rule of thumb: Quickly check the hard side of problem, and Ctrl+F for the word "factor", "prime number" or any number theory stuff. If there's any, skip the round.

Trust me. It works very well.

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

    Got a better idea: check if the setter's handle contains "majk"

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

    I like numbers!

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

      are u one of the problem setters for Hello 2019??? I am probably not in the mood of another round of mathforces XDDD

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

    Just my personal (i.e. biased) opinion:

    This Good-Bye contest was by far the least enjoyable one for me. Problems D and E (which for many constituted the main 2 problems in this contest) were not of very high quality:

    • Problem D has a nice solution — which is, unfortunately, much easier to come up with than to prove. Also, for many, OEIS helped, and very few spent time proving their solution is correct (I, for instance, saw the ridiculous number of fast ACs and just coded it and prayed it works on the N = 10 test).

    • Problem E allows for many solutions, but I think the problem is not very "fresh" — meaning that there are quite a few standard results about degree sequences.

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

      My opinions are also heavily biased, but honestly it's funny to see my "strategy" giving me so much win XD

      Googling up "degree sequence" is first thing I'll do if I solve E, so it's interesting how majk overcomes the issue: Just link the wikipedia and make people see them. It's better than nothing, I believe..

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

      Completely agree with you. I hate problems that are 90% math and 10% coding (C and D).

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

    What if instead of whining about the contest, you practice math problems so you can start AC-ing them? :)

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

Great contest to end 2018! Specially because you have multiple solutions for the problems :), which you get to know when you visit your room and see people doing tons of things to solve B!!

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +23 Vote: I do not like it

[RANT]

I feel really hurt by problem G.

  • One of my solutions, 47754232, should clearly be WA#1 (notice that very early in the source code I output N nonsense lines of numbers!). However, it failed only on 4th pretest, costing me 50 points (actually a couple of times, as understandably, I couldn't expect the bug to stay there!)

  • One of my other solutions, 47754966, passed pretests in just under 3s. This was quite weird for me as my solution was essentially:

while (4 seconds did not elapse) { ask the interactor for stuff; }

(This is very important for what happens next.)

...but okay, it happens.

Then, 20-25 mins later, I get an announcement that we can't actually use more than 100 queries! This of course incurred a large penalty on me (a few more WAs, 40min worse time etc.) as I needed to do a bunch of patches in order to make it into the limit. (Hopefully, it will pass the systests.)

  • The statement for G still contains the phrase "You can print as many queries as you wish, adhering to the time limit." Dammit!

[/RANT]

I feel you should do something about each of the above.

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

    I have checked the submission you mentioned manually and changed it so that it doesn't ask too many queries. You seem to have some bug in your approach, since on test 5 it sometimes detects as few as 6 factors, depending on the randomness. The correct approach should have error probability of order 10 - 14 with 50 queries.

    I am deeply sorry about the issues you had during the contest with this problem, but in this case we will not change the verdict.

    I am happy to discuss more if you wish, either here or PM.

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

      I vented in the comment before and I don't think I have anything else to add. It's good to know that I had something wrong in my code, too. I still totally hate the way the things worked out (I hardly remember getting that infuriated by a single task), but there's no frickin' thing to do now.

      I wonder if I would've passed the original version of the problem. Or maybe not, I'd be fuming if it turned out I would.

      :<

      → Reply
»
6 years ago, # |
  Vote: I like it -99 Vote: I do not like it

I dont see how tourist can come up with the solutions to hard problems so fast. I think he is a great googler.

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

Boy, I am so slow, not only am I slower to code than everybody, but even my programs are judged slower than everybody...

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

    Man, your comment reminded me so much to Pet Cheetah lyrics, Lol.

    (8) No, I move slow. I want to stop time. I'll sit here 'til I find the problem. (8)

    If you want to hear it XD

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

how do i view the contents of a hack?

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

    You need to wait for systest, then it should be avaible on the hacks tab and you can click on "View test", here is the link for some other past contest where you can do that.

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

    After system testing, go to your submission page, you will find a link called View test in the verdict column, below Hack #some_number

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

I made 5 unsuccessful hacks trying to hack two O(n3) solutions of problem B. This is the second problem in recent contests were the limit is set to 1000 and O(n3) solutions pass!

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

    Also depends on what is inside the loop. Implementation with very light calculations generally passes for the order of 109

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

    1e9 operations can be done in about less than half a second

    It depends on the constant

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

Problem D. I don't sure it's correctness. a[n]=n*(a[n-1]-1) starting with a[1]=3. ans = n!*(n-2) + a[n-2]

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

Are you sure that "Idleness limit exceeded on test 4" is not a bug in interactor?

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

    I'm looking in it. It seems sometimes interactor is too slow and it gives ILE verdict because of huge waiting in a solution. I'll handle all such cases and rejudge solutions if needed. Sorry for it.

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

Possible way of thinking in D:

Suppose the concatenated sequence of permutations is p(1) || p(2) || … || p(n!) where “||” is the concatenation operator. The sub-array you will choose will always be in the form of: suffix of length L from p(i) || prefix of length n-L from p(i+1).

Let’s loop on j from 1 to n to see how many suffixes starting at index j (in any of the permutations) we can choose out of all n! suffixes out there. First note how p(i+1) will differ from p(i), the rightmost number in p(i) which is less than to the number on its right (call this number v1 and its index in p(i) ind) will be swapped with the smallest number in sub-array [ind+1:n] (call this number v2) such that v2 > v1, then subarray [ind+1:n] is sorted in ascending order, sub-array [1:ind-1] won't change, resulting in p(i+1).

We have 3 cases here:

1) ind >= j, then all the changes will happen within the sub-array [j:n] to get p(i+1), so prefix of length j-1 is same in p(i) and p(i+1), so you are sure this suffix || prefix should be added to answer.

2) ind<j-1, then the prefix of length j-1 will be different in p(i+1), here is one important thing to notice:

In p(i), sub-array [ind+1:n] is sorted in descending order and p(i)[ind] < p(i)[ind+1]. This implies that p(i+1)[ind] will be v2 and sub-array [ind+1:j-1] in p(i+1) will have sum at most = v1 + v2 + (sum of sub-array [ind+2:j-1] in p(i) or 0 if ind+2>j-1). So the prefix of length j-1 has sum in p(i+1) < than that of p(i) and this suffix || prefix shouldn’t be added to the answer.

3) If ind==j-1, then prefix in p(i+1) will have greater sum (as v1 is swapped with v2), and this suffix || prefix also shouldn't be added to answer.

To conclude, our answer for every suffix of length L (for L from 1 to N) is the number of suffixes of length L which are not sorted in descending order = n! – nCL * (n-L)!. Add 1 at the end to account for p(n!).

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

I was frustrated seeing so many people solve D quite fast. But What!? OEIS!? Thanks a lot to let me know such a great thing!

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

    Actually, I tried to search it in OEIS but couldn't find the solution.

    After thinking for a while, realized it was just counting how many preffix — suffix combinations would exists and came up with it. :P

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

      It's on OEIS as the difference dif(i) = i! * i — ans(i)

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

I made a submission for problem G which passed pretests with 100 sqrt requests, and then printed the answer. After the limit was put in place, it still showed as passed presets, but it failed systests on test 1. Is there anything we can do about this? The problem statement says 100 requests, and printing the answer doesn't seem to be a request.

The submission is here: 47750364

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

    Hi, I'll handle it in the best way. Right now I'm fixing erroneous ILE verdicts for this problem.

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

    I'm investigating your issue. I'll keep you posted.

    UPD: This is a mistake on our side. After rejudging you get AC.

    → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +12 Vote: I do not like it

Maybe I should actually read the wikipedia link that was given in the problem statement E instead of wondering where everyone got the solution from.

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

in problram F:

3
1 1 1
GWL

shouldn't it be 5+3+1=9?

no, it's 2.5+0.5+3+1=7

I didn't even realized can fly half meter until someone told me.

Watch problem again, The duck looks at me like look at a retarded : |

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

After long struggle with Python3 and bugs, my 2018 sadly ends with

My solution rquires division over big integers. However I have no template for it, so I tried to implement it using C++ first, after some time I changed my mind. Because of unfamiliar with Python, I spent long time coding, thinking about many things about language rather than the problem(like is there any functions like std::unique()?). Oh it's really a terrible night for me.

Well I didn't mean stop writing problem, I think the problem is a good problem but it's harder for people only using C/C++, compared with those are familiar with Java or Python.

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

    Maybe throw them into a set using list(set(x)), not sure if this will work for your application?

    → Reply
»
6 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Why do I see legendary grand masters with ratings less then 1400? Is this a glitch? Someone please explain.

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

    It's a feature on Codeforces during the holidays. You can change your color and even name.

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

A duck comes to another duck to 'duck' lmao

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

    For what purpose does a duck duck with another duck I wonder? ;_;

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

      And I wonder that this duck travelled 1017( = 1012 * 105) meters over lava and what not just for a few seconds of ducking :D

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

        Maybe ducking with the chosen duck actually worths the efforts...

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

47761370

Oh come on! TLE 50, for real?? That's , man, it's not supposed to have TLE on !

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

    Basically, the problem has an O(N) solution. The editorial mentions O(NlogN) and O(Nlog2N) solutions (which should both pass). But, somehow, N is set to 5 × 105. What's the reasoning behind setting N so large?

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

    Tragic tears were shed when I couldn't get my nlogn to pass pretest #18

    it was a lazy seg-tree so the constant factor was larger but still...

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Similar to what happened to me. Mine is though. :'(

    47751545

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

      I resolved my case by changing multiset to vector... 47769849

      it appears that gathering all elements of multiset by iterators has extremely high constant o:

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

When will the ratings be updated?

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

The moment I saw the solved count of D for the first time, I felt like something wasn't right, and went for OEIS, yet found nothing (I tracked the wrong pattern I supposed). Then 20 minutes later I solved D by a math-inspired dp solution, with a few proofs backing my claim.
Then two hours later people told me that D can be OEIS-ed...
I don't know what to say regarding my case... :)

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

    How do you find it on OEIS?

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

      I didn't make it to find anything on OEIS. Other people did.
      If you're asking generally of how to search on OEIS, just input a part of a sequence.

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

        I input the sequence and oeis said not found...

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

          If it's the sequence of answer with input from 1 to 10, trust me, I tried it and found none as well :(
          You can look up for other people's comments. They mentioned some other derivative sequences ._.

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

            Actually, the sequence in OEIS has the formula f(n) = n*n! — (solution), so that's why it's hard to find it there. I couldn't find it either :(

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

            Basically, I thought about the problem, and it occurred to me that really, what we want to count is the number of ranges that don't work. Ie: N!*N-cnt.

            And that's indeed what's on OEIS.

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

Is it rated majk?

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

    Most certainly yes. We're just checking some submissions on G.

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

Out of curiosity, how were the large primes of the form 4k+3 created for test data in G?

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

    I think they pick some known big primes public somewhere. Probability checking is not allowed.

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

    Random + Miller-Rabin.

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

It's so...disappointment... I used unsigned long long and get Time Limit on pretest 4 for n = 1:

for (ull d = 1; d <= n - 2; d++)

I shoud just use usual long long, but... loosing 39 points of rating because of such stupid little mistake...

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

Good Bye 2018

ok

open the contest

solve first problem

ok

look at rest of problems

it's all math

uh oh

manage to solve the first 4 through some gift from the math gods

lose a couple rating but that's expected

eh

contest extended for 10 minutes

what

give up while there's 3 minutes left, can't possibly code E from scratch

time to relax after this disaster of a round, go play minecraft

1 minute later

C got hacked

what

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

3 10 10 50 WGL

In problem F how is the ans 220 for this ? I think it should be 240? Am i missing something? pls help

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

    To fly pass 50 meters of lava, you'll need 50 units of stamina, taking 50 seconds.

    Going past 20 leftmost meters normally will build up 20 units of stamina, taking 80 seconds.

    To build up additional 1 unit of stamina, the most optimal way will be swimming in-place within water segment. It's like, from a point in the water segment, you swim to the right 0.5 meters, then swim back to your starting point (or you can choose to start swimming to the left then going back right, the result is still the same). Each unit of stamina stacked costs you 3 additional seconds.

    You'll need 30 more units of stamina before flying pass the lava, so you'll need 3·30 = 90 seconds for the process of building up stamina.

    Overall, the answer will be: 50 + 80 + 3·30 = 220.

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

Math problem: * exists *

Codeforces users:

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

rename codefoces in mathforces

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

Tourist beat 2nd place by more than 2000 points. Anyone else thinks this is scary?

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

I was wondering why rating update is taking so long. Then I noticed that my rating change is 0

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

It was really a GoodBye 2018 Contest

Good Job Problems Setters and thanks for Giving me a good feeling as a Competitive Programmer

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

The contest is amazing.

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

Goodbye 2018! This year I learned much knowledge and made many friends with the ones who also love algorithm and love codes.I think codeforces is a wonderful platform that give we all another home! Hope we all better and better:) Happy New Year!

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

In Python for C question, return t + (t*(t-1)*d)/2 gives correct answer but, return (t/2)*(2 + (t-1)*d) where t is the number of terms in AP and d is the difference.. gives wrong answer on testcase 18. Can anyone explain this please?

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

    If t is odd then t/2 will round off to nearby value in second equation but it will not in first equation as either t or t-1 would be even.

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

I see many of the comments referring that D can be easily solved with OEIS. Can someone explain what is it and how to use it?

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

    https://oeis.org/

    A sequence encyclopedia. In problem D you're given a N, if you assume the answer is a known sequence then you can brute force the first 10 elements of the sequence, and then search it on OEIS. If it's a known result then the website is going to provide you with a formula to calculate the i-th term of the sequence, i.e. the answer to the problem.

    In this case the problem itself wasn't on OEIS, but the diference between every interval (n! * n) and the answer for the problem, call it ans(n). If you brute force the solutions for the first 10 n or so, i.e. ans(1), ans(2), ... ans(10), you can look up the sequence of the difference dif(n) = n! * n — ans(n) on OEIS and get the formula that solves the problem.

    If the website gives you some formula f(n) to calculate dif(n), then then answer to the problem will be ans(n) = n! * n — f(n), derived from the previous equation.

    This is the difference sequence i found on OEIS: https://oeis.org/A038156

    This is the one i used, which is the opposite of the previous one: https://oeis.org/A166554

    The second link provides you with the formula "a(0)=1, a(n) = n*(a(n-1)-1) for n>0", so the answer you would be looking for is n! * n + a(n), since i said it's the opposite to the actual sequence, i.e. a(n) = -f(n)

    Don't forget to include % MOD when calculating everything on the implementation.

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

    Well, it's better not to use it ;) Give some time on it's mathematics to see how overlaps between two permutations contain all the numbers (thus, the same sum), and you will yourself derive what's needed! Sample cases for the rescue, verify your formula for 3 and 4!

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

      "How to do X?"

      • "Don't do X, do Y"

      Stack Overflow in a nutshell

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

Can anyone help me understanding the approach of C? I am a beginner.

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

    only divisor(k) of N can be used and then it's a Arithmetic progression for 1 to n-k-1 by difference k

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

Huh, some specialist took the third place.

→ Reply
»
6 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Good luck & high rating!

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

I am so happy to be a specialist after goodbye 2018.

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

Case 7 of F is: 1 9 W

Jury's answer is 18. Can someone tell me how this is possible? The best option I can find is 19.

[Solved] swim 4.5 meters and fly 4.2, 4.5*3 + 4.5 = 18

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

[Deleted]

→ Reply