By PikMike, history, 5 months ago, translation, ,

Hello Codeforces!

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 FST-OIer 65:-8
2 stefdasca 23:-5
3 Orion 11
4 prohor.b 10
5 MattG 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

• +144

 » 5 months ago, # |   -19 will unsuccessful hacking attempts have penalty?!?
•  » » 5 months ago, # ^ |   -24 why downvotes?!? What is wrong with you? :(
 » 5 months ago, # | ← Rev. 2 →   +93 Good luck to everyone on the round! P.S. Do not view the previous version of the comment.
•  » » 5 months ago, # ^ |   +16 Having changed content of the comment seems to have been good choice.
•  » » » 5 months ago, # ^ |   +47 Not good, great! My contribution began to decrease faster than my rating.
•  » » 5 months ago, # ^ |   +5 Are you dxymaster?
•  » » » 5 months ago, # ^ |   +14 Yes.. What is that?
•  » » 5 months ago, # ^ |   +38 seeing the first versionI'm going to call the military police for this incident.
•  » » » 5 months ago, # ^ |   +22 See the first version 3 minutes before the contestsNow I'm participating in the contest with 10% of my eyes vision.
•  » » » » 5 months ago, # ^ |   +8 More like 110%.
•  » » 5 months ago, # ^ |   +38
•  » » 5 months ago, # ^ |   +3 What is the previous version ?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +14 He said to not view it.
 » 5 months ago, # |   -16 I love your problems <3
 » 5 months ago, # |   +1 Nooor go for it ;)
 » 5 months ago, # |   0 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...
 » 5 months ago, # |   +5 Another week of contest overflow :D
•  » » 5 months ago, # ^ |   0 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. :)
 » 5 months ago, # |   -22 Hope, I will become legendary grandmaster after round.
•  » » 5 months ago, # ^ |   +44 Only +1500 needed. Best of luck.
•  » » » 5 months ago, # ^ |   0 naa ho payega....
 » 5 months ago, # |   0 i'm going to become Blue
 » 5 months ago, # |   +58 I wish all participants who can be rated in this contest can't be rated in the next educational rounds!!!:-)
•  » » 5 months ago, # ^ |   0 Good one.
 » 5 months ago, # |   0 Once Again with a hope to cross 1400
 » 5 months ago, # |   -8 Delayed by 5 minutes :(
•  » » 5 months ago, # ^ |   +64 It's time to read comments :)
 » 5 months ago, # |   +3 Hope i become purple again
•  » » 5 months ago, # ^ |   0 I hope so.
•  » » 5 months ago, # ^ |   0 congrats
 » 5 months ago, # |   -7 It's time to read comment's
 » 5 months ago, # |   +1 goooood luck
 » 5 months ago, # |   +6 unbalanced
 » 5 months ago, # |   -10 The gap of Prob B and Prob C is large.
•  » » 5 months ago, # ^ |   +4 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 ...
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 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.)
 » 5 months ago, # |   0 this C made me miss Geometric problems
 » 5 months ago, # |   +27 Waiting for someone to post 'me after solving A,B' meme
•  » » 5 months ago, # ^ |   +65
 » 5 months ago, # | ← Rev. 3 →   -24 U can't "C"
•  » » 5 months ago, # ^ |   +24 Did you see Indian ICPC Qualifier/Online round this year?
•  » » 5 months ago, # ^ |   0 I read this as "u cant C" and it frustrates me since I couldn't solve problem C
 » 5 months ago, # |   +11 after reading the problem C, I cannot go in the coding phase.what a problem C is!
 » 5 months ago, # |   +13 After a few nice educational rounds i didn't expect this one...
 » 5 months ago, # | ← Rev. 2 →   +84 What's the most turbulent sea you've seen? South Americans: Drake Sea Chinese: South China Sea Codeforces: Div2 C
 » 5 months ago, # |   +47
 » 5 months ago, # |   +26 Recursion.contest ended.
 » 5 months ago, # | ← Rev. 5 →   +2 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?
