Medo.'s blog

Topcoder SRM 729
By Medo., history, 7 years ago, In English

Starts in less than 24 Hours.

https://www.timeanddate.com/worldclock/fixedtime.html?msg=Topcoder+SRM+729&iso=20180210T12&p1=179

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

Comments Comments (26)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder: Contest starts in 2h. Let’s enjoy!

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

Can you please announce the round a bit earlier next time?

I really like the TC problems but one literally needs to ruin his plans to be able to participate. I guess this is one of the main reasons for the low participation.

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

How to solve div2 800?

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

In div1 450, is there any simple solution or do we greedily do a bfs using only vertices on edges(is this right)??

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

    Bfs on edges definitely works (just passed in practice room). I doubt there's a simpler way to do it since this is already pretty straightforward.

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

How to solve div2 2nd and 3rd problem?

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

    For div2 medium, you can use dynamic programming (there are non DP ways to solve it as well). The state consists of the following:

    1. the index of the rectangle you are currently processing
    2. the "intersection rectangle" of all the rectangles you've included so far

    For example, if I have rectangles 0,4,6,8 (the 0 is x1, the 4 is y1, the 6 is x2, the 8 is y2) and 5,2,9,5, then the intersection rectangle would be 5,4,6,5.

    So for each state, we either try to include the current rectangle, or we skip it. We take the best of those two results. When we include the current rectangle, we have to calculate a new intersection rectangle based on the current state's intersection rectangle and the rectangle at the current index. If there's no intersection rectangle for these two, then we can't use this rectangle. Otherwise, we pass this new intersecting rectangle to the next state.

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

      Can we solve this problem using Coordinate Compression in 2D ?

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

        Yes, this is what I did.

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

        The division winner (who was also in my room) wrote the code below (retyped by me without macros). I too solved it in O(n^3) by sorting coordinates but I used midpoints of each adjacent pair of coordinates to ensure I avoided corner/edge overlaps. I don't understand why the code below works despite staring at it for a while. Can anyone help explain? Why does he take "-1" of the x2 but then check x+1 <= x2 in the inner loop? (I can see the 'x' in the inner loop includes both x1/x2).

        int X[10000], Y[10000], XS, YS, n, s, x, y;
int maxOverlap(vector <int> x1, vector <int> y1, vector <int> x2, vector <int> y2) {
	n = x1.size();
	XS = YS = 0;
	for (int i = 0; i <= n-1; i++) {
		X[++XS] = x1[i];
		X[++XS] = x2[i]-1;
		Y[++YS] = y1[i];
		Y[++YS] = y2[i]-1;
	}
	ans = 0;
	for (int i = 1; i <= XS; i++) {
		for (int j = 1; j <= YS; j++) {
			int x = X[i], y = Y[j];
			int s = 0;
			for (int j = 0; j <= n-1; j++) {
				if (x >= x1[j] && x+1 <= x2[j] && y >= y1[j] && y+1 <= y2[j]) ++s;
			}
			ans = max(ans, s);
		}
	}
	return ans;	
}
        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          This is my code,I was the winner of SRM729 div2:) x,y means a square of size 1*1 at (x,y,x+1,y+1). I check every "useful" pair of x,y and updata the ans. Sorry for poor English.

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

What is the corner case for div2 500? I see many people (including me) failed system tests.

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

4 indian members get sponsorship for hello india programming camp (2 Div1, 2 Div2 (Logic TC??))

This fag probably 2nd div2 top, registered account like 15 mins before start

Well played!

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

    We wanted to give a chance to the newbies too as the camp has three divisions of difficulty. Moreover, it is easy to verify 2 genuine coders out of the Div II list easily, their identity and information will be required for booking their bootcamp tickets. Also as per the rules, individuals are only allowed to have one account. If they create a new account, all of accounts may be suspended. Rest assured we will make sure deserving and genuine competitors get the chance

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

How to solve div1-800?

If I understand correctly, the problem can be reduced to the following (which, I believe, should be easier):

Given up to 100 positive integers (each up to 1018), you can replace value at position i with XOR of some values from its prefix (we have to include a[i] into XOR, and can decide separately for each of a[0]..a[i - 1] whether to include it or not), find LIS.

However, I haven't found a way to solve this [hopefully correctly] reduced version.

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

    The key subtask is: given numbers x, b, and a set of numbers yi, what is the smallest number of form x xor (xor of some subset of {yi}) that is  ≥ b?

    If we solve that one, we can apply it inside the standard DP to find the LIS.

    And to solve the subtask, we iterate over which bit will be the first difference with b, and then we have a subtask: a set of numbers yi, find a xor of its subset with certain higher-order bits and the remaining bits as low as possible. This is essentially solving a system of equations in Z/2Z, so we use Gaussian elimination in the right order (from higher bits to lower bits).

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

My screencast with commentary: https://youtu.be/Ugf5kbxmV_8

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

In div 2 — 800 points. I don't understand why the result of {2, 2} is 3.0. Can anyone tell me about the way to caculate the result.

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

For Div1 Medium, is there a proof that it is sufficient to use only cells on edges?

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

    Yes, actually the proof is not so hard.
    Suppose that there is a valid path, . vi is the coordinate of where the frog is on i-th step. Note that the place v2, v3, ..., vk - 1 is not necessarily on edge of the square.
    Let's think about "modifying" the path with following way, that it remains still valid, and the length of path is same or improved.
    Look at the following picture: This represents two cases (left one is case #1, and right is #2).
    Two cases
    The first case is that "x and y is both increasing or decreasing". In this case, you can compress the path, from , to . If you do this, the number of vertices decrease by one, and also the distance remains greater than or equal to d.
    The second case is the other pattern. Without loss of generality (because you can rotate arbitrarily), suppose that the y-coordinate of vx + 1 is greater than vx one and vx + 2 one. In this case, if you change the y-coordinate of vx + 1 into n - 1, obviously the distance will increase or stay equal so distance remains greater than or equal to d, and obviously the number of vertices doesn't change.
    If you repeat the process until no change occurs for any x, v2, v3, ..., vk - 1 will be on the edge of the square. Proved.

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

      Thank you for your clear explanation! I noticed that I tried to prove the following statement instead:

      If x → y → z is a valid path, there exists a cell y' on edges such that x → y' → z is a valid path.

      Thus I could't think of a shortcut in the left case.

      By the way, the statement above is correct. It seems important here that the given board is square-shaped.

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

Is there any editorial of problem div 2 — 800 points?

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

Can somebody please help me in Div 2 800 point problem. The problem is based on Expected Value and there is no editorial for this problem. Thank You.

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

    Simple trick for expected value can be used here — Dp[mask] = turns to complete game from mask. Go in backward direction with base case Dp[S] = 0. Acyclic recurrence code dp

    → Reply