Блог пользователя chrome

Автор chrome, история, 9 лет назад, По-русски

Всем привет!

Завтра в 20:00 MSK состоится Topcoder SRM 681.

Давайте обсуждать задачи после контеста!

  • Проголосовать: нравится
  • +89
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve 500 in div2?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

can't login

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Unable to launch arena

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Are there any official announcments? Is challange phase canceled?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    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."

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Round unrated, challenge starts in 2 min.

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Match today is unrated, as per announcement.

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится +66 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Try grouping parts covered by same subset of shops.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +34 Проголосовать: не нравится

    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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        ^ 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?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 :(.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

          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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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).

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          The equivalence is true modulo any integer.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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;
      }
      
  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    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?

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    http://pastebin.com/x3yJgTcc

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я новичок в ТопКодере. Я решил задачу, но рейтинг не поменялся. В чём может быть проблема?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Контест нерейтинговй изза проблем с сайтом.