zscoder watches anime to make up for that

This isn't a convex hull optimization, but I do think it uses it (dp[n] = dp[i] + smth * (n-i) type) but if it should work I think it will be something like N log N (maybe some more logs)

Is it possible to apply wqs on this task to solve K <= 100000 as well? (Something like, let the score for a set S of lifeguards fired be [amount we can cover + X * len(S)], and then binary search on X)?

I'm not sure if this would work, since the cost function here is linear rather than quadratic.

I don't see why you can ignore the subtraction of 1 in your proof, but radoslav11 has come up with an informal one, which with some care can probably be formalised.

Consider a number X = Y + Z, where Y is even and Z = 1 or 0. Now, when we //= 2, we get X//2 = Y/2. When we /2, we get X/2 = Y/2 + Z/2. Their difference will be Z/2. (Either 0 or 1/2).

Now, we can subtract K, and we will get something like X//2-K = C, while X/2-K = C+Z/2 (to be precise, C = Y/2-K, but who cares). Now, we do a similar thing, divide C into D + E, where D is even and E = 1 or 0. You will get something like D+E+Z/2. And when we compare /2 vs //2, we will get something like a difference of Z/4+E/2.

And if you keep on going, you will get some A/2+B/4+C/8+..., which is always less than 1, so taking floor is okay.

How to solve it after this? It seems now it reduces to: count the number of subarrays with exactly 0 or 2 instances of every element.

Seems like the site is in Russian... where can I find the links to the contest? Editorials? Who are these problems written by?

And can you make graph of y-2x vs round number? ;)

orz, thanks so much! Needless to say, you have my upvote :)

So from my understanding, since I am accessing last[k][1], last[k][2], ..., last[k][k], the computer "mindlessly" expects me to access last[k][stuff] every time, whereas last[1][k], last[2][k], ..., will cause a lot of cache miss penalty.

So then, if I'm right, why didn't much change when I tried the same thing for the "dp" array? It seems to be accessing dp[1][k%2], dp[2][k%2], ..., and I hope that based on what I wrote before, dp[k%2][1], dp[k%2][2], ..., would be a faster option.

For fun, could you share the probabilistic method?

I've had this problem for a while, and most probably it's solvable with Digit DP. Maybe it's not, but I haven't found a solution:

Given a integer X, find the number of integers i in [l, r] such that i ≤ X and rev(i) ≤ X, where rev(i) is the number formed by reversing the digits of i. For example, rev(1560) = 651 and rev(156) = 651 (not 6510, 65100, etc)

Unfortunately I can remember neither the source nor the limits, but probably X < 10¹⁸ or something.

Gale-Ryser may work if your graph is bipartite.

The blog's disappeared from the recent actions feed, but I still haven't found anything toward a solution. Anything would be great :)

Oh, I meant the version without jumps. Is there name for that?

Is there a name for the type of function in G? It's some combination of Sigmoid and ReLU, but I couldn't find it's name...

Sorry, ignore it! But I can't delete it :)

BTW, are there any interesting problems that use some properties of this graph?

Oh, thank you very much, I see now. I overlooked something so simple :)

Can you please elaborate on it, send_nodes :^)

I am very curious how you change the DP to be k^2 log k

he watches boku no pico

What website you used to make such great pictures like this? And is the girl customizable? :')

Could you tell me the order of removing to make it fail?

I tried multiple removals, all of which succeeded.

Edit: Never mind, I got it. Thanks! Removal of 2 creates symmetric 4-cliqueless figure.

Auto comment: topic has been updated by minimario (previous revision, new revision, compare).

Here is an interesting solution, which doesn't involve 2D. Maybe it works, maybe it doesn't, because I haven't gotten a chance to submit: moo

Let's call the left cows a_i and the right cows b_i. Now, let p_i = a_bi. Our goal is to count the number of pairs i < j such that p_i > p_j and |b_i - b_j| > k.

We use divide and conquer. At some step, we consider some pairs such that l ≤ i < j ≤ r. Now, from conquer we only need to count the pairs where and . Let's sort all the indices from l to r by b value, and process them least to greatest. Maintain 2 BIT's storing the p values (one for [l, mid] and one for (mid, r]) and query appropriately.

To get to the udder side...

From a problemsetting perspective, I'd like to ask ilya_the_lamer about how you wrote a checker for this problem, and how this affected the system testing.

By the way, writing the checker surely seems harder than the original problem, and I'm assuming you wrote a n log n (take all the rectangles of some color, do horizontal/vertical segments independently, check for overlap). I wonder how running O(n log n) for n=500000 on ~50 test cases for a bunch of programs affected this system testing. It seemed pretty fast to me, just curious how it ran so fast in this way!

I'm just curious, what's the algorithm you used to determine the best problem? Is it by solve rate, difficulty, etc?

And how to determine the "cutoffs" for easy/med/hard? (If some cutoff values are used to determine these problems)

Looks like there needs to be at least one for every contest...

What complexity do you want it? And does 1--2--1--2 count as a "path" between 1 and 2? (i.e., are cycles allowed in the path)

