Codeforces Beta Round #19

14 лет назад, # |

+12

Новый рекорд по количеству участников

→ Ответить

ddrone

14 лет назад, # ^ |

Это же только зарегистрированных, а в результатах -- количество принявших участие. Разве не так?

→ Ответить

AVoz	14 лет назад, # ^ \| 0 да так, и все таки это рекорд по кол-ву зарегавшихся, даль что ниже психологической границы - 1000. → Ответить

14 лет назад, # ^ |

Ниче, прорвем штуку когда-нибудь)))

→ Ответить

MciprianM

14 лет назад, # |

I just missed registration, could you allow us to register just for a couple more minutes, please?

→ Ответить

MciprianM

14 лет назад, # |

To late... The contest started.. Ohhh...

→ Ответить

TarifEzaz

14 лет назад, # |

I can't log in. They are saying about a broken link just as I try to enter the contest :(

Can anybody help, please!

→ Ответить

Egor	14 лет назад, # \| 0 А что из себя тест 46 по задаче E представляет? → Ответить

RAD	14 лет назад, # ^ \| 0 Цикл из 9999 ребер + одно рандомное ребро → Ответить

Egor	14 лет назад, # ^ \| 0 рандомное ребро внутрь или наружу? В любом случае я не понимаю, почему у меня там WA... → Ответить

RAD	14 лет назад, # ^ \| 0 Ребро внутри этого цикла → Ответить

ivan.popelyshev

14 лет назад, # ^ |

Ты про стек не забыл? у меня из-за этого WA было

→ Ответить

P___	14 лет назад, # \| -12 I don't like this contest at all. Second task shouldn't be dynamic programming. → Ответить

Nedy88

14 лет назад, # |

Good problems. I'm using hashing on C, but still get TLE on test 21.

→ Ответить

MikeMirzayanov

14 лет назад, # ^ |

It can be solved without hashing

→ Ответить

Ripatti

14 лет назад, # ^ |

I used hashing and got AC.

→ Ответить

Qubit01

14 лет назад, # |

with KMP i guess ?

→ Ответить

MikeMirzayanov

14 лет назад, # ^ |

No :)

→ Ответить

Egor	14 лет назад, # ^ \| 0 Well, main trick - it is not string problem :) → Ответить

jbernadas

14 лет назад, # ^ |

I used Suffix Arrays, Longest Common Prefix and Range Minimum Query to solve this problem.

→ Ответить

L.I.S.

14 лет назад, # ^ |

i've find all intervals between all same digits, then sort it, and just moved the left border of string

→ Ответить

jbernadas

14 лет назад, # ^ |

Yes, that part is the same in my solution, but I used all that stuff to get the intervals. I suppose there is an easier way.

→ Ответить

bolin.huang

14 лет назад, # ^ |

It is ok to use map as hashing,since n is no so large(<10^5).

And because each number occurs at most 10 times,record the nearest position of number a[i] after position i,then you can use an optimal brute force to find the shortest repeat length s_rep[i] that begins at i.

So the rest is just a loop.

But this seems not a good solution.Are there any better solution?

→ Ответить

jbernadas

14 лет назад, # ^ |

I did something similiar, for each pair of equal numbers, see if there is a repetition beginning at the first with the second at the middle. To check that all the interval numbers are equal, I used suffix array and RMQ to do that in O(1).

→ Ответить

bolin.huang

14 лет назад, # ^ |

Yep,if each number occurs arbitrary times,my solution will absolutely TLE.And your solution can be implement in O(n).

→ Ответить

14 лет назад, # |

Блин... Обидно, поздновато допер до 2 задачи... Минут бы на 10 пораньше...

Ну ладно, зато из 2 дивизиона легче выбираться)))

→ Ответить

sankear

14 лет назад, # |

А когда будет разбор задач?

→ Ответить

pkhaustov

14 лет назад, # |

+12

Thanks for the great contest! Problem A is a typical implementation problem. Problem B is simple but not really obvious DP. Problem C is a very interesting problem with a lot of ways to solve it.

