NALP's blog

By NALP, 9 years ago, translation, , Welcome to Codeforces Beta Round #19.

Authors of today's contest are Artem Rakhov and me. Thanks to Mike Mirzayanov, Edvard Davtyan and Julia Satushina for help in the organisation.

I hope, you will have fun.

Good luck!

P.S. After start of the contest, you can download the statements:

English

UPD. The contest has finished and you can see the standings and tasks. The winner and only participant who has solved all the problems is kalinov. Congratulations! Announcement of Codeforces Beta Round #19 Announcement of Codeforces Beta Round #19  Comments (58)
 I just missed registration, could you allow us to register just for a couple more minutes, please?
 To late... The contest started.. Ohhh...
 I can't log in. They are saying about a broken link just as I try to enter the contest :(Can anybody help, please!
 I don't like this contest at all. Second task shouldn't be dynamic programming.
 Good problems. I'm using hashing on C, but still get TLE on test 21.
•  It can be solved without hashing
•  I used hashing and got AC.
 with KMP i guess ?
•  No :)
•  Well, main trick - it is not string problem :)
•  I used Suffix Arrays, Longest Common Prefix and Range Minimum Query to solve this problem.
•  i've find all intervals between all same digits, then sort it, and just moved the left border of string
•  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.
•  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?
•  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).
•  Yep,if each number occurs arbitrary times,my solution will absolutely TLE.And your solution can be implement in O(n).
 @admin , can u provide me the testcase file for problemA?
 no delete option....i clicked so many times..as my internet is slow...but there should be delete option..   :?
 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.
•  cool
 can anyone show me a good method to solve Problem E ? my alg is O(m*m), but sill TLE.
•  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.
•  Yeah,thanks you very much.
•  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!
 Problem -AI 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   Code is here. Can anyone tell where i am wrong.Thanks for ur response.
 sorry  the link i provided for my code ishttp://ideone.com/djbUe
•  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.
• wjomlex  Thanks

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

Thanks
•  No problem :)
 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 + 1and M[j] >= left-boundWe make the left-bound to i + u - 1 + u.The algorithm is O(10NlogN).
 There is similar but a lot easier problem like PROBLEM -A http://www.spoj.pl/problems/SBETS/This Codeforces Problem A was really tougher than that.
 hey NALP, thanks a lot for the problem's statements. .  I was hoping that! many times I can't have acces to the internet, so this will be helpful at least for me. .
 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. .
•  "Let through" goals, i.e. the goals that your opponents scored in matches against you.
•  thanks adamax .
•  This is what i asked during contest(though not broadcasted)QUESTION-problem AWhat this lines means"in decreasing order of the difference between scored and missed goals"ex A-B 1:0A(scored-missd=1-0)?B(scored-missed=1-0)?ANSWER i got from admin:A: scored-missed=1-0 = +1B: scored-missed=0-1 = -1
•  yeah, I think would be better if it say " the difference between scored and received goals " or something like that. . .that's the difficult, my english is not good enough ...anyway, thanks a lot kumaranurag, I think I got it
 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?
•  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]
•  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) :)
•  Yeah, me too, I often fail on this kind of DP. can someone change our thought process. Thx
•  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.
•  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:)
•  Can you explain your solution for problem D too?Thanks in advance.
•  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 > yTo 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.
•  Kalinov, can you tell me what is this code for: "point( int x, int y ) : x(x), y(y) {}", it dosnt look like a function.And what is this for: "inline bool operator <"
•  why t_i + 1, why not ti?
•  because we also get item we bought
•  so what is the s mean?
•  Number of items we stealed or bought
•  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.
•  dp[m][s] = min(dp[m-1][s], c[m] + dp[m-1][s-t[m]-1])
•  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.
•  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.
•  get it, thanks!
 As of problem B, printf("%lld\n", ans); fails in test case 11.But cout << ans << endl; is accepted.I'm new at codeforces and don't know why printf("%lld") failed.Do you know why?
•  use printf("%I64d\n", ans);
•  It worked! thanks.