Educational Codeforces Round 60 [Rated for Div. 2]
By awoo, history, 6 years ago, translation, In English

Hello Codeforces!

On Feb/18/2019 18:40 (Moscow time) Educational Codeforces Round 60 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Abizer Reziba Lokhandwala and me.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Attention tech specialists!

Harbour.Space Barcelona is proud to announce a collaboration with one of our industrial partners to offer a fully funded scholarship for our one year Master’s in Data Science Programme at HSU Barcelona.

The Scholarship includes:

  • Full coverage of the Programme’s tuition fee (€23,000 value)
  • 3 hours of study a day at Harbour.Space University
  • 4 hours of internship a day with one of our industrial partners
  • €12,000 euros a year (living allowance)

Our data science programme will feature super star teachers like Mike Mirzayanov (Advanced Algorithms and Data Structures), Alexey Dral (Big Data: Map Reduce, Spark, BigTable/HBase) and Alex Dainiak (Discrete Optimisation), plus many more.

Harbour.Space is unique because:

  1. We don’t play by the rules. We bring practicing professionals, not only academic teachers, who come teach for intense, 3 week modules. HSU students are encouraged to experiment, fail, and try again, until they succeed.

  2. We are your home. Harbour.Space is a community of over 40 nationalities, and we're still growing.

  3. We provide an experience. Harbour.Space University is located in Barcelona, one of the most vibrant cities of our time.

If you are interested in the scholarship, fill out the form below and we will contact you about the next steps.

FILL OUT FORM

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 kmjp 7 258
2 dreamoon_love_AA 7 269
3 BigBag 7 376
4 Benq 7 573
5 step_by_step 6 178

Congratulations to the best hackers:

Rank Competitor Hack Count
1 LiM_256 65:-8
2 stefdasca 23:-5
3 Orion 11
4 prohor.b 10
5 parasocial 9
344 successful hacks and 480 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A tataky 0:01
B KieranHorgan 0:03
C step_by_step 0:11
D Gloid 0:11
E Benq 0:10
F TripleM5da 0:34
G tfg 0:16

UPD: The editorial is out

  • Vote: I like it
  • +144
  • Vote: I do not like it

Comments Comments (162)
| Write comment?
»
6 years ago, # |
  Vote: I like it -19 Vote: I do not like it

will unsuccessful hacking attempts have penalty?!?

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

Good luck to everyone on the round!

P.S. Do not view the previous version of the comment.

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

I love your problems <3

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

Nooor go for it ;)

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

How will the ratings be updated..or in what order since div3 contest is also tomorrow and I believe that the ratings after the educational round gets updated after the hacking ends...

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

Another week of contest overflow :D

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

    Moreover, 'Current or upcoming contests' section includes as many as 18 contests(No. 1125 and 1126 are not shown in the section). Some contest starts after 66 days. :)

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

Hope, I will become legendary grandmaster after round.

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

I wish all participants who can be rated in this contest can't be rated in the next educational rounds!!!

:-)

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