•  » » 5 months ago, # ^ |   +1 About C, yes, this is a correct approach.
•  » » 5 months ago, # ^ |   0 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?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +2 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.
•  » » » » 5 months ago, # ^ |   +1 what is the way to think to get the relation ... f(n) = f(n-1)+f(n-m)..
•  » » » » » 5 months ago, # ^ |   +3 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.
•  » » » » » » 5 months ago, # ^ |   0 Thanks
•  » » 5 months ago, # ^ |   +5 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.
•  » » » 5 months ago, # ^ |   0 if n <= 10^6, I could solve that. how can i do dp. in which array.
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 months ago, # ^ |   0 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
•  » » » » 5 months ago, # ^ |   +1 Argument p in function f should be long long. And if n == m answer is 2
•  » » » » » 5 months ago, # ^ |   0 ohh shh**.. thanks for helping
•  » » » 5 months ago, # ^ |   0 Woah, thought of recursive sequence but never imagined such sequence being real for D :OAbout E, can you clarify a bit clearer?
•  » » » » 5 months ago, # ^ |   +15 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.
•  » » » » » 5 months ago, # ^ |   +6 What????It's so so so so neat.... :
•  » » 5 months ago, # ^ |   +1 You can try to solve D using meet-in-the-middle
•  » » 5 months ago, # ^ | ← Rev. 2 →   +15 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
•  » » » 5 months ago, # ^ |   0 Finally understood it. Thanks. ;)Things look so neat and so easy after this. ;)
 » 5 months ago, # |   0 How to solve F and G?
•  » » » 5 months ago, # ^ |   +5 Isn't 7th step (last but one) complexity 2p * p3 because for each set of parameters it takes O(p) time.
•  » » » » 5 months ago, # ^ |   0 Hmm right....Makes me wonder how this passed so perfectly...
•  » » » » » 5 months ago, # ^ |   0 I added a bitset for that spray part and it ran in 77 ms. Maybe tests are weak
•  » » » » » » 5 months ago, # ^ |   0 Well regarding the editorial such complexity was Pik's intended one. Maybe he is aware of this already.
 » 5 months ago, # |   +6 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)...
•  » » 5 months ago, # ^ | ← Rev. 2 →   +4 ahhhhhedit: 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. >_<
 » 5 months ago, # | ← Rev. 2 →   0 omg...C and D make me crazy....
 » 5 months ago, # |   0 can someone tell what's test case 14 in Problem D ? After writing shit Matrix Exponentiation code, I was continously getting WA :((
 » 5 months ago, # |   0 What is the worst case for the most steps on C? I could only find 10^14.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +10 Correction:(x1, y1)=(0, 0)(x2, y2)=(10^9, 10^9)n=10^5s=One U followed by DsIn one cycle you can either go 2 rights or 2 ups.Therefore it will take 1.5 * 10^14 days.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +6 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.
•  » » 5 months ago, # ^ |   0 That is the best varient. In every n day you can do two good steps or answer is -1, 2e9*1e5/2=1e14
 » 5 months ago, # |   +5 I think this educational round was for Div. 1 participants. LOL
 » 5 months ago, # |   -35 Hack me pls!
 » 5 months ago, # |   +6 In div2 D I've come up with this formula, so is it right ?unfortunately did't fit into memory :(
•  » » 5 months ago, # ^ |   +1 I think you meant n/m. Except that, I got a same formula However I couldn't fit that to TL and ML... :(
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +16 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
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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..
•  » » » » » » 5 months ago, # ^ |   +1 you can read about Matrix exponentiation Here
 » 5 months ago, # |   0 When will the "impossible" condition trigger in C?
•  » » 5 months ago, # ^ |   +2 If every wind blow will move you away from the target in either the horizontal or vertical direction.
•  » » » 5 months ago, # ^ |   0 Is that the only condition? I've only included this condition.
•  » » » » 5 months ago, # ^ |   +92 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".
•  » » » » » 5 months ago, # ^ |   0 Wow, neat trick. Thanksss!!!
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   +4 "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.
 » 5 months ago, # |   0 How to solve C?
•  » » 5 months ago, # ^ |   +1 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
•  » » » 5 months ago, # ^ |   0 How do we know that we can arrive in x day?
•  » » » » 5 months ago, # ^ |   +6 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.
•  » » » » » 5 months ago, # ^ |   0 Why are we going in the direction of wind only ?
•  » » » » » » 5 months ago, # ^ |   +7 "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.
•  » » » » » » » 5 months ago, # ^ |   +5 Got it. Thanks
•  » » » » » » » 5 months ago, # ^ | ← Rev. 3 →   0 why this give us the same result as if we choose to move in some direction for each time the wind moves us ?
•  » » » » » » » » 5 months ago, # ^ |   0 Because of the commutative property of the addition: no matter in which orders we add the value, the result is still the same.
•  » » » » » » » » » 5 months ago, # ^ |   0 got it thank you very much
 » 5 months ago, # | ← Rev. 5 →   -40 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!