Edit: AC'd with complexity . Is there better?

I solved the last one before, it's really amazing and unexpected!

Consider a range of numbers. Let's remove pairs of unequal numbers (arbitrarily) until all the numbers are the same. (Or there are no numbers left). There will be at most 1 number left. Can any other numbers be dominating in this range?

Now, you can use a segment tree to simulate this process. For each node, store some information about the number remaining after cancelling out unequal numbers.

Here's the code for combine (spoiler!)

I think that the same thing as the editorial will work here. For each edge, add w * min(a, b), where a and b are the size of the components when we remove the edge.

Thanks, it's really cool and I got AC with this algo. It's really beautiful!

So what's the solution to E or F?

40% for E seems pretty trivial...but the rest of the problem seems really hard!

Have you realised this was posted before the end of the contest?

Reflect the box over the top and right sides, with the bottom left corner at (0, 0). So in the 3rd sample, all the boxes have left corners (7x, 4y). Note that the path of the ball is then equivalent to y = x. We can find the stopping point, which is the top right corner of some box, in the form (mk, nl) for some (k, l). It's also on the path, so mk = nl, and the first hit is at (lcm(m, n), lcm(m, n)).

With some experimentation, you can see that for some point (x, y), it's also equal to all the points ( ± x + 2nk,  ± y + 2ml) for some (k, l). (In each box, there's 1 point). And because it's on x = y, we can use the 4 congruences

We find the minimum such a, and check if it's  ≤ lcm(m, n).

Thanks, it shaved about 100 ms. off my time. But I guess it doesn't really optimise it that much. New submission link here.

I.1 is the input, O.1 is the output. And if you could try to describe the method when you get AC, that'd be great!

Unfortunately became blue for the first time in over half a year :( D:

huh?

I love minimario too

I think, you are the reason Codeforces is "ridicilous". I cannot stand Codeforces either, and "MikeMirzanayov" too, why he hasn't banned you yet!

Oh, yes, I see it now. I thought of it before as simply function that is used in the ternary search, and didn't consider the combination of individual functions at all XD

Can somebody explain, in problem E, how the binary search works? For each z[i], ans(j) is some function that first increases and then decreases, but it's not strict? (It is the minimum of an increasing function and a decreasing function, so it either decreases or increases and then decreases)

I guess user rsalesc has explained to me the solution, so I will present it here:

Find any DFS tree of the graph (say 1-2, 2-5, 5-8, 5-3, 3-4 in the graph above). Now, each of the other edges will make a cycle using only the tree edges and that edge. For each edge, we can make a cycle. And for each cycle, we need one of those other edges. Therefore, the answer is the total number of non-tree edges. We can find the cycles with DFS and backtracking.

Well...how to solve Div 1. 250? I thought of Binary Search, but I couldn't find good way to check if something could be attained.

Really, here. Are you serious? I ask some question, and you reply with me for some random crappy fake method, pretending you can solve it?

It is not really needed for these trash kind of post. Maybe you can start participating in a contest, let me see you can solve some problems instead of wasting your time posting trash comment like this.

Perhaps you are on codeforces for fun, but people like I are here to learn something. So please start learning, respect for others.

Thanks!

Can somebody explain 623D, it's not on editorial...

Sorry, I accidentally click "Discard" button. Now it is recovered. Peace.

Sorry, I fixed it.

I did not realise, you cannot open inputs twice. So I open one input without having code completely done, and can't submit again haha

Lucky it is only the qualification round, so it does not matter that much as long as I can solve correct one more problem...

For each problem, you can only download the input once? Or is there way try again like in Google Code Jam...

I download once for A problem when I wasn't really ready, to check format~

Looks like some Div. 1 Coders' ratings are be affected...

|num| <= 20 and O(N) passes...

You are right. Is there method to make some idea like this would work? :P

I think there is much nicer/easier solution for problem C. I think it work?

Say you have the array elements a₁, a₂, ..., a_n. Then, call them sorted be b₁ ≤ b₂ ≤ ... ≤ b_n. Then, for each 1 ≤ i ≤ n, we check if a₁ + ... + a_i = b₁ + ... + b_i, and if so, we increment ct++. (If sum are equal, then element must be equal because it is the minimum possible sum). Then ct will be the answer.

Implementation: 14386133

I cannot understand, what you mean, the last k characters don't match? And I still cannot see the transitions...

After post on racism and PraveenDhinwa's comment "It could have qualified for one if the green coder would have got negative votes.", here we are.

Can somebody explain the method to solve Div 1. 444 problem?

The number of marbles in A + number of marbles in B is always equal to A+B; actually always A and -A (mod A+B). So when you double one pile, marbles will always be 2A and -2A (mod A+B).

Here is my Python code:

It say, "The link you followed may have expired, or the page may only be visible to an audience you're not in."?

Is it problem?

Add cout.precision(10);

Here is your AC code: 11868422

If w >= 4 and there are 17 weights, then the minimum number we can get (positive) is 4^16 — (1+4+...+4^15), more than 10^9. And it is clear that with more weights, the minimum is even more.

Since constraint is only 11, we can simply iterate over all possible combinations of bridges to build and then run a Floyd-Warshall on each of them to find the diameter. (By finding max of distance between 2 nodes)

Pretest are so weak, many people do not even try their code on max test. BTW, what is solution to that problem?

Only noticeable difference between two hacks is that there is \n character after swust_20131737's hack, which is probably the problem. Pressing enter key after the last character will probably allow it, the Successful Hacking Attempt. But I never seen this issue bring up before, so may be some differences in problem setter's checker code for this round.

(BTW, how you see \n character, is done by going to the 2 submissions, and double clicking the text (to "highlight" it))

153991: Image 154761: Image

Problem C has tag "dfs and similar"; does this only refer to calculating longest path or is there real way to solve with dfs?

tourist

Round is not even on front page after 5 hour after post...I wonder it, round is actually real?

No, they won Dress Rehearsal. 1% they win real contest xD

Because that way, he gets minus too, and it is no different from saying give me minus.

Is there a problem with submitting? Why can't I submit now?

Edit: It is fix.

All we have done is played simple trick on Codeforces as April Fools joke...what would April 1st be without a joke? :) And you want us banned? We have seen you cheat on contests, and haven't mentioned your ban yet!

