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**:

**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.**We are your home**. Harbour.Space is a community of over 40 nationalities, and we're still growing.**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.

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 | FST-OIer | 65:-8 |

2 | stefdasca | 23:-5 |

3 | Orion | 11 |

4 | prohor.b | 10 |

5 | MattG | 9 |

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

will unsuccessful hacking attempts have penalty?!?

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

Good luck to everyone on the round!

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

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

Not good, great! My contribution began to decrease faster than my rating.

Are you dxymaster?

Yes.. What is that?

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

See the first version 3 minutes before the contestsNow I'm participating in the contest with 10% of my eyes vision.

More like 110%.

What is the previous version ?

He said to not view it.

I love your problems <3

Nooor go for 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...

Another week of contest overflow :D

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

Hope, I will become legendary grandmaster after round.

Only +1500 needed. Best of luck.

naa ho payega....

i'm going to become Blue

I wish all participants who can be

ratedin this contest can't beratedin the next educational rounds!!!:-)

Good one.

Once Again with a hope to cross 1400

Delayed by 5 minutes :(

It's time to read comments :)

Hope i become purple again

I hope so.

congrats

It's time to read

comment'sgooooodluckunbalanced

The gap of Prob B and Prob C is large.

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

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

this C made me miss Geometric problems

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

U can't "C"

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

after reading the problem

C, I cannot go in the coding phase.what a problem C is!

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

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

Recursion.contest ended.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?

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?

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.

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

See there are two case:

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

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

Add these two. done.

Thanks

Yes, D is right. But it can't be computed in given time limit since

n≤ 10^{18}. 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.if n <= 10^6, I could solve that. how can i do dp. in which array.

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?

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.

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.com/contest/1117/submission/50130097

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

ohh shh**.. thanks for helping

Woah, thought of recursive sequence but never imagined such sequence being real for D :O

About E, can you clarify a bit clearer?

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.

What????

It's so so so so neat.... :<

Thank you both. ;) T1duS399 farmersrice

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

Finally understood it. Thanks. ;)

Things look so neat and so easy after this. ;)

How to solve F and G?

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

^{p}bitmasks, in each mask thei-th bit denotes that thei-th letter (0-indexed) in the alphabet is included in the deletion sequence.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).i,j) (i≠j) is not allowed, then the following is true: any substring [L,R] such asL+ 1 ≤R- 1,s_{L}being thei-th alphabet letter,s_{R}being thej-th alphabet letter and those two letters don't occur within substring [L+ 1,R- 1]; will form a bitmask — let's denote it asmask_{1}— that can never be reached. Also, all mask , with (not consisting thei-th bit andj-th bit), will be unreachable as well.i,i) is not allowed, then the following is true: any substring [L,R] such asL+ 1 ≤R- 1,s_{L}ands_{R}being thei-th alphabet letter and that letter doesn't occur within substring [L+ 1,R- 1]; will also form a bitmask — let's denote it asmask_{1}again — that can never be reached. Also, as above, all mask , with (not consisting thei-th bit), will be unreachable as well.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 .mask_{1}into all masks originating from it, which doesn't include either bitior bitj, then every other masks originating from those, recursively. This can be done in a DFS fashion, and each set of parameters (mask_{1},i,j) will be called at most once. Thus, the complexity for this part is .My source code for reference: 50141751

Isn't 7th step (last but one) complexity 2

^{p}*p^{3}because for each set of parameters it takes O(p) time.Hmm right....

Makes me wonder how this passed so perfectly...

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

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

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

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

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

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

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

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

2ups.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 this educational round was for Div. 1 participants. LOL

Hack me pls!

Task A Task B

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

unfortunately did't fit into memory :(

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

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.

you can write the solution with a dynamic programming solution:

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 isAnd this is a standard matrix exponentiation problem

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

you can read about Matrix exponentiation Here

When will the "impossible" condition trigger in C?

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

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

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".Wow, neat trick. Thanksss!!!

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.

"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

How to solve C?

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

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

Calculate the coordinate (

x_{0},y_{0}) of the ship if it went with the wind for the entirexdays. Prefix sums might help.Arrival is possible if the Manhattan distance between (

x_{0},y_{0}) and (x_{2},y_{2}) is not higher thanx.Why are we going in the direction of wind only ?

"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

xdays to redirect ourselves to the destination. It's easy to find out that if the Manhattan distance between two coordinates is not higher thanx, we can reach the place.Got it. Thanks

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

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

got it thank you very much

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!

learn to write comment correctly

definitely will get better with time ;)

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.

Change your

`for(ll i=1;i<=n;i++)`

to`for(ll i=0;i<n;i++)`

Everyone has there own coding style.

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

What is the proof that:

is equivalent to

dp[n] =dp[n- 1] +dp[n-m]?dp[n] can be analyzed as the number of ways to get from 0 tonusing steps of lengthmand 1. Let's try to calculate it in a different way: letibe the number of long steps. Then, we have to maken-imshort steps andilong ones, so the number of possible ways to permute them is .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.

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

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.

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)

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.

I will try to get it thank's for your effort :)

hello everyone

in this contest i cheated:(

and i take the code of problem C from my friend

i want this contest to be unrated for me or ban my account or take just problems A and B into account

i am so sorry for this <3

thank you all

The answer from A?

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.

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.

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

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

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.

could you explain the time complexity.

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

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.Yeah,sure but at first i was not sure about time complexity and i wanted to improve it by cutting recurrence faster.

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

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

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

See this: matrix exponentiation

i still dont get 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)].

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

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

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

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

Best explanation on how to construct the matrix. Thanks

After I saw the problem D

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

I want to know how to solve E with CRT.

See 50144708.

Since 26, 25, 23 are coprime, he's effectively taking the indices mod 26 * 25 * 23 > 10

^{4}, which makes them all unique.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.

Anyone could help me with problem G?It seems that segment tree works but i don't know how to do 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 )

Got it. Thanks:)

RIP My purple dream

My Mint, Blue dream too..

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?

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

Do binary search for

`step`

in range [1, 10^{15}]Ohh looks pretty easy thanks)

Any idea when the tutorials would be released?

How to solve D with matrix binpower?

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).Was editorial out?

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

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

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).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

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

Thanks! I got it.