Well, I've solved problem C without hashing. Also, I didn't use KMP or Z-function. DP is the answer :) Lots of memory to store everything I need, lots of precalc operations and AC as a result. Was really pleasured to solve this problem.

→ Ответить

pkhaustov

14 лет назад, # ^ |

Well, maybe my solution is not the most popular one. So I should better describe it.

Possibly I wasn't correct when I said that I didn't use Z-function. I didn't use the typical linear algorithm to find classic Z-function. The idea was to find for two given positions X and Y the length of the longest string starting from this positions.

I've used classic DP(X, Y) to find a value of DP-function. But it is no use to store the value of DP-function for any values of X and Y. We should store it only for positions with the same letter. It's mentioned in the statement that the number of such positions is strongly limited.

Then it's quite obvious how to use the value of DP-function to solve this problem in O(N) time.

→ Ответить

mkagenius

14 лет назад, # |

-11

@admin , can u provide me the testcase file for problemA?

→ Ответить

mkagenius

14 лет назад, # |

no delete option....i clicked so many times..as my internet is slow...

but there should be delete option.. :?

→ Ответить

Fcdkbear

14 лет назад, # |

Good contest! I had a lot of fun solving problem B :-)

→ Ответить

mastersobg

14 лет назад, # |

Может кто-нибудь рассказать, как решать задачу D?

→ Ответить

KADR

14 лет назад, # |

+20

I didn't use neither Suffix Arrays nor hashing, nor DP. I've just stored all distances between equal numbers and then performed exactly the same thing that is written in the statement, i.e. tried to remove repeats in the increasing order of their lengths. The main observation is that the distance between the numbers from the first half of the repeat and the respective numbers from the second half remains unchanged.

→ Ответить

MikeMirzayanov

14 лет назад, # ^ |

cool

→ Ответить

wbdyni344

14 лет назад, # |

can anyone show me a good method to solve Problem E ? my alg is O(m*m), but sill TLE.

→ Ответить

ilyakor

14 лет назад, # ^ |

Well, if you look at standings you can easily understand that O(m*m) will definitely fail, since a lot of people have TLE. It can be solved faster. The main observation is that if the required edges exist then there is an odd cycle and all edges in answer belong to this cycle. So the first thing to do is to find some odd cycle with DFS. Then you can delete this cycle from graph. If the resulting graph is not biparate, then answer is zero. Otherwise you can run dfs from each of the nodes on cycle marking the colors of nodes. The goal is to understand which cycle nodes have the same color and which opposite. So, you will get some statements like "Nodes x and y of cycle have the same color" or "Nodes x and y of cycle have the opposite color". Obviously each statement is equivalent to statement "Edge to be removed is on segment [x,y] of cycle" or "Edge to be removed is on segment [y,x] of cycle" (depending on (y - x) % 2). Number of statements is linear because they are generated by DFS, so we have problem to find which cycle edges are on all generated segments of cycle, this problem can be solved by usual methods (sorting etc.). I don't know if this problem can be solved in a less complicated way, but even this solution can be coded on contest.
PS: sorry for my terrible english.

→ Ответить

wbdyni344

14 лет назад, # ^ |

Yeah,thanks you very much.

→ Ответить

kalinov

14 лет назад, # ^ |

There is an O(n+m) solution based on DFS graph analysis.

Run a DFS to create a DFS forest. For each node x let color(x) be depth(x) mod 2.

Now, the only edges that could violate this coloring are back-edges in this DFS forest.

If colors on two endpoints of a back-edge are the same, we call this back-edge BAD. Otherwise we call it GOOD.

If there are no BAD back-edges at all then the graph is bipartite and you have to output each edge and we're done.

If there is exactly 1 BAD back-edge then that back-edge is a part of solution because removing it causes the resulting graph to be bipartite. However, if there are more than 1 BAD back-edge then none of them is in the solution.

Now we covered back-edges, but what about tree-edges.