Delayed by 5 minutes :(

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

Hope i become purple again

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

goooood luck

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

unbalanced

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

The gap of Prob B and Prob C is large.

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

    I don't think so, the main thing is that the end of the binary search should be 1e15, and that was the main purpose of the Wa's :( I received 3 Wa's ...

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

      I don't think so, it is soon apparent that int-type can cause overflow, and though your comment is right, that also can be considered as large gap between Prob B and C. (and the end of that is 1e14, not 1e15.)

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

this C made me miss Geometric problems

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

Waiting for someone to post 'me after solving A,B' meme

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

U can't "C"

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

    Did you see Indian ICPC Qualifier/Online round this year?

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

    I read this as "u cant C" and it frustrates me since I couldn't solve problem C

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

after reading the problem C, I cannot go in the coding phase.

what a problem C is!

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

After a few nice educational rounds i didn't expect this one...

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

What's the most turbulent sea you've seen?

  • South Americans: Drake Sea
  • Chinese: South China Sea
  • Codeforces: Div2 C
→ Reply
»
6 years ago, # |
  Vote: I like it +47 Vote: I do not like it

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

Recursion.

contest ended.

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

Is D C(n-i(m-1), i) sum over i in [0,n/m]?

Is C binary search over answer d and calculate if Manhattan distance by applying operations till d is less than equal to d?

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

    About C, yes, this is a correct approach.

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

    How to calculate C(n-i(m-1),i) in time limit, I also came up with the formula Fn = Fn-1 + Fn-m but couldn't implement it within time limit, any ideas?

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

      f(n) = f(n — 1) + f(n — m): matrix exponentiation, but it's MLE for test 10. don't know why. :(

      test 10: 1 2. issue solved.

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

        what is the way to think to get the relation ... f(n) = f(n-1)+f(n-m)..

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

          See there are two case:

          1. use 1 magic gem which will occupy 1 space so remaining n — 1 space.

          2. use m normal gems which will occupy m space remaining n — m space.

          Add these two. done.

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

    Yes, D is right. But it can't be computed in given time limit since n ≤ 1018. I also wasted like 30 minutes in trying to find how to compute it efficiently. You can actually find the dp recurrence and then solve it using matrix exponentiaion.

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

      if n <= 10^6, I could solve that. how can i do dp. in which array.

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

It's just me or both D and E are surprisingly hard compared to past Educational...
Btw, can anyone give me some hints on those ones?

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

    In D, you get dp[i] = dp[i-1]+dp[i-m]. Just matrix exponentiate over this.
    In E consider all triplets aaa,aab,aac,aba,abc..zzz and try matching them.

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

      hii.. i did exactly same but getting MLE don't know how at according to me at any stage of process i have 3*(1e4)*log(1e18) long long memory cells pls help http://codeforces.me/contest/1117/submission/50130097

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

        Argument p in function f should be long long. And if n == m answer is 2

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

      Woah, thought of recursive sequence but never imagined such sequence being real for D :O
      About E, can you clarify a bit clearer?

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

        Identify each index by giving it a 3-character long code. There are 26^3 > 10k codes. Therefore you can uniquely identify which position moved where within the three queries.

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

    You can try to solve D using meet-in-the-middle

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

    Here's a nice solution for E:

    Let the length of the string be n. You want to store an array change[n] storing where the ith character goes after the entire transformation.

    The trick is to write all indices in base 26. Each index can be written in 3 digits in base 26 as n < 26^3. Use one query for each digit. You can encode the ith digit as,

    encode(index) = (i/(26^(i-1)))%26 + 'a'

    and decode as,

    decode(character) = (character — 'a')*(26^(i-1))

    Code: 50128214

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

      Finally understood it. Thanks. ;)
      Things look so neat and so easy after this. ;)

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

How to solve F and G?

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

    My solution for F (pretty tricky, using bitmasks):

    • First, consider a set of 2p bitmasks, in each mask the i-th bit denotes that the i-th letter (0-indexed) in the alphabet is included in the deletion sequence.
    • Take all the bitmasks into a graph. Imagine we're starting at mask 0. The objective is going to a mask that has the smallest string size. Those values can be easily precalculated.
    • From a mask m, it can reach any of the masks having value of (0 ≤ i ≤ p), as long as those masks are allowed to reach (we'll consider that below).
    • If any pair (i, j) (i ≠ j) is not allowed, then the following is true: any substring [L, R] such as L + 1 ≤ R - 1, sL being the i-th alphabet letter, sR being the j-th alphabet letter and those two letters don't occur within substring [L + 1, R - 1]; will form a bitmask — let's denote it as mask1 — that can never be reached. Also, all mask , with (not consisting the i-th bit and j-th bit), will be unreachable as well.
    • If any pair (i, i) is not allowed, then the following is true: any substring [L, R] such as L + 1 ≤ R - 1, sL and sR being the i-th alphabet letter and that letter doesn't occur within substring [L + 1, R - 1]; will also form a bitmask — let's denote it as mask1 again — that can never be reached. Also, as above, all mask , with (not consisting the i-th bit), will be unreachable as well.
    • We can find all occurences of such substrings by traversing to all Ai, j, and then using two pointers to swipe through every possible substring. After this, we can generate the mask by finding which characters are in substring [L + 1, R - 1] — this could be done fairly quickly with the help of prefix sums. The complexity for this part is .
    • After finding each substring, we'll process with the spreading of the "disallowed" attributes from mask1 into all masks originating from it, which doesn't include either bit i or bit j, then every other masks originating from those, recursively. This can be done in a DFS fashion, and each set of parameters (mask1, i, j) will be called at most once. Thus, the complexity for this part is .
    • The final part will be traversing through all the masks. This is a simple DFS traverse, taken time complexity.

    My source code for reference: 50141751

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

      Isn't 7th step (last but one) complexity 2p * p3 because for each set of parameters it takes O(p) time.

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

        Hmm right....
        Makes me wonder how this passed so perfectly...

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

          I added a bitset for that spray part and it ran in 77 ms. Maybe tests are weak

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

            Well regarding the editorial such complexity was Pik's intended one. Maybe he is aware of this already.

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

It took me 1h and 17m to realise all I had to do in C to get AC is to raise the upper bound of binary search(from 2e9 to 1e15)...

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

    ahhhhh

    edit: ok, it's because the manhattan distance between start, end can be up to 4e9, and each period of length 1e5 can bring us at minimum 1 step closer to the target, so an upper bound of 1e15 is sufficient.

    what a silly mistake. >_<

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

      Can you elaborate more I'm not getting it

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

        What part is confusing? I think I already elaborated.

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

          each period of length 1e5 can bring us at minimum 1 step closer to the target this one

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

            Consider going through the entire string.

            It might be that it’s impossible to reach the target. I.e. if the string is LL...L and you have to go right, then it’s impossible. If it’s possible to reach the target, then going through the entire string once will bring you at least 1 unit closer to your target. (Note that it may bring you more than 1 unit to your target.) If it didn’t bring you 1 unit closer to your target then it would be impossible.

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

omg...C and D make me crazy....

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

can someone tell what's test case 14 in Problem D ? After writing shit Matrix Exponentiation code, I was continously getting WA :((

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

What is the worst case for the most steps on C? I could only find 10^14.

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

    Correction:

    (x1, y1)=(0, 0)

    (x2, y2)=(10^9, 10^9)

    n=10^5

    s=One U followed by Ds

    In one cycle you can either go 2 rights or 2 ups.

    Therefore it will take 1.5 * 10^14 days.

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

    Let d = abs(x1-x2)+abs(y1-y2), the optimal answer will never be more than n*ceil(d/2). That is, in every n moves you are approaching the destination by 2 (maybe 1 at the last n moves if d is odd). So the answer is at most 1e5*(2e9/2) = 1e14.

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

    That is the best varient. In every n day you can do two good steps or answer is -1, 2e9*1e5/2=1e14

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

I think this educational round was for Div. 1 participants. LOL

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

Hack me pls!

Task A Task B

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

In div2 D I've come up with this formula, so is it right ?

unfortunately did't fit into memory :(

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

    I think you meant n/m. Except that, I got a same formula However I couldn't fit that to TL and ML... :(

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

      yes, i heard something like using matrix exponentiation is right solution. but i don't have idea what is it that and how to use it.

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

        you can write the solution with a dynamic programming solution:

        dp[i][j] = number of ways to get length j with i gems
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j - k]

        But you can see that you are always coming from somthing with a lower j so you can forget the first dimension: dp[i] = number of ways to get the first i gems and the new recurence relation is

        dp[i] = dp[i - 1] + dp[i - k]

        And this is a standard matrix exponentiation problem

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

          could you clarify a bit.. as far as I understand either you can expand the last gem or leave it as it is so dp[i] = dp[i-1] + dp[i-m]...how does this link with your thought process..

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

When will the "impossible" condition trigger in C?

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

    If every wind blow will move you away from the target in either the horizontal or vertical direction.

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

      Is that the only condition? I've only included this condition.

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

        On an unrelated note: you can always approach this kind of problems with "if we can't get to the destination even after VERY_BIG_NUMBER steps, it means we can't get there at all", rather than adding some case handling to your code. VERY_BIG_NUMBER is typically easier and safer to estimate, compared to trying to cover all "special cases".

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

I've got a question regarding the penalty for a wrong submission. Maybe I am wrong, but I thought that a submission which fails one of the examples given in the problem, does not count as failed (it doesn't penalize you). However, I had a penalty for my first submission for problem C, which failed the 2nd example with runtime error. I've seen other contestants who got Wrong Answer on one of the examples given (not for problem C though) and did not get any penalty. I'd appreciate if someone told me when you get a penalty for a submission failed on one of the examples, and when you don't. Thank you.

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

    "If the result of the judging is Compilation Error, Denial of judgement (or similar) or if the solution didn't pass the first pretest, then this solution won't be considered in calculating results."

    So only if it fails the first pretest, then it doesn't count.

    From https://codeforces.me/blog/entry/4088

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

