Med0b1011's blog

By Med0b1011, history, 13 days ago, In English,
 
 
 
 
  • Vote: I like it  
  • +25
  • Vote: I do not like it  

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 days 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.

»
12 days ago, # |
  Vote: I like it +7 Vote: I do not like it

How to solve div2 800?

»
12 days 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)??

  • »
    »
    12 days 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.

»
12 days ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve div2 2nd and 3rd problem?

  • »
    »
    12 days 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.

    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yes, this is what I did.

      • »
        »
        »
        »
        12 days 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;	
        }
        
        • »
          »
          »
          »
          »
          12 days 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.

          • »
            »
            »
            »
            »
            »
            11 days ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Fantastic, what a great method. I thought it was "point within rectangle" but now I see, it is actually checking "1x1 square within rectangle".

            I can see this "Useful 1x1 square" idea being applicable in many such problems.

            Thanks for explaining! And congrats on your win :-)

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

    Video solution to Div2 Problem 2 here: https://www.youtube.com/watch?v=WG7RguNSNC8

»
12 days 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.

»
12 days 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!

  • »
    »
    12 days 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

    • »
      »
      »
      7 days ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      What makes you think that all people who are in div2 are newbies? The Indian guys who did well in div2 aren't. It's just that they don't take part in SRMs. I know in the end it's your wish, but it doesn't sound fair at all.

»
12 days 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.

  • »
    »
    12 days 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).

»
12 days ago, # |
  Vote: I like it +26 Vote: I do not like it

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

»
11 days 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.

»
7 days 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?

  • »
    »
    7 days 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.

    • »
      »
      »
      7 days 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.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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