Observe a tree-edge u--v such that u is a parent of v in a DFS tree, and imagine that we swap colors for each node in a subtree rooted in v.

Obviously a tree-edge u--v is now invalid and has to be removed, but some of the back-edges have also changed states. If a BAD back-edge led from a node in a subtree rooted in v to a node higher than v, then that edge became GOOD back-edge and vice versa.

So a tree-edge is a part of solution if all BAD back-edges in the graph and none OK back-edges connect a node from a subtree rooted in v with a node in the rest of the graph.

It's possible to keep track the number of such BAD and GOOD back-edges as you do the DFS. For each node add-up back-edges from it's children, add back-edges that go from the node up the tree and subtract back-edges that go down the tree.

That's it. I hope it helps.

I liked the problemset too, especially this problem. Thanks to problemsetters!

→ Ответить

AVoz	14 лет назад, # \| +12 Люди добрые напишите разбор пожалуйста → Ответить

Salat

14 лет назад, # ^ |

написать разбор может только один человек, который все решил.

тогда "добрый человек напиши разбор пожалуйста".

→ Ответить

14 лет назад, # ^ |

Или тот, кто придумал задачи ;)

→ Ответить

14 лет назад, # ^ |

И он не русскоговорящий, так что этот вопрос надо задавать на другом языке.

Или реально напиши в личку Артему Рахову или Коле Кузнецову

→ Ответить

Anurag

14 лет назад, # |

Problem -A
I am getting WA. I am not able to sort the "teams" properly . Though in the below code i have used sorting using #3 defined basis.

My

<A HREF="http://ideone.com/djbUe">Code</A> 
is here. Can anyone tell where i am wrong.

Thanks for ur response.

→ Ответить

Anurag

14 лет назад, # |

sorry the link i provided for my code is
http://ideone.com/djbUe

→ Ответить

wjomlex

14 лет назад, # ^ |

Around lines 126-127... Shouldn't you be swapping v2 and v3 as well? You want to make sure all the data stays together. Every time you swap two teams, you'll want to swap team, v, v2, and v3.

A few notes... if you use a structure that has all of this data, you won't have to worry about only swapping parts of the data. Also, if you use a built-in sorting method, it'll run in O(n log n) rather than the O(n^2) sort you have here, and it'll take you less time to code.

→ Ответить

Anurag

14 лет назад, # ^ |

wjomlex Thanks

I got AC , i appreciate ur effort in detecting my mistake.

Thanks

→ Ответить

wjomlex

14 лет назад, # ^ |

No problem :)

→ Ответить

cgy4ever

14 лет назад, # |

Problem C is wonderful!

For 2 same letter Ai and Aj(i < j) , we call it a "match":

M[i].x = j - i , M[i].start = i.

It can be found that there are no more than 10N "match"s.

We sort them by x first , if equal , by start.

And just to consider each match and keep the left-bound.

If there are some i that:

for all i <= j <= i + u - 1 , M[j].x = u , M[j].start = M[j-1].start + 1

and M[j] >= left-bound

We make the left-bound to i + u - 1 + u.

The algorithm is O(10NlogN).

→ Ответить

jaey	14 лет назад, # \| 0 somebody can explain me what exactly does " in decreasing order of the diference between scored and missed goals " means? I don't understand what missed goals are you refering to. . → Ответить

14 лет назад, # ^ |

"Let through" goals, i.e. the goals that your opponents scored in matches against you.

→ Ответить

VladBelous

14 лет назад, # |

Can anyone explain how to solve B?
I´ve seen, that it is a DP problem with N*N state space, but what exactly is the state and what is the dynamic optimality of the problem?

→ Ответить

14 лет назад, # ^ |

dp[m][s] = the minimal cost of a subset of items that you choose among the first m items so that the sum of (t_i+1) >= s (here i runs over the indices of the chosen items).
The answer is dp[n][n]

→ Ответить

VladBelous

14 лет назад, # ^ |