How to solve C?

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

    Binary search. It works because once you get to the finish point, you can stay there by going in the opposite direction than the wind, so if you can get there in x days you can also get there in y > x days

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

      How do we know that we can arrive in x day?

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

        Calculate the coordinate (x0, y0) of the ship if it went with the wind for the entire x days. Prefix sums might help.
        Arrival is possible if the Manhattan distance between (x0, y0) and (x2, y2) is not higher than x.

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

          Why are we going in the direction of wind only ?

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

            "If".

            We have our choice to either move or stay in any days, yet we cannot stop the wind, so better not using those moves yet and see where the wind will lead us.

            After being led by the wind, we'll start spending our x days to redirect ourselves to the destination. It's easy to find out that if the Manhattan distance between two coordinates is not higher than x, we can reach the place.

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

              Got it. Thanks

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

              why this give us the same result as if we choose to move in some direction for each time the wind moves us ?

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

                Because of the commutative property of the addition: no matter in which orders we add the value, the result is still the same.

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

Sorry guys for bothering all this time. Even after repeated attempts, I could not find the bug, so I thought of rewriting my code from scratch and surprisingly it works fine! Thanks for the help!

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

    learn to write comment correctly

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

      definitely will get better with time ;)

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

      After a lot of motivation that I got in the form of downvotes, I have edited my comment. Sorry for the inconvenience. Actually, this was my first comment on Codeforces so hoping to get better at it.

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

    Change your for(ll i=1;i<=n;i++) to for(ll i=0;i<n;i++)

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

      Everyone has there own coding style.

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

        I said to change that because trying to access a[n] where a is an array of n integers can cause undefined behaviour.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
          oh sorry
