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

Автор Medo., история, 7 лет назад, По-английски

Topcoder SRM 723 starts tomorrow.

https://www.timeanddate.com/worldclock/fixedtime.html?msg=Topcoder%20SRM%20723&iso=20171118T1700&ah=2&am=0

I only created this blog because cgy4ever stopped doing them. I always disliked knowing about SRMs before they start by like 1-2 hours so thought I'd post about it a day in advance. ( If there is someone from TC that prefers to post these kind of blogs, I will happily delete this).

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

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

Can you please tell how you use Topcoder arena. Do you use any plugins for C++(and other system settins). I find it really weird to use Topcoder. Thanks in advance.

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

REMINDER: The contest starts in 30 mins. Let's participate and enjoy!

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

First time when I was about to solve the Hard problem and made the code work 4 minutes after the end...Anyway, the only reason for which I was able to solve it was because it was given before in some IOI. How to solve medium?

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

Medium: Write bruteforce

Hard: Problem taken from IOI (IOI 2012 — City) with additional tediousness

This was not the most glorious SRM problemset.

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

How to solve Div2B(500 — point problem) (TopXorer Problem)?

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

    You are solving for a, b, c ,

    let it be ans(a, b, c)[assume a >  = b >  = c]. Let the highest power of 2 <  = a be 2x. We know that xth bit will be set in your answer no matter what. And number of bits in your answer will be x + 1.

    case 1: If 2x  <  = b,

    We can always make 2x + 1 - 1 , and this is your answer, a = 2x, b = 2x - 1, c = 0.

    case 2: Else

    ans(a, b, c) = 2x|ans(a - 2x, b, c).

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

    I think it was an overkill, but, I wrote a DP solution for this problem: https://pastebin.com/BYknMGXH during the contest. It should be self-explanatory.

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

    A single loop over the bit positions of the binary representations of A, B, C starting from 30 (the maximum possible in a positive integer) and down to 0. Let i be the current bit position, we want every bit position to be 1 after the XOR operation if possible to get the maximum result. We can count the number of 1s in the ith position in A, B, C. There are 3 cases

    case 1: number of 1s at position i = 0 We can't get a one in that position in the result

    case 2: number of 1s at position i = 1 We simply get a one in that position in the result

    case 3: number of 1s at position i = 2 or 3 In that case we can "sacrifice" (clear) one 1 (in the case of 2) or two 1s (in the case of 3) from any of A, B or C and still get a one in that position in the result because the number of ones will be odd for XOR, and after that position it is possible to get all 1s, so you can just end the loop here and set all the 1s after this position in the result to 1. The reason is once you clear a 1, any combination of 0s and 1s is possible to get after it because they all form a smaller number which is within the interval, so you'll form the combination that gets the maximum possible result

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

For Div1 500, I have came up with O(m6) solution if m = n / 7.
Keep track (cb, cu, cf, ca, cl, co) by DP and maintain m ≥ cb ≥ cu ≥ cf / 2 ≥ ca ≥ cl ≥ co. For max test case (n = 100 with all '?') it only took 15ms.
I think this problem was some new ideas for me (so it was good for me), but I want to ask why the writer did not set the constraints to n = 150 and make problem more better.
UPD: For Swistakk's reply, because I thought O(m7) seems kind of "obvious" (because some kind of obvious dp divided by 2something?). But for O(m6) it was focused on "how to combine one 'f' from 2 'f''s." I took over 20 minutes to find out this.
UPD 2: Now I've noticed that these are solution and solution. So both running time is almost equal.

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

    In what sense that would be a better problem? What do we want to achieve by raising constraints?

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

      I think the 500 is a reasonable problem as is...

      To me, the observation that a brute force DP is not 100^6 but much smaller is pretty reasonable (even if it's simple).

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

why brute force in div2 medium doesn't time out? for example solution by m.subkhankulov

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

    Most of the solutions (including mine) append a character to the longest "buffalo". This means the array of "completed prefixes" is non-decreasing. The number of states is a lot less than 8^14 (it can be proven as being the number of increasing arrays of size 14 and sum <= 100). On input equal to all '?'s (7 * 14 of them, to be exact), the number of states checked is ~65k.

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

      I was talking about div2 :) ... so the loop with 10^9 iterations can be used... ok... why not use higher constaints so that it would time out.

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

Maybe it is silly, but problems with defining 6-dimensional array costed me medium. I have the following code:

int used[15][15][29][15][15][15];
int dp[15][15][29][15][15][15];
int f(int b, int u, int f, int a, int l, int o, int ind, int cnt, string &s) {
	if (used[b][u][f][a][l][o])
		return dp[b][u][f][a][l][o];
	used[b][u][f][a][l][o] = 1;
}

I get the following error:

BuffaloBuffaloBuffalo.cpp:21:2: error: 'used' does not name a type used[b][u][f][a][l][o] = 1;

Does someone have an idea why it does not compile?

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

Can anyone explain the solution idea of Div 2 1000(C) of this contest?

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

My solution to the hard problem:

Consider cutting the polygon into halves with a vertical or horizontal segment. If one part is of size a, and the other one is or size b, then a × b pairs will have to pass this segment. Therefore, we just need to find all possible cuts and sum their contributions up.

Let's do vertical and horizontal segments separately. Suppose we want to do vertical ones. A given vertical line(not segment) can intersect the polygon multiple times, and each of them corresponds to a cut. Since many "adjacent" vertical lines intersect the polygon in similar positions, we can partition the x-axis into at most O(n) parts so that contributions in each part are a quadratic function of the x-coordinate. Thus we can calculate the total contributions easily.

Too bad I had some bugs during the contest...... :(

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

    After contest I found some funny idea how to omit possibility of making a lot of bugs here. Probably for every x1 so that there is a vertical line (x1,y1)-(x1,y2) you cut this polygon using this line and calculated what part is on left and what is on right etc. But since this infinite line coincides with side it makes it somehow troublesome. But if we stretch polygon 3 times and ask about cutting it with lines x=3*x1+1 and x=3*x1+2 we never coincide with any vertical line and get all needed information :). I hope overflows are not becoming a problem after this xD.

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

Someone please explain how to solve Div 2 1000. This was the only solution accepted in the contest.

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

    The solution is simple that can write in one line.
    The answer mod 1000000007 equals to 666666691x5 - 333333332x3 mod 1000000007.
    How can we get the answer polynomial? I'll explain the way of solving.
    1. There are O(n2) number of vertices, so there are O(n4) pair of vertices. Distance for each pair is at most O(n) so you can guess that the answer can be a polynomial with degree equals to 5.
    2. Now you have to calculate the polynomial. If you can calculate for the six different n (0 ≤ n < 1000000007), you can get the polynomial. So how to get value for six n's? Of course, "writing naive solution + getting answer for n = 0, 1, 2, 3, 4, 5" is enough.
    3. Do interpolation. Using Newton's polynomial interpolation with modulo 1000000007 is a good way to do it. Then, you get 666666691x5 - 333333332x3. This is the final answer.

    Code: How we got the answer polynomial