Thanks, this looks logical once you´ve stated it.
It still seems, however, somewhat unobvious (or rather indirect). Quite a lot of people solved it during the contest, I´ve spent about 1.5 hours without success.
How did you come up with it during the contest? Could you, please, describe your thought process? (I´m trying to fix mine) :)

→ Ответить

Harta

14 лет назад, # ^ |

Yeah, me too, I often fail on this kind of DP. can someone change our thought process. Thx

→ Ответить

kalinov

14 лет назад, # ^ |

My thought process was something like this:

OK, this looks like DP or greedy. It's problem B so it might be greedy.

How should I sort items? Should I always pay for the cheapest item? No, doesn't work. Should I pay for the item with largest time? No. What about items with t=0.

Well, I guess it isn't greedy.

How would I write a recursive solution?

For each item I should either pay for it or steal it. If I pay for it then I can steal some other items. Yeah, state should definitely contain the position in sequence and the sum of ti.

Well I guess that's it, I just keep track of amount of items I have bought and the amount of items I can steal. In fact if I add 1 to each ti then it's even simpler.

That's it, more or less. It's hard to recall and describe exactly.

A lot of experience with DP and memoization helps ofcourse, but I think the best advice is to write or think about writing a simple recursive brute force solution and then figure what the state is.

When thinking about recursive solution you should try to make it as iterative as possible, that is scan elements in order and decide what to do with it.

→ Ответить

VladBelous

14 лет назад, # ^ |

Very nice, thanks.
Knowing how successful contestants approach the problems is both interesting in itself and educating as well. I thinks it´s underrated as a means of teaching:)

→ Ответить

a70babat

14 лет назад, # ^ |

Can you explain your solution for problem D too?
Thanks in advance.

→ Ответить

kalinov

14 лет назад, # ^ |

Collect points from add and remove commands and sort them first by x and break ties by y.

Each point in a sequence can be active or inactive, and initially every point is inactive.

For each query "find x y" we have to find the first (because of the way we sorted the sequence) active point P in this sequence such that P.x > x and P.y > y

To maintain this sequence we have to build interval tree on it. For each interval we keep track of the largest y of all active points in the interval. If there is no active point in the interval than this value is -inf.

Updates (add and remove) are quite simple, just find the point in the sequence and update the value of the leaf (value becomes P.y on add commands or -inf on remove commands) and then go up the tree and update the value as a maximum of two children nodes.

Find x0, y0 command is also quite simple, but it might not be so easy to understand why is it O(log n).

Start from the root and do the following recursively:

If the x coordinate of the rightmost point in the interval represented by this node is not greater than x0 then none of the points in the interval are good and so we cut this branch.

If the topmost point in the interval represented by this node is not greater than y0 then none of the points in the interval are good and so we cut this branch.

Search for a solution in the left branch.

If no solution is found then search for a solution in the right branch.

My source code for further details.

→ Ответить

14 лет назад, # ^ |

why t_i + 1, why not ti?

→ Ответить

Egor	14 лет назад, # ^ \| 0 because we also get item we bought → Ответить

14 лет назад, # ^ |

so what is the s mean?

→ Ответить

Egor	14 лет назад, # ^ \| 0 Number of items we stealed or bought → Ответить

14 лет назад, # ^ |

so dp[m][s] means in the first m items, (m - s) iteams can't be decide to be bought or stealed.
and but what is the transfer equation is? i can't write it.

→ Ответить

14 лет назад, # ^ |

dp[m][s] = min(dp[m-1][s], c[m] + dp[m-1][s-t[m]-1])

→ Ответить

14 лет назад, # ^ |

yes, i know, every bought item can count (t_i + 1) item, so the dp[m][s] means buy some items in first m items, the transfer equation is: dp[m][s] generate dp[m + 1][s] and dp[m + 1][s + t_i+1] + c_i.

→ Ответить

14 лет назад, # ^ |

Let M be the set of items we choose to pay for; then we need n-|M| seconds to steal other items; it means that sum of t_i >= n-|M|, that is, sum of (t_i+1) >= n.

→ Ответить