Recent actions
0

when you delete them ,you may get a bigger num.

   a                b     c    d   e                   f 
 ____|________________|_____|__|___|_____________________|_

Given it as a axis, when you choose c,d as the minimum pairs ,the remain {a,b,e,f}->you choose b-e but the [abcdef] minimum is |bc|+|de|<|be| but you alg got |cd|+|be|,that is greater than |bc|+|de|

It is but at the same time it isn't because the way you divide the queries you want the answer is:

  1. online

  2. not in buckets of size sqrt(n) for the left pointer

Isn't it similar to what we do in Mo's Algorithm?

The wait is finally over :p

Created or updated the text

It's been 2 days...and still no tutorial...

Seems Barcelona Bootcamp activities are not getting concluded.

to solve this problem we must figure out that every time we must discover the caves that have discovered mimimum times,so to compute the answer just sum up the treasure is at from [0,n-1] caves. suppose treasure is at x caves the expeced day we need is

sigama((x/k+1)*0.5+(x/k+n/k+1)*0.5^2+...(x/k+i*n/k+1)*0.5^(i+1))/n i is from 0 to oo .x is from 0 to n-1

it can be simplified sigma(x/k)/n+1+k*n/(2^k-1)^2+i*n/k/2^i+1 is from [0,k-1], x is from [0,n-1]...

seems that I have not made mistake, now I'll try it....

sigama (i*n/k/(2^(i+1)) consider i*n/k==j then (j*k-1)/n+1 <=i<=((j+1)*k-1)/n

so it can be write as sigma (j/sigma(2^(i+1)),(j*k-1)/n+1<=i<=((j+1)*k-1)/n).

it can be Simplification as sigma (j*((0.5^((j*k-1)/n+1)-0.5^((j+1)*k-1)/n))) we need to discuss first and last item. frome middle,it can be write as

sigma (j+1-j)*0.5^((j*k-1)/n+1) == 0.5^((j*k-1)/n+1) j is from [0,n-1] subtract O(1) items..

(j*k-1)/n can be write as ((j*k-1)-(j*k-1)%n)/n ,now it is quite easy to compute now because j is from [0,n-1]..

point it out if I have missed something...

Hey, could you elaborate? I don't see how to calculate that, and I also don't see how that suffices to solve the problem.

any proof?

Never waited so long for the editorials.

I think there is O(log(n)) solution, we should compute

sigma((i*n/k)/2^(i+1)) 0<=i<=k-1. this can be solved by Euclidean algorithm

Neo Essential oils — I have note this lecture it's like presentation. But i like it.

It makes sense~nice

When will the editorial be published?

I hope that finding such ideas will be easier with practice :)

I hope so too! :-)

If we merge string s1 and string s2, new substring have to contain part of string s1 and string s2. So we can place it only on the k — 1 last positions of string s1 (otherwise it would be completely in string s1 or string s2). So we can't create more than k — 1 new substrings.

When there is 0000 problem we have solution.

When we have 3 zeros problem we only have to have any task that '1 team' doesn't know. If there is none, we answer NO.

When all problems has at most 2 zeros we can't take 1 zero problem, because there can't be less zeros than ones globally in chosen problems.

When we have 0011&1100 or 0101&1010 or 0110&1001 we have solution. When we don't have any pair of that type, we can have at most one number from each pair, so 1, 2 or 3 of them. One won't work. When we take 2. problems, always one team will know all 2. When we take 3 problems always one team will know at least 2. So 0011&1100, 0101&1010, 0110&1001 are only solutions in that case.

So we accept when we have one pair from following numbers (+ column permutations)

0000 (this with itself makes zero)

0001 and xxx0

0011 and 1100

This works cause when correct problem choice is possible, there exists set fulfilling requirements with at most 2 problems. And a[i]&a[j]==0 does the same.

Then, how do we get the upper limit for k ? According to your explanation, the maximum value of k can be 100.

Why can't we create more than k new substrings while merging two strings?

I solved it with exactly the same method. I also want to know the proof.

Can anyone please tell me why my solution for C works. First of all I treat each problem as binary number. Then I push all the numbers into a vector a. Since there are at most 16 numbers so I just check if there are any numbers a[i]&a[j]==0. If exist then yes, if not then no. I don't know why I thought up such an idea but I can't find any case to disprove it. http://codeforces.com/contest/868/submission/31036399

You're welcome. I'm glad I could help.

