NALP's blog

Codeforces Beta Round #19
By NALP, 14 years ago, translation, In English
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

Russian

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
  • Vote: I like it
  • +46
  • Vote: I do not like it

Comments Comments (53)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I just missed registration, could you allow us to register just for a couple more minutes, please?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
To late... The contest started.. Ohhh...
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I can't log in. They are saying about a broken link just as I try to enter the contest :(

Can anybody help, please!
→ Reply
14 years ago, # |
  Vote: I like it -12 Vote: I do not like it
I don't like this contest at all. Second task shouldn't be dynamic programming.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Good problems. I'm using hashing on C, but still get TLE on test 21.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
with KMP i guess ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    No :)
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Well, main trick - it is not string problem :)
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I used Suffix Arrays, Longest Common Prefix and Range Minimum Query to solve this problem.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      i've find all intervals between all same digits, then sort it, and just moved the left border of string
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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.
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      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?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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).
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Yep,if each number occurs arbitrary times,my solution will absolutely TLE.And your solution can be implement in O(n).
          → Reply
14 years ago, # |
  Vote: I like it -11 Vote: I do not like it
@admin , can u provide me the testcase file for problemA?
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

but there should be delete option..   :?

→ Reply
14 years ago, # |
  Vote: I like it +20 Vote: I do not like it
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.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can anyone show me a good method to solve Problem E ? my alg is O(m*m), but sill TLE.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    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.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    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!
    → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
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.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
sorry  the link i provided for my code is
http://ideone.com/djbUe
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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).
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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. .
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    "Let through" goals, i.e. the goals that your opponents scored in matches against you.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like 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?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    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]
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      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) :)
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Yeah, me too, I often fail on this kind of DP. can someone change our thought process. Thx
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        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.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like 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:)
          → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          Can you explain your solution for problem D too?
          Thanks in advance.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
            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.
            → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
       why t_i + 1, why not ti?
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        because we also get item we bought
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          so what is the s mean?
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Number of items we stealed or bought
            → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              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.
              → Reply
            • 14 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it
              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.
              → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        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.
        → Reply
        • 14 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          get it, thanks!
          → Reply
        • 4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks, when there is so simple explanation written by slycelote then why people are not writing just this. in two lines i got the whole logic behind this. Thanks again

          → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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?
→ Reply