Всем доброго времени суток.
Скоро состоится Codeforces Round #315, авторами которого являются студенты УрФУ sivukhin и Um_nik. Это второй наш раунд, первый пришелся на черные дни Codeforces, и мы надеемся, что второй наш раунд не вызовет таких катаклизмов :)
Мы хотим поблагодарить команду Codeforces за эту замечательную платформу и Polygon. Особенно хотим отметить Zlobober за помощь в подготовке задач.
Желаем всем удачи!
UPD1:
Разбалловка.
div2 : 500-1000-1500-2250-2750
div1 : 500-1000-1500-2250-2500
Настоятельно рекомендуем прочитать условия всех задач. Мы постарались подготовить достаточно разнообразные задачи, вполне возможно, что сложные для нас задачи будут простыми для вас.
UPD2:
Разбор
UPD3:
Поздравляем победителей!
div1:
1. KAN
2. Petr
3. enot110
4. tonyjjw
5. Konijntje
div2:
1. Lost
2. loser21
3. fyiwxp221
4. hqpwca
5. LazyWolfLin
Всем спасибо за участие.
Желаю всем адекватных результатов.
One suggestion to Codeforces team, Please do not allow someone to name their handle which has slang or obscene word or may be their handles are part of it. Thanks.
I don't really want to educate anybody here, but "sex" is the main thing why you exist.
where's your previous round? "I don't know what black days are."
Codeforces Round 231 (Div. 2)
why were those black days? o.O
http://lmgtfy.com/?q=black+day+codeforces
скажыте пожалуста раунд будет рейтинговый иле нет?
да
Good luck to everyone!Wish you high rating! And thanks sivukhin and Um_nik for this round! It's good to have another chance to practice more!
Here's a suggestion: Please hold more contests at 17:00 ~ 19:00 Moscow time. That time is more available for Taiwanese and Chinese coders. There are many of them!
Jeffrey I dont think that you should say anything trying to separate China. Plz mind your words.
Wow.
Didn't expect politics to be brought up on Codeforces.
Seriously?
Don't expect you say strange things on Codeforces.
I agree with you.
I agree with Ir1d. Taiwan is an inalienable part of the territory of China, always. Please be careful what you say.
Jeffrey Taiwan is an inalienable part of the Chinese territory.
There will be 2 sites. What wrong with site like codeforces?
You know what's wrong ? there is no 2 Zlobober, so how can we start a round without thanking him in one of the two sites !! mind your words man!
Of course another site has own cordinators
dear -emli-,
i think this will help you to fully understand IslamSalah's comment.
you're welcome.
Today I will beat both of you on contest
no, you can't :) don't even try :)
but anyway, i accept your challenge :D
and don't use fake accounts
what do you mean?
CHALLENGE COMPLETED :p
Taiwan is a part of China... Of course ,don't talk too much about politics
Speaking from a country clouded by all sorts of censorship, your comment is so trustworthy!
Okay I'm kidding, I kind of feel sorry for you,
since you've been brainwashed by a corrupted government since your birth :)
Of course, I still respect your freedom of neglecting the fact that Taiwan is an independent country and spitting out ignorant comments :)
I do not think you really don't expect politics to be brought up on Codeforces as you said before. How dare you say Taiwan isn't corrupted? I'm so sorry but what you said is a joke. I won't argue about it anymore because history will give us the satisfied answer like HK and Macao.
I have to say something again.Even though we all know Codeforces is not a site for politics.
lnishan
We don't need you to feel sorry for anyone.
Just feel sorry for yourself.
As I was saying,please mind your words. Codeforces is not a place for you to fill with nonsense delusion.
So should I guess that you have your own mind and you are not yet another machine used by a stupid government to spread fake things?
Time is the judger for what's right and what's wrong.We have our own beliefs and don't you dare say anything about it as we respected you as a man.
It's really a waste of time to write so much.D
Taiwan is part of China.
It has been before.
And it will be in the future.
AS ALWAYS
You're the one being delusional.
Feel like googling "Taiwan" and look it up on wikipedia?
Oh wait, you can't :) (without using VPN, proxy)
This is just pathetic.
Oh and, this will be the last comment I made on this topic.
Not interested in arguing with some politics zealots.
Keep living in your own world where every country is yours essentially.
hahahah, young man, so jump.
i mean Inishan is so jump. his words are so impolite, but some people still vote up for him. i dont know why,it is just sarcasm, taunt and discrimination. then pretend to be aloof from politics after saying the words, and use":)" to show his "accomplishment". In a word, Inishan's words are so arrogant, and do his grandparents and ancestor know?
I never talk about politics in public places, even this time. but plz mind ur words and be polite to every one. I dont mind my contribution, if u insist on supporting him, a ungratefulness and mean person.
Does the word "jump" have the same meaning in English?
I don't know much about Taiwan and China, I just want to say that starting time is a sensitive issue for us all.
In Korea, we take 'regular(19:30 MSK)' Codeforces round at 01:30(Of course North Korea would have it 01:00 :p). When the round was at 17:00 MSK, we took it at 23:00, which was really great(you can see me excited here). Even a tiny shift was very convenient for me. However, at the 17:00 MSK contest, many people were embarrassed, as their schedule(job, school, etc.) hadn't ended. Many other shiftings were preferable for some people, and uncomfortable for others. I am lucky too, because it doesn't really overlap with my schedule — it's just too late, and I will probably fall asleep in morning class. Some people might have regular rounds in the middle of their day — for example, New York has it at 12:30.
We are competitors from all over the world, yet users of Codeforces. Administrators of Codeforces don't realy have to make equality on opportunity. I personally would really like an early contest, but if it's not preferable, we can't request... I just 'hope'.
Taiwan is just a part of China. Why so serious?
The point is that earlier contest time is more friendly to coders in East Asia. I wanted to vote 'up' but misclicked it. Sorry bro. :)
I agree with JeffreyHo. I'm from Vietnam and it is difficult for me to participate in a contest. It is usually held from 23:30pm to 1:30am. So, can you hold the contest earlier?
I agree with JeffreyHo. I'm from Vietnam and it is very difficult for me to participate in a contest. It is usually held from 23:30pm to 1:30am. So, can you hold it earlier?
Это число и Цукермана и Хардаш`а, но почему это просто раунд 315?
Может быть, не нужно каждый раунд называть чьим-то именем?
Почему количество комментариев, которое указано под темой не соответствует их фактическому количеству? (до моего комментария система говорила, что их 32, фактически было 16)
Там было множество "очень полезных" комментариев, которые, похоже, удалили.
так и еть
Чувствую ненадолго я в синие вернулся ;)
Сравниваешь английскую и русскую версию и понимаешь, как богат руский язык ;)
руский?
Уверен, английский язык тоже очень богат. Просто я плохо знаю его богатства.
Я оставил комментарий, который за 4 часа собрал -180. Я мог оказаться на 8 месте в списке Бредора http://codeforces.com/blog/entry/15998. Но опущенские модераторы его удалили! Позор им!
Раунд #315 провален, можете расходиться :(
думаю надо какого забанить
I missed those black days of codeforces,but happy to witness black days of topcoder :)
Hope they will overcome too.
when did that happened ??
if you are asking about codeforces black days you can find it here, but if you are asking about topcoder I would say almost every SRMs of topcoder had some issues these days. So, I told it as black days for topcoder.
You are right.
It seems that the little issues that pops out almost every TC round is as critical as the black day's of CF, "which I'v witnessed on my third Round by the way".
However I started to get a more fan of TC than CF, hope they work out these issues :D
World Consumer Rights Day Round!
Happy Skyscraper Appreciation Day :D
Today:
1) Independence Day in Ecuador
2) Day of signing Panama Canal Zone accord
3) Day of returning Hong Kong in China
4) Day of St. Lawrence
5) Day of city in Naberezhnye Chelny, russian city.
Are you sure that this round must be named World Consumer Rights Day?
Surely you can give it more funnny name :-P Looking forwart to the round!
Sorry sir. But I have to remind you. The day of Hong Kong's returning isn't today. It was July 1st,1997.
Yes, but:
1994 The last British troops leave Hong Kong. After 153 years of British rule, the island is returned to China.
http://www.historynet.com/today-in-history
Oh,I was saying that the ceremony was on July 1st,1997. And here in China we remember the date as July 1st,not today.
Ok, thank you
but thx for ur remembrance:)
Your problems in the previous round were very interesting I hope this round will be the same :)
We all hope so.
Автокомментарий: текст был обновлен пользователем Um_nik (предыдущая версия, новая версия, сравнить).
This round shuld be called #NotPI :)
ceil(PI*100)It is better to say round #PI++ :)) *******************************************************
Excuse me, is your key stuck?
No, in this way people will read my comment. :)
And downvote your comment! If you do such stupid things!
More like #ICan'tIntoRoundingPi.
This time they told Score distribution SOON ;) THANK YOU |: ################################################################################
Is it depends on your result in contest?
Это ваш первый раунд?
Глупый вопрос.
Это второй наш раунд, первый пришелся на черные дни Codeforces, и мы надеемся, что второй наш раунд не вызовет таких катаклизмов...упс, не заметил
...
Это второй наш раунд, первый пришелся на черные дни Codeforces, и мы надеемся, что второй наш раунд не вызовет таких катаклизмов :)
You know, Div 2 contestants should not compete in Div 2-only rounds....the irony!
Edit:I know this is a div1+div2 round, just saying...
I know this is a combined round, just saying...No it's not combined round
I meant, div1+div2 . Sorry about that.
Any particular reason why you copied Dreamoon's photo?
I didn't copy.
"U contest" sounds good to me. Because Organised by "U"mqra and "U"m_nik of "U"ral "U"niversity .
fuck "U" sounds nice too.. don't take personally
Were you born to be downvoted?
no I was born go give pleasure to hot girls. happy ?
Why would I be happy? I am not a hot girl :p
so hot girl be happy on reading this ? thanks, you are my true friend
Since you were going to give pleasure to hot girl, I assume hot girl will be happy
Эм, а почему стоимость задач div1 не соответствует стоимости задач div2, как это обычно бывает?
То есть, если div2: 500-1000-1500-2250-2750, то div1: 500-1250-1750-...
Не видел правила, согласно которому это обязательно должно выполняться.
Поэтому: почему бы и нет :)
Problem E costs 2750, it going to be interesting!
hope to not see
Succesful Hackson Div 1.A :DI was away from CF for few weeks and what's this? They are no longer declaring the score distribution at last moment! When did people started playing safe?
WTH with A?
Very disturbing one!
Xellos I usually like your memes very much but this picture is very distasteful please can you remove it ?
I don't find it distasteful, I don't care about getting downvotes and since it's getting plenty, it's going to be invisible by default soon, so I don't even need to do anything.
And I can't delete the comment at this point anyway.
But if you can't bear it existing even hidden, there's always the option of walking away from the screen.
Actually, its so "distasteful" that its actually funny :p
true :p
"I can't delete the comment at this point anyway"
Couldn't you edit your comment? Learn from him how to hide your comment.
And, "I don't care about downvotes" — means you don't care this community! Mind your words...
"it's going to be invisible by default soon, so I don't even need to do anything" — logic is there if you don't take things out of context
No.
I was wrong about people always agreeing with Red coders....You were right! :p
?
Codeforces is hanging. Can't read codes of roommates.
When B has more solves than A...
Is the answer for DIV1B this sequence?
Yes sir, first difference of the bell numbers.
yes,it was also 2nd number sequance of bell -_-
Awesome! Is there anybody here, who discovered this sequence by calculating the answer for 1..5 using bruteforce?
I did :D but no time to impement :D
I've bruteforced for all n < 7, then OEIS it. Got 2 sequences, first one's formula is a little hard, so I thought second one is what I need. Accepted :D1.
How did you bruteforced n = 6?
It has 2^36 variants to analyze..
2^(6*7/2) = 2^21 values.
I tried all sequences, then found thr right one, but I could not implement that.
This is why I hate a single-input problem. People that has no idea at all can just do bruteforce, find the several first number of the sequence, google the sequence and get the answer.
There were two sequences corresponding to 1..5 answers. It was difficult to choose between them :)
no it was not :D you can just make 5 more if and 5 more submission and you will find which one was :D
After realizing that both sequences are equal it becomes much easier :)
:D :D :D :D yes much more easier :D
Exactly! missed it... I need to be more attentive :)
Why do you think this is an approach that should not be available? It looks quite creative and risky to me.
It can be even worse than that! The sequence in question is number 4 increasing sequence from the search based just on the 3 given problem examples: https://oeis.org/search?q=1%2C+3%2C+10
And the other (wrong) sequences could be rejected by simply copy pasting and running them against pretests. Shame on me, but that's what I did after I failed to "invent" this sequence on my own. Still, bruteforcing via pretests cost me quite a few points.
Why 10^9 in div1A is AC? I am about the solution without Sieve of Eratosthenes.
It's kinda not 1e9, because not all the prime numbers are 1,2*1e6 and if it's like divisible by 2, that is finished in 2 iterations(assuming isprime breaks at right time).
Actually, it's not 10^9 because of rare up to square root computations.
a bit hard contest ,
Just a BitFunnily enough, I solved A but not B. Can someone help me find the bug in my code (I keep getting a runtime error on test 7)? http://pastebin.com/tYXaAaEx
try this case maybe you r not checking for numbers out of range 5 5 4 37 4 4
Thanks! That was the issue. All I had to do was change "<= n" to "<= 100005" in line 25!
Guys, why SolveB was easier then A? More people solve B!
For me, the description of the problem A was very confusing.
Me too...
Agreed, didn't get the solve because the description was poor.
I think that many people didn't think enough on A.
The authors forgot to mention in problem A that the song continues to download as it's playing. Their mistake is understandable -- what they meant is reflective of real life -- but I can definitely see how it confused people.
A becomes more easier when you realize a statement, and much more easier when you realize a solution.
Какой threshold в A?
1179858
А там хоть когда-то надо про дерево палиндромов выводить?)
нет
Нет )
Очевидно, что число 1 всегда подходит, так как pal[1] = 1, а prime[1] = 0.
А почему найдется наибольшее такое число?
Не для всех чисел оно, кстати, найдется :) . Количество чисел-палиндромов
с константой, примерно равной единице(потому что для первых (len + 1) / 2 знаков числа всегда существует палиндром, при том единственный), в то время как количество простых чисел — субполиномиальная величина, но растет быстрее на начальном этапе
А
разве не субполиномиальная ?)
А, ну да. Туплю что-то :)
How to solve B(div1)?
bell_number
Let's say that equivalent numbers have same color. And all numbers such that they are not equivalent to themself have color 0. Let Fi be the number of ways you can color n points in exactly i colors. Then it is easy to see that
. Now the answer is 
because order of colors except 0 doesn't matter here.
Problem A has the worst statement i have ever seen in my life, i don't want to ofend you guys, but it was really bad, poorly explained, i don't like to do try/error on contests, even the clarification did not help much either.
Overall felt the contest was rushed and not tested enough (statements where not good) that is my opinion , of course people that guess the tasks only by input and output are going to give me negatives, but i don't care, had to speak up.
I agree with you lol
I agree with you about Div2 A, but the rest of the contest seemed ok to me, just a bit harder than usual.
Definitely agree. The examples didn't make much sense, and the clarification was pretty much exactly the explanation for the example(which was also confusing). Maybe a picture would have helped.
You are right, problem B was solved by more people than A! I wonder, how hard it was! (I don't know how hard because I am still unable to understand the problem.)
I guess A must have a bunch of tricky test cases, so even though I got the statement in one go, I preferred not to submit.
Does anyone have something better than randomization for div1 D?
I remember a similar problem being in NWERC 2014, and I solved that one with divide and conquer + heuristic, but it doesn't seem to be possible in this one. The randomisation idea is almost identical, though.
Address this comment: http://codeforces.com/blog/entry/19705?#comment-245177
What is solution to Div1C? Is 2-sat involved?
Exactly. You can use 2-SAT to check if there is any correct word with given prefix.
Div1C Крайне плохая задача для двух-часового контеста.
И в чем же проблема?
Приношу извинения авторам. Задача крута.
Правильно говорить — неадекватная задача.
После Rubanenko уже не так круто (:
That moment,when there are two cheaters in your room and u hack both of them :)
problem statement for problem A.(MUSIC) was very poor had to find meaning from test cases
tfw you optimise againt TLE and get RE instead
also tfw I know I'm going to get WA
There is no need to iterate through all characters from 'a' to 'z' while finding next symbol. One can observe that we can change any vowel to other vowel, and any consonant to other consonant, and the status of the transfromed string will be the same, e.g. whether it's in language ot not. So, finding next symbol requires exactly two 2-SAT checkings and therefore, you can solve this problem in O(NM),
I had this optimization from the very beginning.
What I did later was: (a) change the adjacency list in 2-SAT into adjacency matrix, (b) return -1 if M > 3N(N - 1). It worked something like two times faster and it passed pretests. (Of course consonant-only alphabets killed me...)
I wasn't iterating through all characters and still barely managed to fit within TL, spending 35 minutes and 10 attempts to make it :)
Rough bound which I got: 200*200*4=160000 rules; 160000*2=320000 edges in my graph. 320000 on DFS + 320000 on RDFS=640000 operations on getting strongly connected components.
200*2=400 calls of 2SAT while looking for LCP of answer and word from input; 200*2=400 more calls of 2SAT while restoring answer.
640k*800=5.12*10^8.
Quite a lot, now I am not surprised with TL16 :)
I am pretty sure that it can be implemented much better (and I'll look at other implementations to learn how to make it faster, thanks to authors), but looking at list of attempts with TL16 during contest — I am not the only one who struggled with it :)
At some moment, looking at guys with time <0.1 on pretests, I thought "OK, I screwed up with wasting a lot of time on implementing obvious solution while I had to come up with something smart".:)
mnbvmar, I_love_Tanya_Romanova, I see you. Indeed, I didn't think straightforward approach could lead to TLE. Sometimes it's better to spend more time to think and use not the very 2-SAT algorithm, but only ideas from it)
We can find transitive closure of 2-SAT graph in O(NM) before processing string, and the only information we use from it is reachability from a to !a and vice versa.
Now, when we have some prefix, we can fix vertices that must be visited in any case (respective to positions in prefix), and after that, while processing two vertices correspoding to other positions in string, we can use information about reachability to decide whether vertex to use.
Looks like about half of the solutions for div2 A are failing...wow...
Is this the first time the A problem has had less than half the solves of the B problem?
O(n^2) space complexity solutions are getting accepted for Div. 1 B ? Like seriously ?
EDIT : so wow , much butthurt. I should write these kind of opinions on the complexity of solutions more often just to see the "butthurt impact" it has on people.
Why not? n = 4000, n^2 = 16e6?
"I can't calculate
or try custom test, but it's totally not my fault."
your post in a nutshell
Do me/you a favor and multiply that number by 2 and "calculate" the difference between 256 and that number. Then use the acquired info to understand that two arrays of that size + bunch of other stuff won't fit in 256mbs of space.
You only need binomial coefficients in a 2D array. Why multiply by two?
why "two arrays" ?
there is only one 2-d array, another one is linear.
I was not going to code "your" solution was I ?
Thanks for the awesome contest (especially D and E)!
To get D accepted, I need to add "if (k == 0) return;" to my solution. First I lost Yandex because of a bug in the prime number generation, then this :(
What you did wrong in prime number generation?
and where is bug ? It looks like the algorithm described on wikipedia https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
for (int i = 2; i * i <= n; ++i)? On the wikipedia is the same for i = 2, 3, 4, ..., not exceeding √n: , but Petr used trick i*i <= n
For p prime greater than n1 / 2, pr[p] = 0.
~
so all the prime numbers greater than square root won't be processed.
Ohh, I did the same mistake in Hacker Cup initial round, but first of all experience programmed like you did and specially in final which result in giving you 2nd spot. As I_love_Tanya_Romanova said, you are really unlucky in problem C for last couple of years.
I was actually curious what problems people would see with this code. I see the following:
Actually I was also quite surprise by the fact the you initialize the value of array with 0 as default value which is not needed indeed. Then these two things comes into my mind.
You started with initializing all the array values with -1 then changed it to 0.
You had the boolean array(which is least likely) and changed it to int array as you use IDE so it suggest where you need to change.
And btw I think p[i] == i, and initially filling the array value as its index would have been a better idea, it would have reduced your chances of making mistakes but you know better than me and sometimes minor details decide the result.
If you remove just this line — pr[i] = i; and replace it with if (pr[i] == 0) the resulting array will be filled with 0 for primes and lowest divisors for non-primes.
Can someone explain what did DIV 2 A want us to do? I spent around 60+ minutes, and found it very unclear/contradicting. Not complaining about problem statements, but can someone explain it? Not the editorial, but phrase it in a better way.
You have to sum the infinite geometric series with the initial value being the current amount downloaded and the rate being (q — 1) / q repeatedly until the current downloaded is greater than or equal to the total length of the song.
Thanks chaosagent :)
It is a shame for me that I designed this algorithm but discarded it for the reason of precision errors may take place :/
I should have tried :|
I actually failed the system tests because of floating point precision... I just deleted a few zeroes and now it works and I am very very pissed off lol
Bad luck!... Get AC after change EPS from 1e-9 to 1e-6 :( ...
Integers :)
Waiting for Editorial. I want to see jury solution of Div1. D.
Auto comment: topic has been updated by Um_nik (previous revision, new revision, compare).
Hoped to stay in Div 1 this time, but because of a really stupid mistake in Div1A, will probably go back to Div 2. :(
:)
Автокомментарий: текст был обновлен пользователем Um_nik (предыдущая версия, новая версия, сравнить).
I only submitted B, and got a rating rise :D
Actually I believe problem A was Harder than problem B.
Автокомментарий: текст был обновлен пользователем Um_nik (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by Um_nik (previous revision, new revision, compare).
it was the worse A that have been prepared !!!!! i solved B in 7 min and C in 20 min But not A !
but other problems were fantastic!!! WOW ;)
thanks for reading!
Not my best performance, plus part of code editing is hidden under Chrome, but still — screencast
I had an unusual and impressive experience in this contest. My program for problem C outputs -1 after running about 1.9s. And I allocated a block of memory with the size of 1000000. In my computer, my program only used 1/3 of the memory I allocated. During the contest I tested my program and everything went well. However on the grader, it runs much more faster and used all the memory within only about 1.8s seconds so it got RE before it output -1.
Amount of accepted solutions to A which had "Palindromic tree is better than splay tree" in code is damn too high!
It's almost like a magical formula that gets solutions AC'd :D
We've added this phrase just for fun (:
Yeah, surely I know, but my point was that having this in code in most cases tells that people don't have an idea what is going on in this task and still managed to produce a correct code :P.
Why take chances, that's why! Suppose some guy solved it without adding that line, and then got pretests failed for some reason, panics and adds that line, just in case it was the reason for wrong answer. Submits again, gets pretests failed again, realizes that line doesn't matter, but still, leaves it there, just to be safe, or maybe cause he forgets to comment it in a hurry.
For 569C - Primes or Palindromes?, reading the problem statement, how can one determine — "Up to which number he should calculate the number of prime and number of palindrome number" ?
Editorial of the contest gives the mathematical proof that n < 107 even for maximum A = 42. So you can run once in your computer for A = 42 precomputing primes upto 107 to get the exact limit .
I forgot to use long long and get Wrong answer in problem 568A. TAT
It seems many other people took this mistake too. What a trick!
I can't understand 3rd sample test case in B div1 "B. Symmetric and Transitive"
1)empty set 2){x, x} 3){y, y} 4){z, z} 5){x, x}, {y, y} 6){x, x}, {z, z} 7){y, y}, {z, z} 8){x, x}, {y, y}, {x, y}, {y, x} 9){x, x}, {z, z}, {x, z}, {z, x} 10){y, y}, {z, z}, {y, z}, {z, y}
i think "E" can be solved with "divide and conquer & dp". this problem look similar to "http://codeforces.com/problemset/problem/101/E" ( my code : http://codeforces.com/contest/101/submission/13598464 ). they are similar because of limited memory.
we can solve 568/E using very basic idea. maintain length of longest sequence from any index i to n. if there is gap at i , store for all m numbers. if not a gap, only for one number. but it will take O(m*k + n) memory = ~10^8. now, divide the array into bucket of size sqrt. we can store all the information for first bucket. when we are done with first bucket , process second and so on. Space compexity = O(sqrt*k + n) ~ 3*10^7. decide the bucket size accordingly. Time complexity : O(m*k*FenwicktreeLogn(n)) .
i think problem "E" can be solved by "divide and conquer & DP". there is a problem with much similar idea ( http://codeforces.com/problemset/problem/101/E ) with my solution ( http://codeforces.com/contest/101/submission/13598464 ) .
The basic idea for this problem is to maintain a DP for each index i which store the maximum of length of LCS from i to n. if array has gap at i, then store for every m numbers , otherwise store for only one number array[i]. TimeComplexity : (m*k) which looks fine. Space Complexity : O(m*k+n) ~ 10^8 > 128MB. to resolve this problem, we can divide the array into blocks of size SQRT. now, store all the DP states for 1st Block , then 2nd Block and so on. so Space Complexity : O(sqrt(n)*m) ~ 3*10^7 , which looks passable. decide the bucket size accordingly.
Edit : Space Complexity does not passes. looks slightly greater than expected.