Anyway changing a[n] to a[n + 1] will work too but I think we should create array outside main with const int, say like a[111]
          → Reply
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

What is the proof that:

is equivalent to dp[n] = dp[n - 1] + dp[n - m]?

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

    dp[n] can be analyzed as the number of ways to get from 0 to n using steps of length m and 1. Let's try to calculate it in a different way: let i be the number of long steps. Then, we have to make n - im short steps and i long ones, so the number of possible ways to permute them is .

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

      So we are basically saying: To calculate number of ways of getting to n using steps of length 1 and m, we have 2 options:

      1) Either the last step is of length 1, so there are dp[n - 1] ways to it.

      2) Or the last step is of length m, so there are dp[n - m] ways to it.

      Thank you very much.

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

    Q1-this part ->> n-i(m-1)=n-i*m+i why we add i at the end ?

    Q2-we use combination not permutation because if the gems arrange them self in a configuration we won't have new configuration am I right ??

    thanks in advance

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

      Ans1 — I am not sure if I understood this question well. But if you mean that why left hand side is equal to right hand side, so the answer would be: because -i is distributed over +m and -1 yielding -i(m) and +i(1).

      Ans2 — We use combination to express that given some i, we want to know the number of ways we can choose i magic gems out of n-i(m-1) magic gems to convert them. This is equivalent to imagining that we have i converted magic gems and n-im unconverted magic gems, and we want to know the number of ways in which these can be permuted with respect to each other.

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

        for Q1 , I mean why we have to add i to the number of gems that we select from in other words why we don't select i from just (n-i*m)

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

          If you select i from n-im then the occupied space will be i*m + (n-im-i)*1 = n-i. You need the occupied space to be n. Note that you take i magic gems and convert them to i*m normal gems. That is, if you took these i gems from x gems, the space will change from x to x-i+im not x+im, because every taken gem removes 1 unit of space and adds m units.

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