•  » » 5 months ago, # ^ |   +7 learn to write comment correctly
•  » » » 5 months ago, # ^ |   +17 definitely will get better with time ;)
•  » » » 5 months ago, # ^ |   +8 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.
•  » » 5 months ago, # ^ |   0 Change your for(ll i=1;i<=n;i++) to for(ll i=0;i
•  » » » 5 months ago, # ^ |   +1 Everyone has there own coding style.
•  » » » » 5 months ago, # ^ |   0 I said to change that because trying to access a[n] where a is an array of n integers can cause undefined behaviour.
•  » » » » » 5 months ago, # ^ |   0 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] 
 » 5 months ago, # |   +16 What is the proof that:is equivalent to dp[n] = dp[n - 1] + dp[n - m]?
•  » » 5 months ago, # ^ |   +38 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 .
•  » » » 5 months ago, # ^ |   +5 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.
•  » » 5 months ago, # ^ |   0 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
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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)
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 5 months ago, # ^ |   0 I will try to get it thank's for your effort :)
 » 5 months ago, # |   +13 hello everyonein this contest i cheated:( and i take the code of problem C from my friendi want this contest to be unrated for me or ban my account or take just problems A and B into accounti am so sorry for this <3thank you all
 » 5 months ago, # |   +43
•  » » 5 months ago, # ^ |   0 The answer from A?
 » 5 months ago, # | ← Rev. 3 →   +35 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.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 You should multiply(not add) the result for right and reft segment. Check my implemntation if something is not clear.
•  » » » » 5 months ago, # ^ |   0 Oh sorry , i meant multiplication...but the parameters are right...??
•  » » » » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 could you explain the time complexity.
•  » » » 5 months ago, # ^ |   +1 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..
•  » » 5 months ago, # ^ |   +1 Nice solution. Your technique seems to be similar to the one described in this blog's: https://codeforces.com/blog/entry/14385
•  » » 5 months ago, # ^ |   +4 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.
•  » » » 5 months ago, # ^ |   0 Yeah,sure but at first i was not sure about time complexity and i wanted to improve it by cutting recurrence faster.
 » 5 months ago, # |   0 can you help me my code for D is to slow and i don't know why https://codeforces.com/contest/1117/submission/50134529
 » 5 months ago, # |   0 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???
•  » » 5 months ago, # ^ |   0 It doesn't work that way, you have to take atleast m x m matrix.See this: matrix exponentiation
•  » » » 5 months ago, # ^ |   0 i still dont get it.
•  » » » » 5 months ago, # ^ |   +3 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)].
•  » » » » » 5 months ago, # ^ |   +8 Thank you so much, I came across mat expo for first time..
•  » » » » 5 months ago, # ^ |   +21 If you have a recurrence of formF(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
•  » » » » » 5 months ago, # ^ |   0 Best explanation on how to construct the matrix. Thanks
 » 5 months ago, # |   +48 After I saw the problem D
 » 5 months ago, # |   +12 Why the tag of Problem E is "chinese remainder theorem"?I want to know how to solve E with CRT.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +17 See 50144708.Since 26, 25, 23 are coprime, he's effectively taking the indices mod 26 * 25 * 23 > 104, which makes them all unique.
•  » » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   0 Anyone could help me with problem G?It seems that segment tree works but i don't know how to do it.
•  » » 5 months ago, # ^ |   +25 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 <= RSolve 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 )
•  » » » 5 months ago, # ^ |   0 Got it. Thanks:)
 » 5 months ago, # | ← Rev. 2 →   +3 RIP My purple dream
•  » » 5 months ago, # ^ |   0 My Mint, Blue dream too..
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ |   0 def reachable(startX, startY, endX, endY, step) -> boolDo binary search for step` in range [1, 1015]
•  » » » 5 months ago, # ^ |   0 Ohh looks pretty easy thanks)
 » 5 months ago, # |   +11 Any idea when the tutorials would be released?
 » 5 months ago, # |   0 How to solve D with matrix binpower?
•  » » 5 months ago, # ^ |   0 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).
 » 5 months ago, # |   +2 Was editorial out?
 » 5 months ago, # |   0 could anyone help me find bug in my code of problem C? thanks in advance! link
 » 5 months ago, # |   +3 We got another round and we don't have editorial of this round yet!!!!!!!!!!!!!!!!!!!!!
 » 5 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   +1 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
•  » » » 5 months ago, # ^ |   0 Thanks! I got it.