Are you blind?

is it cause you forgot to thank mike

take my mandatory downvote

_HossamYehia_ XD

It's actually long. So are you hoping long problem statements?

no, please, no

Maybe Div 1.5 (purples included)

http://codeforces.net/blog/entry/49826 (14 months ago)
http://codeforces.net/blog/entry/58153#comment-418381
I hope it will be rated personally for you and not to your fake accounts (http://codeforces.net/team/37327) .

Do you want to come back tip of Div.2?

Losers are losers

This is the bug of competetive programming — only the world best participants can win prizes, it is dissapointing -_-. A lot of newbies quickly lose interest -_-. In any other sports participants are divided according to their age/gender/rating etc. and it is possible to win the prizes in any competition, if you are good for it.

Believe me, you are really blind!

"Educational"
Of course they are supposed to be easier

Contest will start on Tuesday

Before system testing!

Any of seasons 2017-2018 or 2018-2019.

It is "Educational" you don't take any score for hacks!

Hi pranjal.ssh!

Let's discuss this after the results of this round.

Now it does. Too late

same here :(. wasted more than 40 minutes!

we can use dp. dp states are dp[i][j] --> number of minimum hours he has to stay in the college if he skips 'j' lectures till the ith day!

Calculate pre[i][j] = Minimum time spent in university on i'th day after using j skips on this day.
Then calculate dp[i][j] = Minimum time spent in first i days after using j skips.
Answer is dp[n][k].
Transition is dp[i][j]=dp[i-1][z] + pre[i][j-z]. 0<= z<= j

You may have an initial greedy idea to skip classes on endpoints of a day if skipping that class saves you the most number of hours. Unfortunately, this does not work because of the case

2 8 2 10111101 11000011

Greedy solution would skip first and last class on first day, but optimal solution is to skip first and second class on second day.

We can make sets s_i for each day i that contain the hours that have classes. Then, for each day, we can calculate the minimum number of hours to attend class that day if we skip j classes on that day, and calculate this number for all j such that 0 ≤ j ≤ min(k, |s_i|).

Once we have that, we do a simple dp, where our dp array has n rows and k + 1 columns. dp_ij will contain the minimum number of hours to attend class after day i while still having j days left to skip. Then, for the first row, we fill it up with the values we calculated in the last paragraph (i.e. dp[0][k] will be total number of hours of day 0, dp[0][k-1] will be minimum number of hours on day 0 if we skip 1 class, dp[0][k-2] will be minimum number of hours on day 0 if we skip 2 classes, etc.). For rows i > 0, we just test the possibility of skipping 0 ≤ j ≤ min(k, |s_i|) days from each point in the previous row.

Then the answer will be the minimum number in our last row.

Totally random test with n = m = k = 500

i think the test 16 is something like when we skip on ith day some starting lectures and some lectures from last for an optimal solution. e.g 2 6 2 101101 000000 ans=2

I also got WA on test 16, mostly it would be the case of having some prefix and some suffix skipped on a particular day, as I was considering either of them on one day not both.

http://codeforces.net/blog/entry/58155?#comment-418680

Btw can you please explain your approach to E?

Hoyl, why did nobody tell us this during the contest!? Sorry, it should be fixed now, statement will get updated in a couple of minutes.

DP[i][j] indicates the minimum way to solve the suffix ending at index i, with j as the letter we are currently trying to assign (starts at 0, goes to 25), S is the input string

DP[i][j] = Min(S[i]-j + DP[i+1][j+1], DP[i+1][j]) — if S[i] <= j

DP[i][j] = DP[i+1][j] ------------------------------------ if S[i] > j

O(N*Alphabet)

Same issue

I'm investigating it. Thanks. Fixed!

Still, i am not able to see any other solution to problems. Ha Ha Ha

Hack to other solution how possible without a see code.

What is the test hack for problem C? I understand now.You are allowed to do multiple replacements for the same position of the string.

I'm not sure whether we can do it using only one segment tree, but model solution uses two segment trees with almost the same approach.

I have used one segment tree. There was no need of rollbacks, lazy updates, dynamic segment tree whatsoever. Only range query and point updates.
Solution

Not allowed to view request page :/ Pastebin/Ideone?

4 16 11
1111011101111111
0111110111111111
0011101111011000
0000010000001000

Yours : 31

Jury : 30

Because the output is not "-1" maybe.

We are investigating the issue.

So that hackers stay away?

Yes, I did.

36015253

The tests are not final. All the solutions will be re-tested on successful hacks after the hacking finishes. One of the points of competitive programming is that you should test your solutions better yourself.

really weird.

this comment also says the same. It seems like a lot of them would be hacked

Same thing happened to me in C.

SUBMISSION LINK:http://codeforces.net/contest/946/submission/36018053

It got accepted during the contest but now the same solution is giving "Wrong answer on test 1."

There is an "else if" missing in Line 15 in your code, without this "else if" the while loop breaks if the condition on Line 15 is not satisfied, however, your code won't pass even if you fixed this line because of the input constraints (10^18) and will give you TLE.

The right approach is to subtract the quotient of the division of a by 2*b from a and subtract the quotient of b by 2*a from b while you can instead of subtraction.

My AC Submission : Link

I did not solve it incontest and nor have I submitted it later, but pretty sure this is the solution (Confirmed by comparing it with accepted codes).

Basically notice that when you make the ith fibonacci string you already have a concatentation of F(1)...F(i-1) present so its F(i)...F(i-1)F(i-2)F(i-1)

An important intuition is that the number of occurences of the string s in F(1)...F(i) can be broken as number of occurences of some prefix of s in F(1)...F(i-1) and number of occurences of the remaining part of s in F(i). [We multiply these].

To do this, we maintain 2 types of DP. till[i][l][r] stores the number of ways to get s[l...r] as a subsequence till the ith fibonacci string. curr[i][l][r] stores the number of ways to get s[l...r] as a subsequence in the ith fibonacci string. Notice that for each way in till[i-1][l][m] we can match it with a way in curr[i][m+1][r]. Thus we multiply these. We apply a similar logic for the transition of curr. In simple terms these events are independent so they're multiplied.

Transition:
1. curr[i][l][r]+=curr[i-2][l][m]*curr[i-1][m+1][r] for all m in [l, r)
2. till[i][l][r]+=till[i-1][l][n]*curr[i][n+1][r] for all n in [l, r)

The final answer is till[x-1][0][n-1] if fibonacci index = x and length = n (0 based indexing)

Firstly, for every subsequence that is exactly the pattern, it will appear in 2^(positions free to the left) * 2^(positions free to the right).

left[i][l][r] = sum of 2^(positions free to the left) for every subsequence that contains exactly characters [l, r[ in the pattern

right[i][l][r] = sum of 2^(positions free to the right) for every subsequence that contains exactly characters [l, r[ in the pattern

sub[i][l][r] = number of subsequences that contains exactly characters [l, r[ in the pattern

sub[i][l][r] = (sum l <= m <= r of sub[i — 1][l][m] * sub[i — 2][m][r]) + sub[i — 1][l][r] + sub[i — 2][l][r]

left[i][l][r] = (sum l <= m <= r of left[i — 1][l][m] * sub[i — 2][m][r]) + 2^(size of f(i — 1)) * left[i — 2][l][r] + left[i — 1][l][r]

right[i][l][r] = (sum l <= m <= r of sub[i — 1][l][m] * right[i — 2][m][r]) + 2^(size of f(i — 2)) * right[i — 1][l][r] + right[i — 2][l][r]

The subsequence either has parts in f(i — 1) and f(i — 2) (the summation part) or is completely inside f(i — 1) or f(i — 2) (the rest). But this isn't the complete answer because it has 2^(one side). So the answer comes either from f(i — 1) and f(i — 2) or from one of them so:

ans[i] = ans[i — 1] * 2^(size of f(i — 2)) + ans[i — 2] * 2^(size of f(i — 1)) + (sum 0 < m < n of left[i — 1][0][m] * right[i — 2][m][n])

This was 2012 ACM ICPC World Finals problem D. A thorough explanation can be found at:

https://www.youtube.com/watch?v=dPFq4OLc-_Q

n = 500 with o(n ^ 3) just so fast. Btw, for O(n ^ 2), if the operations are not complicated, it works for n = 10000.

I wasted 10 minutes on this problem and got a penalty of 20 minutes because in my first submission i thought that I must maintain the order of the input and build a prefix sum array to know the best position of splitting :\

It says "in two sequences". I think this is pretty clear. They would say subsegment if they meant contiguous numbers

There was an issue in the checker, for some tests it returned OK instead of WA. It is really unfortunate but it is not a dramatic issue because you can always assume that there weren't such tests during a contest. Obviously, this argument can't be applied to wa1, though our estimated number of people affected is not that great. The participant can literally check his output for the sample case himself. We are still really sorry about it, the checker is fixed now and we will do our best in the following rounds to eliminate the possibility of similar mistakes.

For example, see this test case (note the z at the 2nd position)

azbcdefghijklmnopqrstuvwxyz

There is a subsequence valid if we delete the first z, but we didn't use any change operation so the correct output is:

azbcdefghijklmnopqrstuvwxyz

The output must contain the changes you made for the string to be ok, but deleting a character is not a "change".

Hope this helps you!

its doesnot give you point but if your rank is 300 and you hacked user with rank 299 you will be 299 so its good to hack

I was thinking to send a message to inform you but I said maybe he do it for a purpose.

Sum of 1)Time taken for all questions from start of question to accepted solution 2)20*no. of wrong submission

So u were waiting :D You became specialist. Congrats (Y). I became green :D

do you copy past codes like comments? so .. you are just green :/

my_comment