why downvotes?!? What is wrong with you? :(

Having changed content of the comment seems to have been good choice.

Are you dxymaster?

seeing the first version
I'm going to call the military police for this incident.

What is the previous version ?

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. :)

Only +1500 needed. Best of luck.

Good one.

It's time to read comments :)

I hope so.

congrats

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 ...

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

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

About C, yes, this is a correct approach.

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?

Yes, D is right. But it can't be computed in given time limit since n ≤ 10¹⁸. 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.

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.

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

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

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

• First, consider a set of 2^p 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, s_L being the i-th alphabet letter, s_R 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 mask₁ — 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, s_L and s_R 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 mask₁ 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 A_i, 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 mask₁ 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 (mask₁, 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

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. >_<

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.

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.

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

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

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

"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.com/blog/entry/4088

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

learn to write comment correctly

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

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 .

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

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.

could you explain the time complexity.

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

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.

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

See this: matrix exponentiation

See 50144708.

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

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 )

My Mint, Blue dream too..

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

Do binary search for step in range [1, 10¹⁵]

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).

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