We thought it would only be fun to do something like this: no harm intended!

...then trophies receive following PM:

We thought it would be quite boring if it weren't for a contest, so yes, it's happening :)

Yes, compilator changed from PyPy 3 to Python 3, but that change got me AC to problem B :) (It was TLE in PyPy, but same code got AC in Python)

What is solution to problem C...it seems like simple task but I cannot pass Pretest 4

It will be posted before the end of the week.

I asked t-mac, he said there are 3 SRM in April (times in EST):

April 9, 11am

April 17, 7am

April 27, 9pm

April SRM dates are still not up on the calendar...will there still be SRM in April? (Link)

It's another swarm of unrated competitors...

It's special contest to celebrate CF's 5 year anniversary? :)

Codeforces has had an excellent start, and I'm sure it will grow and continue to become better in the future!

On behalf of everyone, thank you for this wonderful site!

It's quite coincidence; sorry_dreamoon/qwerty787788 got second place in Codeforces and Topcoder

Maybe he really is the Petr...

...and the scoring is dynamic, just as we all had not hoped D:

Because problems of this round are hard to determine their difficulty, We will use Dynamic score for this round. Then the order of problems is from easy to hard by sense of me and testers.

When editorial is going to come? It will be interesting to see author's solutions to these problems :)

I think Pretest 6 has a string equal to original string, when problem says they must differ by exactly one position. Such as this, output should be "NO":

1 1

a

a

Doesn't using the current Div1-E as Div1-D make it harder, not easier? The D task will be hard as E task, and E task will be even harder!

Have you found yourself yet...

The system testing is delayed due to verifying test cases(not a technical reason or trouble in the judge server). We feel really sorry about this.

The problems are so hard, even round author can't solve them.

I think Codeforces is broken. Take a look at "Pay attention" area...

UPD: Already fixed.

What's wrong with system testing?

Why Petr try so hard to solve E instead of other problems? It lands him in 117th :/

Looks like he changed his username from clashofclans to Majid (and the name as well) during Codeforces New Year's Gift :(

Yes, screenshot of messages is here

Maybe we can write problem about it:

Input: First line has 5 integers, each describing number of points each problem is worth. Second line has 5 integers, number of submissions he will take until he gets the problem right. Third line has 5 integers, time it will take to solve each problem.

Output: Maximum possible score

The order you solve problems in is obviously not as important as your ability to solve these problems, but for fun, let's take a look at this problem for fun.

Let's assume that problems A, B, C are worth 500, 1000, 1500 points, respectively. Let's also say you solve A, B, C in x, y, z minutes, respectively.

Note that if you solve A, B, C at times a, b, c, you will get 500 - 2a + 1000 - 4b + 1500 - 6c = 3000 - 2a - 4b - 6c points.

If you follow the order A -> B -> C, they will be solved at times x, x + y, x + y + z, so your points value will be 3000 - 2x - 4(x + y) - 6(x + y + z) = 3000 - 12x - 10y - 6z

If you follow the order C -  > B -  > A, we will have A, B, C solved at times x + y + z, y + z, z, so your points value will be 3000 - 2(x + y + z) - 4(y + z) - 6z = 3000 - 2x - 6y - 12z

A -> C -> B will give points equal to 3000 - 12x - 4y - 10z

C -> A -> B will give points equal to 3000 - 6x - 4y - 12z

You can use this code to calculate which strategy is most optimal.

For example, when (x, y, z) = (5, 10, 20), A -> B -> C is the most optimal way to go.

What is wrong with the practise room; "Run System Test" does not work...

It's such sad story...after letting the top 3 places to dreamoons, liymsheep fails D him/herself and becomes 10th instead of 4th :(

Hopefully this will put the end of my blue colour; I hope to be purple again :)

Have to hope editorial is the opposite, however.

Do you mean problem B?