Topcoder SRM 723 starts tomorrow.

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

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.

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 .

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

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.

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

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

How do you keep track of the upcoming SRMS?

Use clist.by.

You can further signup and customize the list to see contests of particular websites only !

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

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?

Medium: Write bruteforce

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

This was not the most glorious SRM problemset.

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

You are solving for

a,b,c,let it be

ans(a,b,c)[assumea> =b> =c]. Let the highest power of 2 < =abe 2^{x}. We know thatx^{th}bit will be set in your answer no matter what. And number of bits in your answer will bex+ 1.case 1: If 2

^{x}< =b,We can always make 2

^{x + 1}- 1 , and this is your answer,a= 2^{x},b= 2^{x}- 1,c= 0.case 2: Else

ans(a,b,c) = 2^{x}|ans(a- 2^{x},b,c).Amazing Solution! Thanks for the reply.

Thanks for a clear solution.

Hints: lets s="00" is a bit sequence. since s[0] is '0' i can't take s[1] as '1'. again lets s="10". here we can take s[1] as '1' by considering s[0]='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.

A single loop over the bit positions of the binary representations of

A, B, Cstarting from 30 (the maximum possible in a positive integer) and down to 0. Letibe the current bit position, we want every bit position to be1after the XOR operation if possible to get the maximum result. We can count the number of1sin theposition ini^{th}A, B, C. There are 3 casescase 1:number of1sat positioni=0We can't get a one in that position in the resultcase 2:number of1sat positioni=1We simply get a one in that position in the resultcase 3:number of1sat positioni=2or3In that case we can "sacrifice" (clear) one1(in the case of2) or two1s (in the case of3) 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 forXOR, and after that position it is possible to getall 1s, so you can just end the loop here and set all the1safter this position in the result to1. The reason is once you clear a1, any combination of0sand1sis 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 resultFor Div1 500, I have came up with

O(m^{6}) solution ifm=n/ 7.Keep track (

c_{b},c_{u},c_{f},c_{a},c_{l},c_{o}) by DP and maintainm≥c_{b}≥c_{u}≥c_{f}/ 2 ≥c_{a}≥c_{l}≥c_{o}. 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(m^{7}) seems kind of "obvious" (because some kind of obvious dp divided by 2^{something}?). But forO(m^{6}) 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.

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

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

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

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.

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.

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

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?

function name = variable name = f?

OMG Thank you!

UPD: fixed, the problem was with parentheses.

UPD: fixed, the problem was with parentheses.

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

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 sizeb, thena×bpairs 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 thex-coordinate. Thus we can calculate the total contributions easily.Too bad I had some bugs during the contest...... :(

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.

Wow...That's ingenious

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

The solution is simple that can write in one line.

The answer mod 1000000007 equals to 666666691

x^{5}- 333333332x^{3}mod 1000000007.How can we get the answer polynomial? I'll explain the way of solving.

1. There are

O(n^{2}) number of vertices, so there areO(n^{4}) pair of vertices. Distance for each pair is at mostO(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 sixn's? Of course, "writing naive solution + getting answer forn= 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 666666691

x^{5}- 333333332x^{3}. This is the final answer.Code: How we got the answer polynomialThanks for the response :)