Tutorial is loading...

Problem author: KAN.

Tutorial is loading...

Problem author: KAN.

Tutorial is loading...

Problem author: pashka.

Tutorial is loading...

Problem author: pashka.

Tutorial is loading...

Problem author: Umqra.

Tutorial is loading...

Problem author: Endagorion.

Tutorial is loading...

Problem author: Um_nik.

Tutorial is loading...

Problem author: Um_nik.

in Div1 D, if O(26*n^2) solutions were intended to pass then time limit is too strict. if only O(n^2) solutions are intended to pass then why did you limit the number of different types to 26?

it's really unfair some people pass with O(26*n^2) solution while the others didn't.

I must admit this particular issue didn't get the attention it deserved. I didn't expect a lot of

O(kn^{2}) solutions to pass, and I also underestimated the effort needed to optimize toO(n^{2}). In an early stage I considered giving the problem with integers instead of latin letters, but it didn't seem quite elegant. Also, with Ω(n) different symbols allowed the solution would require Ω(n^{2}) memory which is a bit large and may lead to additional time expenses and/or optimizations required, especially if you use a slower/less efficient language.As for unfairness, I tend to disagree. If your solution passes the pretests in, say, ~1.5 seconds out of 2, then you know you're in for a sort of gamble and are free to optimize and resubmit (like tourist did). As for the discrepancy between asymptotically identical solutions, well, that can never be completely disposed of. (That said, I don't tend to diminish the oversight on my part.)

Actually $$$O(n)$$$ memory is enough

Another solution for B:

First we give each hobbit on the pillow. Now we distribute pillows to everyone who is close enough to Frodo, until we start giving pillows to all hobbits, or we do not run out of pillows. Create two variables that one of them would take the number of hobbits who needs pillows from left side, the other — from right. If you have not reached the border, increasing the value of the variable. At each step required Left + right + 1 pillow (for Frodo). If you follow the cycle we still have pillows, then add m / n to the answer. Sorry for my English

i did the exact same thing...gives me tle on case 6 code

Your code doesn't implement what Dey suggests. In order to do that with your current code (24051579), you should break the while loop when

ptr1 = 1 andptr2 =n, then add ⌊x/n⌋ to the answer.During contest, I also had done exactly the same, only difference was that I didn't break the loop when left = 1 and right = n, that's why I got TLE and I thought that this technique won't work. But your comment help me to get my solution ACCEPTED.

Thanks..

Problem D div 1:

Can anyone explain in a little bit more details the formula for the number of reachable strings with comp(...) = u? Why does that equation with number of combinations hold?

UPDNevermind, got itAn alternative

O(n^{2}) solution for D that isn't too complicated:As pointed out in the editorial, observe that a valid string is any string

usuch thatcomp(u) is a subsequence ofcomp(S), whereSis the input string. The general idea is to do a dp by "building" all the valid strings (somewhat similar to the classical edit-distance dp).Define the dp as

dp_{i, j}= number of ways to complete a partially-filled string, where:icharacters determined alreadyj-th character inSThen at each dp state (

i,j), we can advance todp(i+ 1,k), for some specific values ofk. In particular, these values ofkare the first occurrence of each letter in the substring ofSfrom [j,end]. This is because:comp(S). This maintains the fact that we are a subsequence.The answer is then the sum of all valid

dp_{0, k}. The definition of "validk" is the same as the one above.A naive implementation of this can run in

O(n^{3}). You can optimise this toO(n^{2}) by using a prefix-sum array.Accepted solution: 24045286

How to solve problem C if the problem asks for the largest element in the stack after all the operation instead of the top element?

Can anyone explain how this formula came in Div2B ((x-1+x-y)y)/2

suppose we have y beds on one side of Frodo and Frodo has x pillows (y <= x-1). his neighbor has to have at least x-1 pillows to be satisfied,then the neighbor of his neighbor has to have x-2 pillows to be satisfied and so on... so we calculate the number of pillows :

SUM = (x-1) + (x-2) + (x-3) + ... + (x-y+1) + (x-y)

SUM = (x-y) + (x-y+1) + ... + (x-3) + (x-2) + (x-1)

2 * SUM = (x-1+x-y) + (x-1+x-y) + .... + (x-1+x-y) + (x-1+x-y) ---> SUM = y((x-1+x-y))/2

can you explain about this formula came in div2b x*(x-1)/2+y-x+1 too?? thanks..

@WannabeStronger Sure, so if y > x-1 we should give at least x-1 pillows to Frodo's neighbor, x-2 pillows to the neighbor of his neighbor and so on till we give a hobbit one pillow and then we're done! the number of pillows would be : SUM = (x-1) + (x-2) + (x-3) + ... + 2 + 1

SUM = 1 + 2 + ... + (x-3) + (x-2) + (x-1)

2 * SUM = x + x + .... + x + x ---> SUM = ((x-1)*x)/2

Now everyone is satisfied but still there are some hobbits that don't have any pillows and as mentioned in the question

"Each hobbit needs a bed and at least one pillow to sleep". till now, we gave x-1 out of y hobbits at least one pillow so we should give the rest (y-(x-1)) at least one pillow too! so the overall number of pillows would be: ((x-1)*x)/2+y-(x-1)Another formula for the same number:

Let

tnbe the total number of pillows,y≤x- 1. As Borna pointed out:tn= (x- 1) + (x- 2) + (x- 3) + ... + (x- (y- 1)) + (x-y)Then, if we rearrange the summands:

tn= (x+x+x+ ... +x) - (1 + 2 + 3 + ... + (y- 1) +y)find sum from (x-y-1) ===> (x-1) =

(sum from 1 ==> (x-1) =(x-1)x/2) - (sum from 1 ==> (x-y-1)=(x-y-1)(x-y)/2)

= 2yx-y-y^2/2

=y(2*x-1-y)/2

C can also be easily solved with sqrt decomposition. We can create array and store the operations according to their positions. Then we split the whole array into sqrt(N) blocks, and maintain the biggest difference between push() and pop() operations in each block. We only need to change one block after a new query. To find the answer, we can just iterate over the blocks from right to left and find the first block, starting from which the difference is positive.

To understand it better, you can have a look at my code: http://codeforces.com/contest/759/submission/24052265

Problem div1 D can be solved without prefix sums or any other stupid optimization in as well. Code

congrats for the selection of world finals

DIV.2 B Shouldn't the question be "n-1 hobbits are planning to spend the night at Frodo's house" rather than "n hobbits" ???

Yes, you're right. Perhaps he's a hobbit too!

756A — Pavel and barbecue and if bi equals 1 then he reverses it. this word show all skewers reverse or one skewer reverse ? l am misunderstand.

If

b[i] = = 1 the skewer at positioniwill reverse (and then move to positionp[i]).i have a test case for barbeque prob (div2 prob C) 4 2 3 4 2 0 1 0 0

i checked many accepted codes everyone is giving ans as 0 , whereas the ans should be 1 i.e 2 3 4 2 should be 2 3 4 1 can anyone tell me why these codes are accepted ?

2 3 4 2 is not a permutation

Yup thanks got ur point .

Imagine we have 5 skewers:

abcde. What happens with a skewerewhen we move skewerato the place where skewereis located?ewould move to a position determined by P.Each second the skewers at every i will move to respective Pi. Since P is a permutation, There will always be only one skewer at any i at any time.

How is that? If you read statement — Pavel moves skewers (skewers aren't moving by themselves, right?).

There is no such info in the statement. Instead, the statement says that in

onesecond we move onlyoneskewer. So, according to the statement, after we moveato the position ofe, we get the following configuration:abcde⟶bcdea.Is my reasoning faulted?

Each second Pavel move skewer on position i to position pi, and if bi equals 1 then he reverses it.Since they didnt mention which 'i' will be moved, I interpreted it as he will move all 'i' to their respective pi in one second.

Can you elaborate a bit — I don't understand this part.

How can he move

allskewers in one second if it wasexplicitlysaid in the problem description that he moves exactlyoneskewer in one second? Not 2 skewers, not 3 skewers, but exactly 1 skewer.Nevermind, it seems your interpretation is right.

Back to the original question, e would be in the same position along with the other skewer since they said it's alright if total time can be >=2n which implies repeated positions are fine.

This is also wrong. Here is why.

Let's assume that we allow for several skewers to be on the same place, i.e. we allow the following configuration:

■

bcde■■■■

aThen there is no way for the following sentence to be meaningful:

There are now 2 different skewers in the last

positionand we don't know which oneto choosein order to move it to positionp_{i}.The choice is yours to make. Basically end goal is to move each skewer to all 2n positions. The order you do it in doesn't matter.

Now I understand. Thank you! :)

In Div2 B editorial "Suppose there are y beds on one side of Frodo" , one side means left side or right side ? Can you please help me to understand

This also had me a little confused. I ended up assuming that after I moved a to e, I immediately started moving e to it's position and so on for all other skewers.

760B why is Y ???

Can someone please give some more hints on Div1 C?

can anyone tell me in this test case of "Travel card" problem 10 13 45 46 60 103 115 126 150 256 516

Output

20 20 10 0 20 0 0 20 20 10

why ans at trip starting from 60th minute is 20 why it can't be zero

it is 0.

The first line of input contains integer number n (1 ≤ n ≤ 105) — the number of trips made by passenger.So the first number, 10, it's the number of tripsthanx i got it

can you please tell me trip starting from 115th and 126th minute is why 0?

can you please tell me trip starting from 115th and 126th minute is why 0?

Can any one please explain analysis to problem E? The above editorial is quite vague. For example,

What is the relation/difference between k and pref?

What is D? a[pref], a[k], a[n] or a[1]*..*a[n]?

"sz is the size of the new layer" -> what is layer? all adjacent ai = 1?

What is Di?

What is the editorial is trying to show is that the state space is , particularly around 20 times , this is because when you are evaluating dp[i][x], i.e. if you are at ith denomination say

D, you must have already summedm%Dinto your sum, because that can not be added to the sum while processingi..ndenomination. So, let S be the sum of all denominations from 1..i, so, for this layer( i.e. denomination) valid values of x are onlypD+m%Dwhere p varies from 1...S/D. You can see that sum over thisS/Dis bounded. Correct me if I am wrong.FOR DIV2 B : Can anyone explain how those two formula came ? : and

For Div 1 C, what does the author means when he says "Look at the operations in reverse order"? Is it decreasing p_i or is it the actually the queries we are given in the input, going from bottom to top?

There's a very short algorithm for D using

O(n^{2}) time andO(kn) space that I haven't seen mentioned. Let`a[i]`

be the number of strings of length`i`

(using the prefix we have processed so far). Let`p[c][i]`

be the value that`a[i]`

had after the last time that character`c`

occurred. For each character`c`

in the string, we update`a`

with the amounts of new strings that end with the character`c`

, which are exactly the strings that ended with a letter other than`c`

(calculated by`p[c][i] - a[i]`

for each length`i`

) appended with any positive number of copies of`c`

. Then we copy`a`

into`p[c]`

. CodeO(log^{2}m) seems to be a little large form≤ 10^{10000}sincem≤ 10^{10000}seems to be suitable forO(logm(log^{2}(logm)))Editorial for div1 B please?

It can be solved using dynamic programming, as we need to find minimum cost for each

ithtrip, as there are 3 types of tickets so there are3 ways.As we have to take the minimum cost, so we will take minimum of all these 3 and hence the required ans will be dp[i] — dp[i-1], as we have to give the difference (a-b).

Refer this submission for more clarity. :)

Div1C can also be solved in O(mlogm) just using segment tree. (not using lazy propagation)

For segment tree, store sum and maximum suffix sum on each node without reversing the operations.

Updating query takes O(logm) time.

For answering query, make a function find(val, id) which finds the position of rightmost suffix which has suffix sum bigger than 'val' in corresponding node. If right child's maximum suffix sum is bigger than 'val', recursively find answer at right child. Else, recursively find answer at left child, but this time 'val' becomes 'val' — 'right child sum'.

For details, look at AC solution — 29482992