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

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

We will hold AtCoder Beginner Contest 351.

We are looking forward to your participation!

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

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

GLHF!

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

why are the scoring distribution not uniform in ABC's? just a question. By uniform I meant that they vary from contest to contest.

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

GLHF!

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

I wish I could AC the first five questions.

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

is easy?

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

GLHF!

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

Problem C has to be the worst ABC problem i have ever read in my life as a noob, it was terribly difficult to understand.

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

is there any possibility to solve F using Dynamic segment tree ??

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

I might be the unluckiest man ever to get 6 second places in all ABCs while never getting the first place :( Why are these Japanese so fast :cry:

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

D gave tle please can anybody suggest

bool isValid(int nrow, int ncol, int m, int n) {
	return (nrow >= 0 && ncol >= 0 && nrow < m && ncol < n);
}

bool funCheckHash(vector<vector<char>>&grid, int r, int c) {
	int delrow[4] = { -1, 0, 1, 0};
	int delcol[4] = {0, 1, 0, -1};
	int m = grid.size();
	int n = grid[0].size();
	for (int i = 0; i < 4; i++) {
		int nrow = r + delrow[i];
		int ncol = c + delcol[i];
		if (isValid(nrow, ncol, m, n) && grid[nrow][ncol] == '#')return true;
	}

	return false;

}

int bfs(int r, int c, vector<vector<char>>&grid) {
	int m = grid.size();
	int n = grid[0].size();
	int ans = 0;
	queue<pair<int, int>>q;
	vector<vector<int>>vis(m, vector<int>(n, 0));
	vis[r][c] = 1;
	q.push({r, c});
	int delrow[4] = { -1, 0, 1, 0};
	int delcol[4] = {0, 1, 0, -1};
	while (!q.empty()) {
		auto node = q.front();
		int r = node.first;
		int c = node.second;
		q.pop();
		ans += 1;
		for (int i = 0; i < 4; i++) {
			int nrow = r + delrow[i];
			int ncol = c + delcol[i];
			if (isValid(nrow, ncol, m, n) && !vis[nrow][ncol] && grid[nrow][ncol] == '.' && !funCheckHash(grid, nrow, ncol)) {
				q.push({nrow, ncol});
				vis[nrow][ncol] = 1;
			}
			else if (isValid(nrow, ncol, m, n) && !vis[nrow][ncol] && grid[nrow][ncol] == '.' && funCheckHash(grid, nrow, ncol)) {
				ans += 1;
				vis[nrow][ncol] = 1;
			}
		}
	}


	return ans;

}
void solve() {


	int m, n;
	cin >> m >> n;
	vector<vector<char>>grid(m, vector<char>(n, 'X'));

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> grid[i][j];
		}
	}
	int ans = 1;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (grid[i][j] == '.' && !funCheckHash(grid, i, j)) {
				ans = max(ans, bfs(i, j, grid));
			}
		}
	}

	cout << ans << " ";


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

getting WA on 16 testcases for problem D, any clue what edge cases i am missing,

https://atcoder.jp/contests/abc351/submissions/52879952

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

    I guess this is the issue: fields next to magnets can (and sometimes should) be visited multiple times from different directions, so you have to either not mark them as visited, or clean them up after every traversal.

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

      Why? Can you please explain?

      Edit : Got it, a magnet adjacent cell can be an element of more than one connected component sets. Hence we need to unmark all the magnet adjacent cells or atleast have a set of pairs where we can store the magnet adjacent cells.

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

      why some test cases are failing since i did the correct way to solve this problem.

      int r[4] = { -1 , 0 , 1 , 0}; int c[4] = {0 , 1 , 0 , -1}; int cnt1 = 0; int cnt2 = 0; set<pair<int, int>> v; void solve(int i , int j , vector&arr, int n, int m, vector<vector>&vis) { if ((arr[i][j] == '@')) { if (v.find({i , j}) == v.end()) {

      v.insert({i, j});
              cnt1++;
          }
          return;
      }
      
      
      
      vis[i][j] = 1;
      cnt2++;
      // bug(i , j);
      
      for (int a = 0; a < 4; a++)
      {
          int nrow = i + r[a];
          int ncol = j + c[a];
      
          if (nrow >= 0 and nrow < n and ncol >= 0 and ncol < m and vis[nrow][ncol] == 0 and arr[nrow][ncol] != '#')
          {
              solve(nrow, ncol, arr, n, m, vis);
          }
      }

      } void solveit() {

      int n, m;
      cin >> n >> m;
      vector<string> arr;
      for (int i = 0; i < n; i++)
      {
          string s;
          cin >> s;
          arr.push_back(s);
      }
      
      
      for (int i = 0; i < n; i++)
      {
          for (int j = 0; j < m; j++)
          {
              if (arr[i][j] == '#')
              {
                  if (i > 0)
                  {
                      arr[i - 1][j] = '@';
                  }
      
                  if (i < n - 1)
                  {
                      arr[i + 1][j] = '@';
                  }
      
                  if (j > 0)
                  {
                      arr[i][j - 1] = '@';
                  }
      
                  if (j < m - 1)
                  {
                      arr[i][j + 1] = '@';
                  }
              }
          }
      }
      
      
      // bug(n, m);
      // int get = solve(1,2,arr,n,m,vis);
      int ans = 0;
      // print2d(vis);
      // bug(get);
      vector<vector<int>> vis(n , vector<int>(m, 0));
      for (int i = 0; i < n; i++)
      {
          for (int j = 0; j < m; j++)
          {
              if (arr[i][j] == '.' and vis[i][j] == 0)
              {
                  cnt1 = 0;
                  cnt2 = 0;
                  solve(i , j , arr, n, m, vis);
                  ans = max(ans , cnt1 + cnt2);
                  // bug(cnt1,cnt2);
                  // bug(v.size());
                  v.clear();
                  // cout<<endl;
                  cnt1 = 0;
                  cnt2 = 0;
              }
          }
      }
      if (ans == 0)
      {
          cout << 1 << endl;
          return;
      }
      cout << ans << endl;

      }

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

    Test case:

    3 3
    ..#
    ...
    #..
    

    Answer is 5, your code gives 3.

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

    how did you fix this issue? I'm facing the same test case wrong as said in the comments. if i just return on fields next to magnet and never mark them visited I get 11 as answer on the first test case.

    Edit: I found a way to tackle the TLE which we get for unmarking all those cells. Just use a set and set.count() which is $$$ O(log n) $$$ and then we can use set.clear() at the end of every dfs.

    Here's my submission

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

