chrome's blog

Topcoder Single Round Match 681
By chrome, history, 9 years ago, translation, In English

Hi there!

Tomorrow at 20:00 MSK will be held Topcoder SRM 681.

Let's discuss problems after contest!

  • Vote: I like it
  • +89
  • Vote: I do not like it

Comments Comments (65)
| Write comment?
»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I like second problem in div2, who is author of round?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    I try solve this problem this way,but didn't work some test case. How I do this correct?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Do not discuss problems during coding phase!!!

      → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 500 in div2?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Points where robot can reach will from a rectangle because robot can move between x-l and x+r along x axis and y-d and y+u along y axis(here (x,y) are coordinates of robot and l,r,d and u are count of left, right, down and up in string).

    So if robot 2 can enter the rectangle of robot 1 then they will collide else it is not possible.

    Code

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    my idea was to set a meeting point of two robots by brute force. Then check whether they both can reach that point by counting up, down, left and right characters.

    → Reply
»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

can't login

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Before start of challenge phase plugin froze for me. Now I can't log back in :/

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I could not compile during the last 2 minutes, I got something like server busy, is this common in topcoder??

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too. I was trying to upload a fix to my solution, but couldn't before time ran out. The worst part was there was more than 4 minutes left when I was trying to upload. haha, oh well. I've been competing on TC for a while and this hasn't happened to me before.

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Unable to launch arena

→ Reply
»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

java applet doesnt work, use www.arena.topcoder.com

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are there any official announcments? Is challange phase canceled?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    They sent the following: "Challenge phase will be starting as currently scheduled. Given the frequency of issues (and the fact that access to topcoder.com was actually down for several mintues), the match will have to remain unrated today."

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Round unrated, challenge starts in 2 min.

    → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Match today is unrated, as per announcement.

→ Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Well...how to solve Div 1. 250? I thought of Binary Search, but I couldn't find good way to check if something could be attained.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Yes, binary search is good.
    Now swipe left to right, when at position p, add segments which begin here in a set.
    Now to get mid at current position you should always take from segment with minimum r (I don't know any formal proof, but it's right intuitively)
    Whenever you can't take, stop and say that mid is bad.
    Also, after processing position p, remove the segments which over here from your set.
    By the way, it reminds me of this problem

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Proof for that is easy. Suppose there are 2 segments A and B. Both have the same left end-point 'p1' but end-point for B 'p3' is > end-point for A 'p2'.

      Let's say you can allocate k points from each. And m = p2. Also, let's assume: distance(1 -> p2) = k distance(p3 -> m) = k Now, if you allot points from B first, you will exhaust all k points that you could allocate before p3 is reached. And you have no way to choose parts till m.

      Optimal solution: 1 -> p2 points allotted from A, the rest from B.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did maxflow and apparently the range of the data is not feasible. I think it sounds like some interval related problem. I am not sure how to use those continuous intervals.

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +66 Vote: I do not like it

I am the writer of this round. I'm very sorry for technical issues that caused the round to be unrated. I'm not sure what went wrong during the match. It seems that topcoder.com went down during the round.

Here are solutions.

div2 code: http://pastebin.com/tiX7gjQw