past is past, learn from it and move forward! Never stop.

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

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

Alternative solution for D,which passed about 10 times faster than matrix exponential: Start with simple DP. DP[i]=answer for line of length i (in particular dp[n] is answer for our problem). Easy transision is: dp[i]=dp[i-1]+dp[i-m]. But we cant count it because n is too big right? Precompute DP up to 10^6(you can actually pick another value like 10^3 lets say). Now lets write recursive func COUNT(n) which while give us answer for line of length n. So if we call our function and n is already<=10^6 we can read the result from our DP. In another case n is pretty big. Lets look at the middle element of this segment and think what can be put in this place. It can be 1, so we'll get two smaller(1/2 size) arrays and the same problem on them to compute our answer. If in this place will be no "1" some segment of length m must be placed there. Lets check all m possibilities and then call our func resursivly on two disjoint segments ( left and right) for each possibility. Sum up results and you will get the answer. Important thing to note is that if we use function COUNT(n) we should store the result of this in (unordered)map, to use it later in another recursive call.

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

    why are u checking all m possibilities? is it possible because of the fact that either the whole segment is normal gems or a single special gem.

    so ,

    for i = 0 to m: count(l,r) += count(l,mid-i) + count(l+m-mid+i,r)

    please correct if wrong.

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

      You should multiply(not add) the result for right and reft segment. Check my implemntation if something is not clear.

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

        Oh sorry , i meant multiplication...but the parameters are right...??

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

          I dont actually know... my function count takes just one parameter ( length of segment) and you can check my code, it is pretty short and clean.

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

    could you explain the time complexity.

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

      We split segment into two moreless equal smaller segments. Then we recursivly take one of them and when we want to compute second we already have big part of count(n) precomputed. I would estimate it as log2(10^18)*M, but im not sure about it..

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

    Nice solution. Your technique seems to be similar to the one described in this blog's: https://codeforces.me/blog/entry/14385

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

    Nice idea! Just wanna point out that you don't even need to precompute any values, you can have it solved entirely using that recursive function. Simply set the base case of if(currentLength) < m) return 1; and it works. My submission (50143055) runs in just 31 ms.

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

      Yeah,sure but at first i was not sure about time complexity and i wanted to improve it by cutting recurrence faster.

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

can you help me my code for D is to slow and i don't know why https://codeforces.me/contest/1117/submission/50134529

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

In case of D , can we compute the final answer as ,

[f(n), f(n-1)] = [[1,1],[1,0]] * [f(n-1), f(n-m)]

so ,

[ f[n] , f[n-1] ] = [ [1,1],[1,0] ] ^ (n-m) * [f(m),f(1)]

[ f(n), f(n-1) ] = [[1,1],[1,0]]^(n-m) * [2,1]