Well. ABC began to have Grid BFS again! I only remember that ABC stopped doing so several months ago. I'm bored with the similar BFS problems. The codes are long and difficult to debug.

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

I get RE in Python for problem D for 20 test cases (rest all are AC). Can someone please help what might be causing the error...

To clarify my code a bit, I have created a visited grid which records which grid locations have been visited. In the grid, all magnets are marked '#' and all cells to left right below and above are marked 'x'. Then i run dfs for all unvisited cells, in process marking the visiting cell as visited. I never mark the 'x' grid cells as visited since they can be visited multiple times from different 'regions' of dfs, and maintained a dictionary (could have used set too) to maintain which 'x' marked cells have been visited in current dfs (so that they are not revisited).

In every array access I have (I think) put in place a boundary check to make sure no index is out of range. Any help would be appreciated. Thank you.

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

    Python by default has recursion depth limited to 1000, so for large grids it gives a RecursionLimitError.

    To fix this add sys.setrecursionlimit(100000) to the beginning of your code.

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

      Oh yes, that fixed the issue. Thank you very much. I had read about this issue but I guess I hadn't been much attentive then TT.

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

Since no Editorial is available until now, it will be helpful if somebody can share their approach in $$$E$$$.

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

    I. Since the moves preserve the parity of x+y, I first split all points into two independent groups and add their results together at the end.

    II. For every group, the distance then is simply distance in 'maximum' metric ($$$max(|x_0-x_1|,|y_0-y_1|)$$$) (easy to see).

    III. To calculate the sum of distances, I first transform this metric from maximum into Manhattan, for which the solution is simple and quite well known:

    Spoiler

    IV. Finally, we need to calculate sum of differences over both coordinates, which can be done separately by sorting and maintaining sum and count of previously added elements.

    V. The final distance has to be divided by 2, which is an artifact of the transformation from point III but also easy to see when running against samples.

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

      As I understand, what you are saying means that, if we have $$$2$$$ points: ($$$x_1$$$, $$$y_1$$$) and ($$$x_2$$$, $$$y_2$$$)

      After transformation, they will be: ($$$x_1+y_1$$$, $$$x_1-y_1$$$) and ($$$x_2+y_2, x_2-y_2)$$$

      Where the Manhatten distance between the transformed points is equal to the actual distance between the original points:

      |$$$x_1+y_1-x_2-y_2|+|x_1-y_1-x_2+y_2$$$| = max(|$$$x_1-x_2|, |y_1-y_2|$$$)

      Can you please prove why this is true?

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

        You forgot the $$$\dots*2$$$ from point V in the equation, maybe that was the problem in proving it?

        If you still struggle while remembering about $$$*2$$$, try to use the general fact that $$$|t|+|u| = max(|t+u|,|t-u|)$$$, then set $$$t=x_0+y_0-x_1-y_1$$$, $$$u=x_0-y_0-x_1+y_1$$$, like you wrote out.

        But it's easier to just draw it to be honest. :)

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

          Was not aware of this one:

          |t| + |u| = max(|t+u|, |t-u|)

          which is logical since it is just taking the max between the different sign combinations.

          It makes sense now, thank you!

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

        After letting a = x1-y1, b = x2-y2, you can simplify the expression by case-analysis 1) a >= b and 2) a < b to remove the absolute operator. In both cases, the LHS and RHS of your last equation satisfy LHS = 2*RHS

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