As regards simple concepts — that's almost always the case with short contests. I used to call these tasks tricky as they really require to get a trick — sometimes an observation, sometimes just restating the problem in a much simpler way, sometimes reducing to something simpler. I hope that finding such ideas will be easier with practice :)

Thank you so much for the explanation! It makes so much more sense now. The worst part is that it is a very simple concept as well, isn't it? I really must stop overthinking things. Thank you again for taking the time to lay it out so well — it really helped me understand the solution.

can u please explain the whole solution?

Resolving to compose an impeccable exposition paper is constantly unnerving. All things considered, an immaculate thesis paper incorporates various inquires about,Dissertation Help Online encounters that can feel you exhausted or stalling out.

So seems like my solution is wrong, just change the maximum preserved length of string may result in wrong answer. I'm just lucky.

You can check here: 31053045 (change L to something else, my solution in contest equals L = 500)

Set it to 500, 550, 700, 1000, 567, 543, 510, 100000 will get AC.

However, set it to 400, 475, 499, 501, 600, 456, 511, 512, 10000 will get WA in various tests.

Just realized this when practicing problem E:

" the criminals can move with arbitrary large speed "

My brain during the contest: OH SHIT, ARBITARY SPEED SPECIFIED BY THE INPUT? NOPE NOPE NOPE NOPE NOPE JUMP TO F.

Jokes aside, is there anyway to solve the problem in decent complexity with a bounded velocity for the criminals?

You will receive rating updates as long as you have made submissions during the contest, even if none of them are successful.

Wow thanks, man. It's very clear now.

Let's see the movement of both pointers:

Right pointer: when it gets to [l, r], it comes from r + 1, goes to the mid, solves [l, mid — 1] ending in mid — 1, solves[mid + 1, r] ending in r (so when it comes back, it is in mid — 1 from the previous call). So for each range [l, r] it will move O((r — l) / 2). If you take the sum of every range it will be O(n*logn)

Left pointer: when it gets to [l, r] assume that it starts on optr, it will move on [optl, optr] to find the answer, move back to the optimum point, solve the left part (going back on the optimum point after the call), go back to the optr and solve the right part. So for every range you take the 2 * (optr — optl) and that's O(n*logn)

The idea is the same as parallel binary search for the complexity of moving the pointers.

Why go function doesn't change the complexity of your solution?. I realized that D&Q could work but I couldn't come up with an idea to calculate the cost..

It's not like key difficulty of this problem lies in reducing to case gcd(n,k)=1 by dividing by common divisor and then there are just few simple formulas...

That was not a lecture, just some random presentation.

Is there a glitch, every unrated person is given a rating of 1378 (Even unsuccessful submissions ), please explain.

Why downvotes? I wasn't fu**ing with you guys. Post above + this prove that tests were weak.

Good day to you,

In my opinion hacking with copy-pase (vs.) hacking with "flash" might pretty different. Hacking flash is mostly about observation & finding a mistake (somewhere). If copy-paste would be allowed, one could easily create stress-tests and hack the solution without even looking at the code :)

Yes, this have some drawbacks, yet I guess this might be the main reason.

Good Luck & Have Beautiful Day! ^_^

Why don't we want people to copy-paste solution :P

I think for problems such as B, it would be very beneficial to the sanity of most people to allow copy-pasting for hacking :P

What the heck ._.? Setters should get familiar with DeBruijn words. My bound was 12, but if I'm not mistaken we can get even 13 if concatenation of words on input is DeBruijn's word of order 13.

EDIT: Ahhh, I see that there was a limit of total length up to 100. My upper bound of 12 works. That makes it harder to construct cases, but 6 is still easily breakable.

Ha ha.. I tried every possible case. Took 40 minute to code.

That is the biggest submission i have ever seen.

Yes, you are right it was my mistake)

My code was checking initial values in strings and then was setting prefixes and sufixes only if the concatenated strings were remembered as whole strings. If they were not remembered as whole strings (it means their length was greater than 109) it just checked new strings on the concatenation of sufix and prefix of these strings and do not set new prefix and suffix. Which means that if this string will be concatenated in future, it will present empty prefix and sufix.

It fails this test:

4
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
4
1 2
3 4
5 6
7 1

BTW, it is also interesting that you could have stored all the generated strings up to 109 length and it would fit within memory limit: 254500 KB

Edit: I corrected that bug during the contest and lost 180 points. It showed up that it was not worth it. Very mean as usually when I do not notice such bugs my solutions fail and when I noticed them, they are not caught by systest...

Edit2: Test exceedes input size but you can get the idea of the problem. Submission: http://codeforces.com/contest/868/submission/31030570

