Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

atcoder_official's blog

By atcoder_official, history, 3 months ago, In English

We will hold AtCoder Beginner Contest 351.

We are looking forward to your participation!

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF!

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I think they are based on the relative difficulty of each problem.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish I could AC the first five questions.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

is easy?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

GLHF!

»
3 months ago, # |
Rev. 3   Vote: I like it -7 Vote: I do not like it

Problem C was sh*t

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No you are wrong ABC359C is worse than ABC351C as a C

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +34 Vote: I do not like it

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 months ago, # |
  Vote: I like it -30 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        formatting code would increase your chances by 69% to get help

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Test case:

    3 3
    ..#
    ...
    #..
    

    Answer is 5, your code gives 3.

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

    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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 months ago, # |
Rev. 4   Vote: I like it +64 Vote: I do not like it

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

Solution
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Such a clever observation and idea!!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Neat.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      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.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So nice trick!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +14 Vote: I do not like it

    $$$D > > > F$$$

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      maybe it's even easier than C.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what did you do to make it so quick? I haven't done it yet but I've thought of segtree solution with some help of a mentor.

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          After you solved some problems using the similar trick, you'll be able to come up the idea faster too. But unfortunately CF problems aren't so obvious :(

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it +36 Vote: I do not like it

Can somebody explain their solution for problem G?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I approach problem E??

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • 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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck !

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

too many manhattan

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve F using 2 ordered multisets. thanks