Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | tourist | 3805 |

2 | maroonrk | 3637 |

3 | Benq | 3513 |

4 | ecnerwala | 3506 |

5 | MiracleFaFa | 3466 |

6 | slime | 3428 |

7 | jiangly | 3415 |

8 | Radewoosh | 3399 |

9 | greenheadstrange | 3393 |

10 | djq_cpp | 3391 |

# | User | Contrib. |
---|---|---|

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 185 |

4 | Um_nik | 182 |

4 | YouKn0wWho | 182 |

6 | maroonrk | 170 |

7 | antontrygubO_o | 168 |

8 | errorgorn | 166 |

8 | kostka | 166 |

8 | SecondThread | 166 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/16/2022 18:51:24 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

For C,is there a way to get the maximal solution? :D

Can someone help me with understanding of problem E. When we fix

T, we need to know whether exista's, such that Sum of_{i}a=_{i}aanddp>_{ei, k, ai}T. For that, we finda's, such that Sum of_{i}a<=_{i}aanddp>_{ei, k, ai}T. So here we use, thatdp<=_{ei, k, x}dpif_{ei, k, y}x<=y, but I believe it's wrong. I will describe the graph below.5

1 2 1

1 3 1

1 4 1

2 5 1

Here dp

_{(1->2), 2, 1}= 4, while dp_{(1->2), 2, 2}= 1.I think we don't actually use

dp_{ei, k, x}≤dp_{ei, k, y},x≤y. We can leave the residual in our current node for example. Then we usedp_{ei, x, k}≤dp_{ei, x + s, k + s},x≤y,sis some non negative integer, which is true. I hope i didn't misunderstand something.Indeed, the value does not increase monotonically with $$$a_i$$$. In my opinion, we could regard $$$a$$$ as a resource. When ensuring that the value is greater than $$$T$$$, we need to spend as little $$$a_i$$$ on the current edge as possible (make the $$$a-a_i$$$ as large as possible). In this way, there will be more ways to allocate the remaining edges (although this is a comment a long time ago, but I still reply here, hoping to help people who encounter this problem like me in the future)

I read codes of problem D and can't understand them. In most of the codes, when string length exceed 1000 on concatenation, they consider only first and last 500 characters of the string and leave the rest. I don't understand why they are doing so. Shouldn't they try to keep the meeting point as that is the point where new strings will be formed. One such code doing this : http://codeforces.com/contest/868/submission/31066000

I deem what STD wanted to tell us is that the answer k will not exceed 9 and we may maintain arrays of distinct substrings,or bitset as we merge the two demanded strings.But in fact the solutions you mentioned seem a little different from the original solution,because these solution get ans from three strings(itself,left and right strings) for each query.Hmm...I have read similar codes from submissions so I put forward my idea here~

Can someone please elaborate how the maximum answer is 9 in DIV 2 D?

The editorial assumes 10 is the answer and tries to see after all queries, if the number of unique substrings of length 10 can reach 2^10.

At first it explains how many substrings of length 10 there are in the original strings. Assume input is one long string of length 100, maximum number of unique substrings of length 10 won't be more than 100.

Now we need to know after each query, whats the maximum amount of new substrings of length 10 that can be added each time.

When we concatenate two strings, the new substrings of length 10 must start in the first string and end in the second. If it started and ended in the first string, that means its not newly created (same with the second). The maximum amount of new substrings of length 10 for each query therefore is 9.

So we started with 100 unique substrings of length ten, each query added 9.

Maximum amount when done is 100 + 9 *100 which is less than 2 ^10. So 10 cant be a possible answer.

Why is the number of unique substrings after concatenating two strings is 100 +9?

Lets say two strings are there S1 and S2 of length 100. Both of them will have not more than 100 unique substrings of length 10. It is also possible that the 100 unique subtrings of S1 are not present in S2. So when we concatenate them we get a total of 100 (from S1) + 100(from S2) + 9(from border of two strings) unique substrings.

So if there are 100 such strings then the number of unique substrings can be: 100*100 + 9*100.

The input states that the total

sumlength of all strings in the beginning is 100. Then the maximum amount of unique length 10 substrings at start is 100 forallinput.So the only way there can be 100 unique substrings in both S1 and S2 is if minimum 100 of those 200 were created new. If they were created new its already accounted for.

Oh yes, thanks. Did not notice that :p

no problem :D

Nice explanation, really appreciable!!

Thanks for your explanation！

wonderful explanation

For problem F, shouldn't

j_{1}≤j_{2}since we must try partitioning at allxwherex<p(j_{2}) ≤j_{2}?In

Problem G, What is meant bysmoothest partition?According to wikipedia,In mathematical analysis, the smoothness of a function is a property measured by the number of derivatives it has which are continuous. A smooth function is a function that has derivatives of all orders everywhere in its domain. If this definition is correct , then how it is related to the problem.In Problem G Endagorion How E0 = (E5 / 2) + 1 ? where Ei is be the expected number of days to find the treasure in spot i. Can you elaborate how you got this.

On Div2C, the number of problems needed is at most 2, if k was bigger, lets say 6 or 8, would 2 be enough?

How is optimisation part O(nlogn) in F?

Edit: Got it

In div2C " if there is a good set of problems, then each of the problems in the set must be known to exactly two of the teams."

why is it so?

Can someone explain the proof elaborately?

In a good set, even problems of the form 0111 and 1000(for k=4) would work. Any pair of problems with bitwise AND=0 must work. I don't know why he wrote that.

Can you explain why he wrote that at most 2 problems will be sufficient else the answer does not exist?

can anyone explain problem c ??

C is really awesome idea. Three cases(let say k=4): 1. A certain problem is not known to all teams [0, 0, 0, 0] 2. Let say ith problem is known to only the jth team among other teams, if there exists a problem K, such that it is not known to jth team, then these problems (ith and kth) form a good set. 3. According to pigeon hole principle, suppose there are k problems in a good set then pi be the numbers of teams knowing the ith problem. There exists an answer only if sum(pi) over all i <= 2*k. Otherwise, a certain team definitely knows >=k/2 problems. Also pi in each case <=2. To prove that, let's say: 1110 0010 Here it violates p1=3>=2 so not possible. So finding a pair is enough since 1100 0011 1100 0011 here size 4 problem set also works but the minimum is size 2 which also possible, 1100 and 0011. These two are non-intersecting. To find that we can subtract a number from 1111 (15) to find the non-intersecting pair. Solution: https://codeforces.com/contest/868/submission/125541891