Edit3: When I fixed the bug and I tried 109 upper_bound it exceeded memory limit but I'm pretty sure something around 90 would fit. Don't want to check it though.

Andrey Stankevich is the best teacher during the bootcamp, does anybody have any English lectures that are downloadable from him?

They used at least 2 different templates. Not to mention Tabs vs Spaces.

31016987 31017265

I did.. :p 31042120

Every second, all hands move in clockwise direction. In order to measure this precisely I divided the clock into 12*60*60 units (the total number of seconds in the whole turn on the clock — 60 seconds in minute * 60 minutes in hour * 12 hours in total). Now you can observe that with every second hour hand moves by one such unit. Minute hand completes the whole turn within an hour so you divide 12*60*60/60*60 = 12 units with every second. Second hand completes the whole turn within a minute, so you divide 12*60*60/60 = 720 units.

Once you scale the values, you have precise integer values of hands positions. You can then compare these values against t1 and t2 (you have to scale them too by *= 3600). The comparison is simple — just check if none of the hands block one way or another:

http://codeforces.com/contest/868/submission/31017176

MaxL isn't 10^4, each step you can add the last two strings, then maxL is 2^m

How could snowy_smile solve pF in two minutes...?

submission history

I used such idea. For K you should get 2^K different substrings with length K. Let's denote that we have string S with L length.

Count of different substrings with length K for string with size L are equal L — K + 1.

Then we have next formula: 2^K <= L — K + 1 => 2^K + K — 1 <= L

maxL ~ 10^4 (each step you add string with size 100)

=> maxK ~ log2(10^4) ~ 14

Correct me, if I'm wrong.

You can compute the value dp[c][v] using a binary search. Criminals want to be found as late as possible, therefore you look for the biggest time that is possible for the criminals to archive (using a good spreading).

Checking if a specific time >= M is possible, you simply place as many criminals as possible at each leaf, such that either choice of the policeman ends up in a time >= M. (placing x criminals at leaf u takes cost[v][u] + dp[c-x][u] time).

Here is my implementation: 31030667 (variable naming is quite messy, but I hope you get the idea)

Could you elaborate on the DP relations? What are the transitions from dp[c][v]? I tried exactly this state but the transitions got messy. :\

How to arrive at the maximum number K in the question D ???

for(int i = m; i > cap + 1; i--){ tmp += arr[a[i]]; arr[a[i]]++; }

This makes your code O(n^2) for some case. Check the go function here to optimize it: http://codeforces.com/contest/868/submission/31021372

That's hilatious. Mine was about 10x as slow, long, and complex as yours and also passed.

http://codeforces.com/contest/868/submission/31028937

your go function is awesome! you're so smart

Thank you! charcoal explained the logic to me — now I see why my understanding itself was wrong!

It's actually still true for k=5.

Assume there is a problem used on the test which is unknown to exactly three teams. (the four and five cases are easier.) Call them teams 0, 1, 2.

If some other problem is unknown by teams 3 and 4, then the answer is YES and we can use these two problems.

Otherwise, each of the other problems will have been seen by at least one of team 3 and 4. Then we cannot make a test where teams 3 and 4 have seen at most half the questions using the original question. (and we can remove it)

NO

Ahhh! Now I get it — stupid mistake from my side in understanding the problem. So, basically, the problem set size keeps changing depending on how many we are considering at one time, but I was checking against a fixed number (one of my several mistakes in this problem). Also, this explains why some solutions I had checked were enumerating subsets. Hmmm.

And, no, your English is absolutely topnotch. Thank you for the explanation! It helped a lot! :-)

I get it with reading your code. Thanks so much.

I will give simple example for given test case.

For given problem A = {1,2,3} you can choose some of them.

Let assume that we get two problem S = {1,2} ( |S| = 2 )

Then, Team 1 know problem 1,2, Team 2 know problem 2, Team 3 know problem 1,2, Team 4 know problem 1

For this, Team 1 know 2 problem, which is greater than |S|/2. So this is invalid case.

For all nonempty problem set, {1},{2},{3},{1,2},{2,3},{1,3},{1,2,3} ,they are invalid. Get it?

Sorry for my English. I'm not the native, so i guess there are so many grammar error and word error.

It's easy to see, that the criminals will hide at the leaf nodes. And so the policeman will catch each criminal at leaf nodes.

Perform dynamic programming: dp[c][v] = time to catch c criminals, if the policeman is currently at a leaf node v.

Is that enough? Computing these values is not trivial.

