### NALP's blog

By NALP, 10 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!

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

• +46

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

### wjomlex  Thanks

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

Thanks
•  10 years ago, # ^ |   0 No problem :)
 10 years ago, # |   0 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).
 10 years ago, # |   0 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.
 10 years ago, # |   0 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. .
 10 years ago, # |   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. .
•  10 years ago, # ^ |   0 "Let through" goals, i.e. the goals that your opponents scored in matches against you.
•  10 years ago, # ^ |   0 thanks adamax .
•  10 years ago, # ^ |   0 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
•  10 years ago, # ^ |   0 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
 10 years ago, # |   0 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?
•  10 years ago, # ^ |   +1 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]
•  10 years ago, # ^ |   +1 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) :)
•  10 years ago, # ^ |   0 Yeah, me too, I often fail on this kind of DP. can someone change our thought process. Thx
•  10 years ago, # ^ |   +3 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.
•  10 years ago, # ^ |   0 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:)
•  10 years ago, # ^ |   0 Can you explain your solution for problem D too?Thanks in advance.
•  10 years ago, # ^ |   +1 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.
•  10 years ago, # ^ |   0 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 <"
•  10 years ago, # ^ |   0  why t_i + 1, why not ti?
•  10 years ago, # ^ |   0 because we also get item we bought
•  10 years ago, # ^ |   0 so what is the s mean?
•  10 years ago, # ^ |   0 Number of items we stealed or bought
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   0 dp[m][s] = min(dp[m-1][s], c[m] + dp[m-1][s-t[m]-1])
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   0 get it, thanks!
 10 years ago, # |   0 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?
•  10 years ago, # ^ |   0 use printf("%I64d\n", ans);
•  10 years ago, # ^ |   0 It worked! thanks.