is this right???

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

    It doesn't work that way, you have to take atleast m x m matrix.

    See this: matrix exponentiation

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

      i still dont get it.

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

        Ok [f(n), f(n-1)] = [[1,1],[1,0]] * [f(n-1), f(n-m)], but what will [[1, 1], [1, 0]]2*[f(n-1), f(n-m)] give you? It will give you [f(n)+f(n-1), f(n)], where f(n)+f(n-1) is a meaningless value. So actually it should be in this form:

        [f(n), f(n-1), ..., f(n-m+1)] = Transition_Matrix*[f(n-1), f(n-2), ..., f(n-m)].

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

          Thank you so much, I came across mat expo for first time..

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

        If you have a recurrence of form

        F(n) = a1*F(n-1) + a2*F(n-2) + a3*F(n-3) + ... + am*F(n-m)

        then the matrix will be

        |  a1 a2 a3 a4 a5 . . . am  |
|  1  0  0  0  0  . . .  0  |
|  0  1  0  0  0  . . .  0  |
|  0  0  1  0  0  . . .  0  |
|  0  0  0  1  0  . . .  0  |
|  .         .           .  |
|  .         .           .  |
|  0  0  0  0  0  . . 1  0  |

        Here we have F(n) = F(n — 1) + F(n — m)

        So a1 = 1, am = 1, a2 = a3 = a4 = ... = am-1 = 0

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

          Best explanation on how to construct the matrix. Thanks

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

After I saw the problem D

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

Why the tag of Problem E is "chinese remainder theorem"?

I want to know how to solve E with CRT.

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

    See 50144708.

    Since 26, 25, 23 are coprime, he's effectively taking the indices mod 26 * 25 * 23 > 104, which makes them all unique.

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

      Thanks, I was puzzled by "WA on 10" initially, so I changed my base from 26 to 25, then I got AC. But I still don't know whether it's strictly correct, for I only used 25 as my base.

      It's 50125872(WA on 10) and 50126626 AC.

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

Anyone could help me with problem G?It seems that segment tree works but i don't know how to do it.

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

    My solution:

    Let l[i] be the biggest number x such that x < i and a[x-1] > a[i] , consider a[0] = inf . r[i] be the smallest number x such that x > i and a[x+1] > a[i] , consider a[n+1] = inf .

    The answer for [L,R] is sum(min(r[i],R)-max(l[i],L)+1) for L <= i <= R

    Solve the problem offline by using Fenwick tree . (solve min(r[i],R) from R large to R small , max(l[i],L) from L small to L large )

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

RIP My purple dream

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

Can anyone explain how to solve C task please?) I just saw some solutions and there was binary search, how can we use binary search in this task?

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

    def reachable(startX, startY, endX, endY, step) -> bool

    Do binary search for step in range [1, 1015]

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

Any idea when the tutorials would be released?

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

How to solve D with matrix binpower?

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

    Observe that if f(n) is the answer for n size. Then, f(n) = f(n — 1) + f(n — m).

    Hint: Since n is very large, we need Matrix Exponentiation. I am not going in details but essentially now you have to make a column matrix of length something like 100. Make a square matrix so that transitions are possible(There's an easy pattern so we can fill the square matrix).

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

Was editorial out?

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

could anyone help me find bug in my code of problem C? thanks in advance! link

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

We got another round and we don't have editorial of this round yet!!!!!!!!!!!!!!!!!!!!!

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

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

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

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

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

In Problem C, I tried hard, but can't understand none of the explanations to determine boundaries for binary search(10^14). Can anybody elaborate it please? Thanks

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

    Worst case is when you start at position (0,0) and destination is(1e9,1e9) then manhattan distance is 2*1e9 , also in worst case scenario wind would be against you and it is at max 1e5 so if you can reach destination you should be able to move by 1 every wind cycle therefore 2*1e9*1e5 = 2e14

    → Reply