Div 1B solvable in single log complexity:

Use segment tree to record d for each position; additionally, keep track of the minimum d in a segment that is not yet visited.

Use interval tree to store all edges (keys are interval of start positions)

Now, modify "for each " step in Dijkstra's algorithm to

let be any edge s.t. ; delete edge (!)

Greedy property of shortest path problem guarantees the deletion to be correct. Therefore total complexity is O(VlogV + ElogE) = O(ElogE).

This also works fine on generalized, interval-to-interval edges.

Amazing. Seems that there must be an much much easier explanation of this problem. Could you tell that magic idea?

Read last sentence again: heap.push happens at most n times. It is fine to have multiple pops at once, but by aggregate analysis it is O(nlogn).

lol, this is also the first solution I come in mind. All you should do is reverse the input and it becomes a standard trie problem :D

PS: do not forget to add trailing zeroes at the front to fill up required length

Tip: information considering the length, or left endpoint of a group need not be stored; what happens as we move past a event point is just that cost of pushing down increases. So the only thing recorded is: at this point how much does push-down cost increase? That is good for implementation since only a pair (height, costincrement) is needed.

For simplicity, first subtract each number by their positions i, so we need to make the sequence non-decreasing.

Now, start from beginning. Each time a modification is needed, there are two options: raise the current position up or push elements before down. It should be noticed that for each position raising up happens at most one time (probably more than one unit though).

If nearest elements already form a equal sequence then all of them should be pushed down. However, pushing down n elements does not necessarily costs n -- some of them may be raised up before. For these elements pushing down actually contributes negative one per unit (for undoing raise). Furthermore, once some elements form a continuous equal sequence, they will be equal forever so we can view them as a group.

Now we are able to construct a solution. We start moving from position 2 all the way to the end. Once we move past a position some 'event' height will be recorded. There are three different situations:

1) a[i] = a[i-1]. In this case, position i simply merges with the previous group, and the cost of pushing down that group increases by 1.

2) a[i] > a[i-1]. We don't need to modify anything now; however an event point should be added at height a[i-1] for possible traceback afterwards -- when height is reduced back to a[i-1] two groups become one.

3) a[i] < a[i-1]. This is the only case we need an modification. Now, look for the cost for pushing down the previous group. As long as the cost does not exceed one (actually it never goes below one, you can prove it), it is worth doing.

i) If that is sufficient to lower a[i-1] to a[i], we are complete. Then the cost will increase by one.

ii) Otherwise, a[i] will be raised up. In this case, however, the cost will be reduced by one since when we push down position i afterwards, before it goes back to original value we are essentially undoing raise. Finally, we create an event point at original value of a[i]; when we reach that point later, cost of pushing down increases by 2 (from -1 to +1).

For implementation: store all event points in a heap(priority queue). When pushing down is performed, refer to the top(largest) value and update. Since each position adds at most one event point, total complexity is O(nlogn).

Problem 1c can be solved in O(nlogn) without dp.

I found myself trapped in some kind of (seemingly) paradox in problem E.

For each position i, we can get a probability pr[i] for returning to position 1. Obviously, pr[] is non-decreasing. Now there is a problem. We have 1-pr[i] probability to go back to position 1, but pr[i] is definitely not the probability you can get to destination (it is just the probability to get to i+1). However as the procedure is infinitely repeated until getting to the destination(on either side), so outside 1-pr[i] we must reach the other end.

Where is my fault in reasoning?

Vacuous truth

Actually, this is also the same diagram shown in iterative FFT (by the way, FFT and FWT are quite similar, only different in calculation step)

What is the intended solution for problem B with extension N=$10^9$? Can't get any idea for sublinear complexity on N.

Gold only for full scores...

Never imagined such contest :p

If the test data were stronger there might not be so many full scores and I might get a chance to get in international ranking :p

7 contestants from China got 300 :p