div1 code: http://pastebin.com/GqPkiviy

  • div2 easy: do what's stated in the statement

  • div2 med: Let's look at the absolute value of the difference between x and y coordinates. We need at least as many L/R characters to make the x coordinates coincide (similarly for U/D characters for y coordinates). This is also a sufficient condition.

  • div2 hard: This is a bitmask dp. Below just a summarized version of the code, so read that first. We go bit by bit from high to low. The bitmask represents which numbers are strictly less than max, and other numbers are currently equal to max. Also, once we fix the bit of the 0-th number in the list, all other numbers are determined. Take a look at the code for more details.

  • div1 easy: Binary search for the answer. After you can do greedy or max flow on compressed graph (greedy is much easier to code though). The greedy takes parts from an available shop with the smallest b[i].

  • div1 med: I thought this was a div1 easy when I first came up with it, but it is a bit tricky. You can do brute force. Here's a brief proof on why this works. Let's look at the max number in the range. Then, we have a recurrence T(n) = min(a,b) + T(a) + T(b), where a+b+1=n. By the "small-to-large" principle, T(n) is O(n log n), so the answer is always small. I'm also sorry that it's impossible solve this problem in some languages like C#.

  • div1 hard: Compute probability that a pair of coins contributes to the final answer using an O(N^3) dp. Then, add up vals[i]*vals[j]*pr[i][j] to get the final answer. When I came up with this problem, I was trying to think of a dp based on a range But, I discovered that approach didn't quite work, since after splitting, the two parts are not independent.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Can you explain the maxflow method for div1 easy? How do you build the compressed graph? I represented each shop and each item part as a node and it is too large to fit in.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try grouping parts covered by same subset of shops.

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      You can see rng_58's code for a nice implementation. The basic idea is that you can compress coordinates first. There are only at most 100 numbers in the input, which splits up the parts into 100 different intervals. So you only need to have a node for each interval rather than for each item part.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    d1-500 was so cute :) (And definitely not an easy!)

    900 was a bit easier than usual, maybe it could have been a 600 in a more difficult round, but I'm fine with it as a 900 too. The admins tend to know their stuff when it comes to difficulty :P

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hi can you explain about the div2 hard problem im kinda new i didnt understand the question can u please elaborate please? thank you :)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Random opinion: I've never seen an n = 10.000.000 work with an O(n log n) solution, I scratched every idea that could go above linear while thinking about the Div1-Medium. I think in the end I came up with something that is O(n) time and O(sqrt(n)) memory, but I didn't have time to code it. If it's correct or there are other O(n) solutions, I think this problem should either have a smaller N or a bigger N and more points awarded.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      Random opinion 2: Given how input was generated, it was probably hard to construct evil testcases here :P.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        ^ This too. I've actually wondered about this for every problem that had generated inputs in TC. Maybe the TC staff can shed some light on how they build strong test-cases this way?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Another issue about generating inputs — it is really uncofmortable to construct countertests during hacking phase if input needs to be given as few seeds to generator :(.

          → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        actually I used stack idea which fail if input was decreasing array, I thought the input is random but then I was hacked with the following test

        n=10,000,000

        x0=(2^50-1)

        a=0

        b=(2^50-1)

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 2   Vote: I like it +13 Vote: I do not like it

          I also implemented the stack idea and noticed that test case (it is actually in the sample ones). So I did a "dirty" hack by reversing the initial array whenever the stack size exceeds 30000 (doing some manual testing on Arena yields this limit). I'm not sure if there exists a test case that causes my solution to fail but I feel that it's quite difficult to generate such one randomly. It passed in the end.

          → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For me med was by far the hardest problem in that problemset :pp. How do you implement this bruteforce?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The only thing we need to know how to do is go backwards and forward in the sequence. For each number, walk left and right until you hit the end of the array or a number >= to yourself. You can see my code for details.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        The trickiest thing in the whole solution is that we can go left. Have you ever seen input generated with some similar formulas that allowed to go left and when that was useful to solution? I have seen such thing for the first time, usually we are not supposed to delve into those formulas. And you didn't even mention it in your solution, so I thought that maybe you have some other approach on your mind :P. What is funny is that it came through my mind that maybe we are able to construct an inverse, but I discarded that idea, because I thought it is not working because of that modulo (1 << 50) — 1 xD.

        Btw nice problem and if I'm not mistaken it is possible to construct solution without possibility of going left that works in O(n) time and O(sqrt(n)) memory, but it was too complicated for me to complete coding it in time. We divide sequence to parts og length , keep maximums within them, use typical algo for intervals between them and then determine radiis of those maximums (for every maximum we need time, but it is not easy to code it given time I was given).

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        can you add some explanation/references on how to compute the inverse in order to go left ?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Here, x is the previous value and y is the next one.

          The equivalence is true modulo any integer.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      For each number, move left until you find a bigger number, move right until you find a bigger number, add radius to answer.

      Edit: and I agree that med was the hardest in the problemset :p

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Keep leftmost and rightmost value of your current range; finding next element to the right is trivial (simply use formula from problem statement), and deriving previous element is also not hard:

      long long get_prev(long long x)
{
	x-=B;
	if (x<0)
	x+=(one<<50);
	x^=A;
	return x;
}
      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    For div1 med I tried to implement it the somewhat classic way to solve it using a single stack which stores a decreasing sequence, this is linear in time and I expect it to run in O(sqrt(n)) memory as this is the expected length of the longest increasing/decreasing subsequence in a sequence of N random numbers, could you confirm if this kind of solution may get accepted?

    Also, does the generated sequence behaves like a 'random' sequence?

    EDIT: I see now you could create a fully increasing sequence with this generator (which is irrelevant to my solution, can you also create a fully decreasing one?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      It's not too hard to generate cases where the numbers are all increasing or decreasing, which would break naive stack-based solutions. For example, a=0, b=1, x0=0.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok, thanks a lot for your reply, and for yet another great problemset.

        → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you provide more details on part about "small-to-large" principle ? Thanks.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    So comment with 2nd sample test 'Don't forget, the answer is modulo 1,000,000,007.' was a trap :).

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    For the 500-point problem, given the input generators, is it possible to construct the hardest test case for the correct answer? If I'm not mistaken, the worst case for this complexity is when the maximum entry is close to the middle (but not quite at the middle). However, let's just say that we want it exactly in the middle every time. Are there seeds that could generate something like the following for n ~ 10,000,000?

    1 2 1
1 2 1 3 1 2 1
1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

    Obviously, you cannot get this exact sequence (since, for example, in the third sequence 1->2 and 1->3 and 1->4, which is impossible), but can you get a sequence where the max is in the middle every time?

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Another way to prove it's NlogN for D1 Med:

    Let's say that element i is covered by element j if the radius for element j extends over element i. If we take the sum over all elements i of the number of elements j covering i, that's on the same order as the sum of all the radii, which in turn determines how much work is done by the brute force algorithm.

    Suppose a particular element i is covered from its right by elements j_1, j_2, ..., with i < j_1 < j_2 < ...

    Each j_i needs to be at least twice as far away from i as the j_(i-1) before it; otherwise, j_(i-1)'s radius wouldn't extend far enough to cover i. So, each i can only have log(N) elements j covering it from the right. The same logic applies for the left.

    → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    May you please a little bit more on how you get this equation:

    T(n) = min(a,b) + T(a) + T(b)

    I can't see why this is correct

    UPD Sorry, I get that, it's so easy. I am probably too tired after implementing O(n) solution :)

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution for div2 hard passed all of the system tests, but I think it isn't correct.

    http://pastebin.com/x3yJgTcc

    → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

After centuries my wrong approach (at least what I thought of my solution for div.1 medium) passes the system test and contest becomes unrated.

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone please explain me DIV 2 hard, I still didn't get it.

→ Reply