There is a very simple solution for F (one without any data structures).

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

    Such a clever observation and idea!!

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

    Neat.

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

    how did you come up with this : $$$\sum_{1 \leq i < j \leq N} \max{{{A_j - A_i, 0}}} = \sum_{1 \leq i < j \leq N} \left( \frac{|A_j - A_i| + (A_j - A_i)}{2} \right) $$$

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

      If you realize that the $$$\max_{}:\mathbb{R}^2\to \mathbb{R}$$$ and "distance" $$$|\cdot-\cdot|:\mathbb{R}^2\to \mathbb{R}$$$ functions can be both computed by taking the cases on the maximum value then one might think that there could be a connection between the two. In fact there is the general formula

      $$$ \max_{} \{ a,b \}= \frac{|a-b|+(a+b)}{2}. $$$

      The formula might seem weird at first if you take the cases

      $$$ |a-b|=\left\{\begin{array}{ll} a-b,&a\geq b \\ b-a,& a < b \end{array}\right. $$$

      you can see how one could have come up with "the cancelation" trick in the formula.

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

    A little easier: Write $$$\max(A_j - A_i, 0) = \max(A_j, A_i) - A_i$$$. Then, the sum can be written as

    $$$\displaystyle \sum_{i = 1}^{N} \sum_{j = i + 1}^{N} \max(A_j, A_i) - A_i = \sum_{i = 1}^{N} \sum_{j = i + 1}^{N} \max(A_j, A_i) - \sum_{i = 1}^{N} \sum_{j = i + 1}^{N} A_i,$$$

    where the second sum is just the sum of $$$(N - i) \cdot A_i$$$ for all $$$1 \le i \le N$$$, and the first sum can be calculated using sorting (basically the same method as yours, but I think this is slightly more natural to think of).

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

    So nice trick!

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

I spend 1 min thinking the solution of F and 4 min for coding after the round. Oops.

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

You can check out video editorials of C, D, E, F if you are stuck

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

Can somebody explain their solution for problem G?

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

How can I approach problem E??

  • »
    »
    3 недели назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    • If you color the lattice points like a checkerboard pattern, note that the rabbit cannot switch colors. So we can split the points $$$(x, y)$$$ depending on the parity of $$$x+y$$$ and solve the problem independently for each.

    • Since the rabbit jumps diagonally we can think of changing our coordinate system, let the "x-direction" be the vector $$$(1, 1)$$$ and the "y-direction" be the vector $$$(-1, 1)$$$. This transformation turns the point $$$(x, y)$$$ into $$$(\frac{x+y}{2}, \frac{y-x}{2})$$$ and now the rabbit jumps one space horizontally or vertically. (Note: When dealing with the case where x+y is odd, you can shift the points one space in any direction to avoid fractions.)

    • Now, how do we find the total manhattan distance between each pair of points? You can solve this independently for total x distance and the total y distance.

    • For total x distance, sort the points by their x-coordinate and consider how many times each gap (in the x direction) between two points is added to the sum. It is the product of the number of points on the left and the number of points on the right. Do the same for y-coordinates.

    My solution: https://atcoder.jp/contests/abc351/submissions/52883361

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

I did problem F using ordered set. I have one doubt how can fenwick tree be used to calculate the count of elements greater than a particular number? ( actually i'm trying to code after long time, some insight would really help!)

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

    Something like this: (segtree is a segment tree with operation "sum")

    # Add an element x
    current_count = segtree.get(x)
    segtree.set(x, current_count + 1)
    
    # Find the count of elements less than x
    segtree.prod(0, x)
    

    Then subtract that from the total number of elements to find the count greater than or equal to x.

    (Note, in problem F you need to use coordinate compression otherwise the segment tree will be too large.)

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

      got it thanks, i knew this technique before just wanted some help, so what we do is co -ordinates compression since values can go upto 1e9 , but co-ordinate compression makes them limited to 1e5 () , after that we update the segment tree with value 1 at those points. Then we keep traversing again and updating the values with -1 to remove them, so the sum to [current_value, n] will give us the count of values greater than current_value.

      Thanks again, to remind me this technique again!!

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

    You can use the Fencwick tree to store $$$\sum X_{j}$$$ $$$\forall$$$ $$$X_{j} > Y_{i}$$$ $$$i \in [0, N-1]$$$ and $$$j \in [i + 1, N-1]$$$. Then you can use the formula $$$\sum X_{j}$$$ — $$$cnt(X_{j}>Y_{i})$$$ $$$*$$$ $$$Y_{i}$$$. This works because all the values $$$<=Y_{i}$$$ will contribute a $$$0$$$ to the answer. You can now reverse the array and do the operations for left side i.e for reversed array $$$j$$$ $$$\in$$$ $$$[0, i-1]$$$. Now counting elements $$$<=$$$ some elements and finding their sum can be done using Fenwick Tree. You can coordinate compress the elements since storing them would give MLE but remember their original values. Now use compressed values to iterate in the Fenwick Tree and original values to store the sum in Fenwick Tree. Calculate all the values using the formula.

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

    You're creating a new 'vis' vector for every dfs call try optimising that.

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

Good luck !

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

I think it's terribly bad to design the corner case of 0 in problem G.I just submitted the code at the last 2 minutes of the contests,and WA on the last 2 tasks.This was a terrible experience for me.

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

too many manhattan

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

How to solve F using 2 ordered multisets. thanks