Although I got 100+100+63 which seems a good score, the competition is tooooooo tough :(((

I think of another approach(with also linear complexity and same amount of code and easy to proof)

First, fill the string according to the nearest constraint for each position. Second, run a string matching algorithm to see if they really matches.

Waiting for the official editorial...

The third problem is so difficult. I only came up with a very naive solution that uses balanced tree and heap, which runs in , obviously will get TLE

UPD: I've got the way to reduce a log factor. Notice that when an interval breaks we get two new intervals of same length or with difference 1. And it's easy to see that if every sub intervals break again there will be still at most two possible lengths. Then, we only need to record how many intervals have a certain length, while the exact place could be found further separately(the new subproblem is what is the K-th insertion for an interval originally have length x), also need to pay attention of that slight difference of one: one shorter interval appears at front may generate length N-1 and N, while a little bit longer one after it may got N and N+1, and we need to be especially careful when dealing that length N.

Find the longest path in a DAG(also need a union-find for equal cases). If its length equals N, then they are type 1...N respectively, the rest is simple.

No instant feedback?

How can you guarantee that the second tree has a depth of O(lgn)? It could be a chain also.

there was unofficial (still rated) events for VK Cup, why not this time?

Best problem E ever in Codeforces. No any complex ideas but very very very insightful

Is it still possible to solve problem 1B/2D, if we allow same number appearing multiple times?

They must be bottom Div 1 contestants. Solving A,B,C problems quickly is enough to get a good place in division combined contests.

What is the mysterious statement "Then one can prove that" in problem E editorial? I just can't get the proof. Many game problems are like that: some patterns not hard to be found yet when I want a mathematically correct answer(proof) rather than a simple AC code, then no one will help me.

I hope most rounds are on 18:00 MSK in the future. That 1-hour switch has really some impact on us(Chinese).

Usually, problem statements will be written in English, if the author wants it to be put in an international site.

You are a programming competitions addict when you type a single letter c in browser's address column then codeforces.com immediately pops up, followed by community.topcoder.com/tc

Please, do not refer any topic on Codeforces with politics. Contest is contest, politics is politics.

Although Ford-Fulkerson method with shortest augment implementation has complexity O(V²E), it is in practice faster than push-relabel method, and also easy to implement(about 15 lines for a recursive version, and 25 lines for a non-recursive one). That bound looks like not possible to reach, however complexity of push-relabel might be a tight bound.

int64 issues:

#ifdef LOCAL
typedef __int64 ll;
#else
typedef long long ll;
#endif

and, add -DLOCAL to your compiler.

3000 point E problem come back! Do you guys want to make a super hard problem that is even harder than Chinese IOIer's round?

In a previous round written by YuukaKazami, no one solved problem div2-E during the contest. However That problem is not much difficult now, because at that time suffix automaton was first introduced to handle string problems, so no one but the author knows it. And later YuukaKazami admitted that it is a fault, because he didn't know div.2 problems C,D,E must be div.1 A,B,C problems, otherwise it will be D.

But a div.2 only round can have such a difficult problem.. This round has set up a new record :p

Sad to see exponential expression :(( that means it is an NP Hard problem?

Will be a very good chance to increase rating for low div.1 users!

Remember Good Bye 2013? I solved only A,B,C(that means only A, if in separate divisions) and got +180(1720->1900)

However I can't participate :( The rearrangement of holiday makes that Sunday be a working day in China :(

Newly registered contestants are considered to have median place expectation at their first contest. It does not mean they really are considered to have zero rating.

I wonder who is the real person behind the handle worse. Maybe he holds two accounts, one (possibly in div.1) is for real competing, and this is only for a test or just for fun.

worse even knows Segment tree and Strongly connected components and other algorithms and data structures! That is much better than even many Blue coders!

Original Elo rating has been developed into smth that fix into multi participant environment, rather than the first version that only supports two person game. (Here the rating system is not exactly the same as in Chess or StarCraft)

And in one-on-one battles, it is impossible to get two participants with such a big difference compete in one game. But in multi participant, hundreds of people and possibly in a large rating interval are put together. There must be some changes.

less than infinite rounds, if he continue like this he will be higher than tourist because of an integer underflow and get 21474836xx rating XD

One way to proof an algorithm is, find something that is always true when the program iterates over. You need to: 1.prove that the condition is true before start; 2.proof iterations will not change it.

And it sounds very similar to Proof by Induction in math. Maybe some math proving guide is helpful too.

Wow. Seems like this topic is a huge success XD

Actually creating board games is a interest for us :D but we have never got such a complicated problem. Some previous problems are quite easy that someone who even doesn't know game theory, can come up with an answer by just using math/logic, within a single hour.

And we never expected to get a long lasting problem (And that's good! that means we can keep playing this game; If an optimal strategy for general case is found then why going on?)

Can you share some part of your searching method? I cannot get an idea better than brute-force search+AlphaBeta method

The intention that I post this problem is, in this problem, it's very hard to get split into smaller independent states: if the board can be divided into some independent set of smaller case it should be like

x 0
0 y

(where 0 denotes a zero matrix)

and looks like very hard to achieve that. And it's also hard to tell if two boards are equivalent. So either Grundy number or prune search doesn't work well.

Although I don't know much about Java, a similar case in C++ shows that you can't allocate more than 16MB dynamically in stack(not static). Maybe it's that problem.

If you allocates too much once you could get badAlloc

Stop ZLD! Why you create so many accounts for div.2!

ZLD_submit_for_practice1 OrzSKYDEC hzwerOrz hellp zld3794954

By choosing only base 2, 3, 5, 7 and 61 you can determine any number's primality under 10¹⁸ (sorry for my poor memory, maybe there are some minor mistakes, you may search for more details)

Using percentiles to measure cause some problem on Codeforces: a lot of users have 1 match and ~1750 rating :D

Maybe we should only count those who has participated in at least 1 Div.1 contest, or regular Div.2 participants.

I came up with "1." by the following reason: Almost everyone in div.1 knows how to avoid simple mistakes e.g. integer overflow. In fact if you want to hack a div.1 solution, you need fully understand what defender trys to do, rather than find a improper int in a code.

BTW, (#successful hacks + #FST) / (#accepted) will be a good choice for dynamic scoring (except problems D and E because probably only one or two submissions will be made in a room)

Two suggests:

1. Div.1 successful hacks should get more performance points(because really hard)

2. Problems with higher difficulty should get some bonus for hackers(because even harder than above)

I'm sure that after several of this post in the future, simple mistakes like integer overflow in Div.2 will reduce A LOT :D

And we will see how worse can push his rating down to ........ negative!?

EDIT: worse has achieved negative rating! May I say "congratulations" to him? :D

Yes. strlen() just keep going on until \0 is found

C++ string object holds more things than only a pointer to the front. So string::size() works in O(1) since it already knows where the string ends and only need a simple subtraction.

OMG. Again that's a problem to convince yourself "that brute force works in time".

After reading solution to problem C, I suddenly understood why we can update 1st type operation naively... just some idea of amortized analysis gave O(n log n) complexity for n operations :p

Wow. So early blog post

And I like the contest time which is a bit early than usual :D don't have to stay up to midnight :D

Oops, there was a contest out of schedule?

Didn't log in arena and missed :((

I'm just curious about why TC always asks a string for such 0/1 answer problem

I used a different approach: enumerate all pairs, calculate the midpoint, and use that midpoint as center.

But later I discovered that if the center is not a vertex, answer is 2. So I was just make things more complicated...

How to solve div.1 500? Sorry that I'm not familiar with string suffix structures.

I just saw many solutions get 490+ points and I guess it will be very tricky.

free IQTest doesn't look like what we will call that a IQ test (which always consists of puzzles with numbers and figures)

yeah. that stupid error require expression after >> operator

If Chinese students were allowed to participate in IOI multiple times, that record could be beaten :p However after 2005(?) Chinese informatics olympiad committee set up a rule that anyone are allowed to participate in IOI at most once, and that's why you can't see Chinese names in IOI Hall of Fame although China is the strongest team in IOI with no doubt.

Soooooooooo many contestants that out-of-competition participants have to use 4-digit room number :p

Maybe it is a record high register number for a single division contest :p

I think, if you want to get (relative) high rating on TC you need to think very fast (~5 min for problem A almost every time and you get ~2300 rating!) But here skill level and correctness are more important. Even you finish problems A and B very fast, you cannot get such high rating

Wow. Such a long contest

What's the format of contest? Does it follow standard ICPC rules?

EDIT: sorry, I've got a problem registering. The website wants information of "college/university" but I'm not a university student now. So what should I fill in the chart ?

In the test you given win[root]=false and lose[root]=false. Check that again!

A full structure of Trie should be a more bit representing "is some word ends here"

Solution of Div.2 hard problem:

First, if x =  = y, then obviously answer is 0. So assume x > y

Let rem = money left on day t, cur = candies left on day t (both taken at noon);

Initially rem = xmody, cur = xdivy.

Then, since x > y, after cur days Alice buys another cur candies, her money left will increase cur * (x - y), and let diff = cur * (x - y); Notice that if rem + diff ≥ y, Alice will actually buy more candies.

We will split into two cases then:

1. if rem + diff < y, Alice needs period = ⌈(y - rem) / diff⌉ times to iterate cur days until cur increases. In such case, cur only increases by 1 after period * cur days;

2. if rem + diff ≥ y, cur immediately increases after cur days, and because diff could be very large because cur will increase, we need modulars here. After cur days, Alice will get rem + diff additional money if she still buys only cur candies, so cur will increase by (rem + diff)divy, and rem = (rem + diff)%y.

The first case takes period * cur days, and second takes cur days. If days left < days to be taken, we should calculate the final result and terminate. The result is trivial: in first case finalResult = rem + (daysLeft / cur) * diff + (daysLeft%cur) * x, in second case it's just rem + daysLeft * x. If days left  ≥  days to be taken, we will keep iterating the process.

Complexity analysis: Both cases can be done in O(1), so we just care about number of iterations. After one iteration cur increases by at least 1, thus after k iterations days passed = Ω(k²), so running time for one test case is , enough to pass all tests.

Code in C++

PS: This is the first time that I try to write a solution with

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

I missed that point min(N1,N2)+1. Then I reduced the problem to vertex cover of set of cycles. But actually it's possible only to choose one vertex(by min(N1,N2)+1), so it got WA.

Well I thought we must buy max(N1,N2)+1 or nothing, but that was wrong...

my solution can't even pass pretests

FST!

:((

a_ix + b_i -> a_ix + b_i

A more straightforward formula looks like this

Let f[i][0] = max. answer considering numbers <= i && doesn't choose i, f[i][1] = max. answer choose i

Then f[i][0] = max(f[i-1][0],f[i-1][1]), and f[i][1] = f[i-1][0] + cnt[i]*i

Actually this is doing the same thing as the formula in editorial.

Actually I like Codeforces challenge rule more, because 1. You need a good "sense of hack" — that is, to notice some problems have some tricky point, if you lock problem early and start hacking you can get a lot more opportunity; 2. If someone else hacks you then you still have a chance to correct it (Of course lost some points, but better than nothing :p)

Looks like compiler automatically returns tail recursion result?! Amazing but that strongly rely on the compiler, maybe on Codeforces it works but not always work.

Nope. When a Codeforces round ends a message box pops up and says "the coding phase of round xxx has ended"

Why are people downvoting this!

But I never use REP macros... It differs from people

Still no editorial post... bad :(

That's magic in C. You can program a one-liner gcd or disjoint set XD

There are 5 different cases(but we can reduce that to 3):

1. The first player can decide the result of the game. Then he will lose n-1 games and win the last one.

2. The result is deterministic (first player always win or lose), in such case, if first player always wins, result depends on parity of k; otherwise first player loses.

3. The first player can ensure a lose but cannot win, then opponent force him always lose.

4. The first player can ensure a win but not a lose(this is more complicated and I took some time to evaluate that): assume k=1, then first player choose to win; then assume k=2, we will see that the second player can let him win, and get a first play in next game and wins; evaluating similar cases as k grows we will see that first move will always win if optimally play. So the result depends on parity of k again.

5. The opponent can decide the result. Obviously the first player loses.

And finally the conclusion is: If first to play can decide the result then first play wins; Then if first to play can only ensure a win, result depends on k; Otherwise first player loses.

But GCC gives compilation error if you write void main(), and that's not supported in standard.

For the ones who have studied problem 1A — Dreaming in IOI 2013 the solution will be quite clear. Fortunately I have read that problem and solved it before :D

Look carefully! Bottom right one says Registration is running

1H after coding phase and system test still not complete :(

What are hackings on problem A div1? At first I think some people doesn't use long long but it seems that pretests include that case.

hope all accepted solutions!

slowest ever system test :(((

1 and l almost look the same in hacking box, I agree. I've got same problem before.

Seems that the post you talked about is the only contest forecast post that doesn't mention MikeMirzayanov :p

Codeforces Round 232 (Div. 1) was a terrible memory... All extreme math problem P This is not Mathforces :(

Well I don't hope I can get back to yellow only by one contest, I mean, there are more chance of positive rating change in non-chinese rounds

UPD Wow. I become master again. And you too XD

The first ever non-Chinese Div.1 round in 40+ days(excluding tournaments)!!!

Hoping to get back to yellow :D

STL is evil in some way... Believe me, after IPSC 2014 there will be "HashSetKiller" programs, like already exist JavaQuickSortKiller!

p.s. one problem in this year's IPSC is to hack C++ and Java hashset program to let them get TLE in not very large test case, and there even exists a input that could hack both programs! (See HARD version of that problem)

because we can use infinitely times of 1. So why use numbers greater than 58? (all input number smaller than 30)

Compress some 0/1 data into a single integer and that's called bitmask. In this problem, we should record "if prime factor x appears". And that's a typical problem which bitmask DP can be used to solve.

n**k could be VERY VERY VERY large (100000¹⁰⁰⁰⁰⁰) , which surely overflows any type of floating point number; or cause your python solution which automatically turns into BigInteger operations and get TLE

Codeforces latex doesn't work properly as handling exponents : log^2n cannot show log²n

But I think the latter is more of natural. Actually this issue has been discussed in some other posts.

That's because we can finally have a long long holiday AND MORE IMPORTANT some people think setting a CF round is a lot of fun XD

O(logn²)? That should be O(log²n)

P.S. all links to the problem goes to problem 346A. Maybe there are some bugs

haha but , I DON'T WANT TO LOSE RATING :((((

Your argument is true but almost all softwares&&hardwares use the same way to represent negative. So using n&-n is OK i think. And more important n&-n works faster and because it's a very basic operation, say in Fenwick trees this trick proved to be helpful.

I just wonder why he doesn't use a swap() function... Even <algorithm> gives one easy-to-use template

Codeforces Round 254 (Div. 1)

Codeforces Round #FF (Div. 1)

Codeforces Round 257 (Div. 1)

Codeforces Round 259 (Div. 1)

Chinese Div1 got a Ultra kill!! Someone stop it :D

O(nm) = O(n³), because m = O(n²) it depends on how many edges in the graph.