Thanks for the reply, charcoal. I think there was some problem with the formatting — fixed it. The given example has 3 problems with 4 teams in total. Can you please explain this test case (or have I interpreted your answer incorrectly?)

I too used Divide and conquer optimization but got TLE ... Can you check this once? 31025909

You can solve it just by brute force with bit. You don't have to use dp.

Is bitmask dp required for solving C?

What about this test case?

3 4
1 0 1 1
1 1 1 0
0 1 0 1

Okay, just to be clear on this — so the whole question depends on the system being dynamic, not static right? Is that correct? My attempted solution tried finding opens paths in the clockwise and anti-clockwise directions consider the point in time in which t1 and t2 are considered. That worked for the sample cases, but failed miserably in the pretests.

Could you please go into a bit more detail about your logic? That would help us beginners a lot. Thanks!

You misunderstand problem.

The number of known problem for each team should be less than or equal to half of total number of problem in problem set.

For given example, total number of problem in problem set ( T ) is 1.

The second team know 1 problem, but this value is greater than T/2.

So given example is invalid.

Can anyone give me hint for problem E?

Hey all,

In the contest, I got hacked by the following test case (Problem C — Qualifications Round):

3 4
1 0 1 1
1 1 1 0
0 1 0 1

The answer for this should be "YES", isn't it? Question 3 only has 2 teams which know the solution, and that is less than or equal to half of k=4. Am I missing something here? (The judge says that the correct answer is "NO").

Thanks!

Had you slept during the contest ? That was not a good decision

Why it never makes sense to add two same problems in terms of teams who know it? Maybe adding that problem will give us additional 0 to one team and ones to others which wont make problem.

You can divide clock like this guys said, but it wasnt necessary. I only converted hours to seconds: hours = 5*hours + minutes/60 + second/3600. and minutes to seconds: minutes = seconds/60 You must work with doubles,but suprisingly it wasnt problem, i got AC without having precision troubles.

Just imagine a clock. At exactly 3 o'clock the hour hand is at the position of 3. When one minute and 13 seconds has past, the hand is a bit further than position 3. So it is between 3 and 4.

ok nvm i know now i dont have to

ok i get it, as the real clock looks like.. but how can i calculate how far is the hand ahead of it's value?

Because seconds hand is at 13, minute hand is little ahead of 1. Because minute hand is a little ahead of 1, hour hand is a little ahead of 3. Hence answer is NO.

Can someone explain how to solve D?

How to solve F?

Guys i dont get these statement with B problem...

4th pretest : 10 22 59 6 10 ANS = YES

Ok, there is a path between 6th hour and 10th hour, even if our point is directly on the hour hand we can get it

But 5th pretest : 3 1 13 12 3 ANS = NO

But why? Here there's the same situation in my opinion.. there is a path between 12th hour and 3rd hour, but we just have to go backwards and our point is also directly on the hour hand just like in 4th pretest...

why answers are different? cannot we go backwards? The task statement says that "he doesn't have to move forward only: in these circumstances time has no direction"

What do not i understand?

how to solve D?

The pretests seem too weak in D , I didn't memoize my DP hence my complexity should have been something like 2Q * (Something related to K) and Q was upto 100.

You should see my solution then.

ohh thanks i missed it :(

The hour and minute hands will be a bit ahead of 10, so it is a valid test case.

Sent same solution with other compiler and it got accepted.

And it really passed system tests XD

Is it correct? 31024676

B 46 test case: 10 50 59 9 10 is it ok ??? bcz in statement it i found Misha's position and the target time do not coincide with the position of any hand. so how it becomes a valid case ?

can you please explain this one also !

Tests to this task were very weak...

Tests to D are very weak. My buggy code got accepted after the contest.

Then you did not solve it.

I just divided the clock into 12*60*60. Hour hand moves by 1 such unit every second. Minute hand moves by 12 such units every second. Second hand moves by 720 such units every second.

Then just compare these values with t1*3600 and t2*3600 and that's it.

how to solve B ? i have tried it but failed on test 56 (:

No need for dp — just brute everything.

I've just got AC using 6 as upper bound (and I believe 6 is very easy to achieve so upper bound can't be less)

Yeah, here is a counter-example to the statement "size of answer <= 2" if we allow k = 6:

4 6
1 1 1 0 0 0
1 0 0 1 1 0
0 1 0 1 0 1
0 0 1 0 1 1

Each two distinct teams have a common known problem, but if we take all four, each problem is known by exactly two teams.

I can't figure out what's with k = 5 though.