Привет, Codeforces!
В 18.02.2019 18:40 (Московское время) состоится Educational Codeforces Round 60 (рейтинговый для Див. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Abizer Reziba Lokhandwala.
Удачи в раунде! Успешных решений!
А вот сообщение от наших друзей из Harbour.Space:
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.
Поздравляем победителей:
Место | Участник | Задач решено | Штраф |
---|---|---|---|
1 | kmjp | 7 | 258 |
2 | dreamoon_love_AA | 7 | 269 |
3 | BigBag | 7 | 376 |
4 | Benq | 7 | 573 |
5 | step_by_step | 6 | 178 |
Поздравляем лучших взломщиков:
Место | Участник | Число взломов |
---|---|---|
1 | LiM_256 | 65:-8 |
2 | stefdasca | 23:-5 |
3 | Orion | 11 |
4 | prohor.b | 10 |
5 | parasocial | 9 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
Задача | Участник | Штраф |
---|---|---|
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: Разбор опубликован
will unsuccessful hacking attempts have penalty?!?
why downvotes?!? What is wrong with you? :(
Автокомментарий: текст был обновлен пользователем awoo (предыдущая версия, новая версия, сравнить).
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 version
I'm going to call the military police for this incident.
See the first version 3 minutes before the contests
Now 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 wish all participants who can be rated in this contest can't be rated in the next educational rounds!!!
:-)
Good one.
Delayed by 5 minutes :(
It's time to read comments :)
Hope i become purple again
I hope so.
congrats
i hope that the problems be short :) sometimes it is hard to undrestand
Надеюсь обойдется без говна
goooood luck
unbalanced
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 ≤ 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.
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. ;) T1duS 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):
My source code for reference: 50141751
Isn't 7th step (last but one) complexity 2p * p3 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. >_<
Can you elaborate more I'm not getting it
What part is confusing? I think I already elaborated.
each period of length 1e5 can bring us at minimum 1 step closer to the target
this oneConsider 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.
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 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 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 (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.
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 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.
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.
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++)
tofor(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 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
.
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.
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
past is past, learn from it and move forward! Never stop.
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
В тегах задачи C указано ДП. Это какая-то ошибка или существует решение через ДП?
UPD: уже не указано
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 > 104, 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, 1015]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 awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (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