Medo.'s blog

Topcoder SRM 723
By Medo., history, 6 years ago, In English

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

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

Comments Comments (31)
| Write comment?
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

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

    First option: Use web arena https://arena.topcoder.com .
    Second option: Download applet from https://www.topcoder.com/community/competitive-programming/ . After that, watch some first part (~10:00 or ~15:00?) of this youtube video https://www.youtube.com/watch?v=A5vnkkFGOo0 .

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

      Does applet work better. I find web arena quite slow.

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

        Yes the applet works much better for me. The Practice section on Arena keeps on Logging Off and telling me to Log In again even on a very good connection. I faced no problems of the kind on the Applet.

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

      I am using Kawigi Edit.I faced a problem if I have global array. Expected is that it should reinitialise to zero for every testcase automatically but it uses the array which was left over by previous testcase. How to get the expected work done ??

      Apart for getting class and stuff written ,does kawigi do anything better

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

    This link was shared by one of our seniors to begin with topcoder, I think it may help you.

    And I personally use KawigiEdit as plugin for c++. Download it from here

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

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

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

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?

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

Medium: Write bruteforce

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

This was not the most glorious SRM problemset.

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

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

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

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

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

    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.

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

    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

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

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.

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

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

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

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

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

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

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

    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.

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

      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.

      → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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?

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

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

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

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

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

    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.

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

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

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

    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
    → Reply