AtCoder Beginner Contest 218 Announcement

3 years ago, # |

+12

My parents would rather let me participate in AtCoder contests than let me participate in Codeforces rounds, but they allow me to participate in both kinds of contests.

Imagine you're in UTC+8 and then you can figure it out ;)

→ Reply

3 years ago, # |

Nice problemset, any hints on problem H?

→ Reply

3 years ago, # ^ |

How to solve G?

→ Reply

3 years ago, # ^ |

Do dfs traversal over the tree, now you need to keep track of the median for the entire path you're in, which can be done in several ways, i used ordered sets. Supose you want to know the best posible score for a node X, if depth of node X is even, is your oponent turn, so he will get you to the lowest possible outcome, otherwise is your turn, so you maximize it, run a top-down dp and print the value for node 1.

→ Reply

3 years ago, # ^ |

Doesn't that give you TLE? (Ordered set for every node)

→ Reply

3 years ago, # ^ |

Keep a global set, in which you only keep elements contained in the path from node $$$1$$$ to node $$$X$$$, to mantain this, you can add elements when you enter a node, and delete them just before you exit it.

→ Reply

m1sterzer0

3 years ago, # ^ |

I skipped the contest this week to prep (w/ sleep) for hacker cup round 1. I'm getting around to solving these now.

As I have primarily been using python for these (although might switch to Go once I've finished building up a reasonable library), multiset wasn't available, and I didn't think to use a Fenwick tree. I'm solving it with 4 heaps. It is a bit slow (near 1.0s), but it does the job. (2 heaps for left and right insertions, and 2 heaps for left/removals) and just do the bookkeeping to cancel out the addition/removal heaps when the heads of each match).

→ Reply

OleschY

3 years ago, # ^ |

The problem statement is equivalent to placing $$$min(R,B)$$$ 2x1-Dominoes on $$$A$$$ and adding the covered $$$A_i$$$ s. But that's as far as I could get...

→ Reply

3 years ago, # ^ |

Does this cover the case when you do something like $$$AAB$$$?

→ Reply

OleschY

3 years ago, # ^ |

← Rev. 2 →

There is no need to do $$$AAB$$$ because you could do $$$ABA$$$ and get more points. $$$AAB$$$ would be the equivalent of placing the Domino on $$$A_{N-1}$$$ and the non existent $$$A_{N}$$$.

→ Reply

3 years ago, # |

+32

To be honest, I don't think the difficulty C of this contest is suitable for the difficulty of ABC's usual problem C. Otherwise, a lot of people, including me, won't do D first or even other later problems before doing C. At least for me, the implementation difficulty of D is simpler than that of C :(

→ Reply

OPyrohov

3 years ago, # ^ |

I am so depressed with a C ... It made me feel incompetent :(

→ Reply

nichke

3 years ago, # ^ |

It's a thing that's popular on AtCoder (geometrical transformations), I usually get very mad when I see them, but they occur every once in a while. It's just about simulating rotations 4 times and writing a check function with the restricted canvas, but that in itself gets very implementation heavy and ugly. There's probably a better way to solve it, but this is how I usually get AC withing ~100 lines of code.

→ Reply

3 years ago, # ^ |

Actually, I got AC with an about 40 lines and only 1.44kb code.

Click to see the code

namespace Solution {
	const int N = 207;
	int n, cnt1, cnt2; char a[N][N], b[N][N], a1[N][N], a2[N][N], a3[N][N];
	struct dist {int x, y;}dis[N * N];
	struct node {int x, y;}p[2][N * N];
	
	ib solve(char t1[N][N], char t2[N][N]) {
		F(int, i, 1, cnt1) p[0][i] = (node){0, 0};
		F(int, i, 1, cnt2) p[1][i] = (node){0, 0};
		F(int, i, 1, max(cnt1, cnt2)) dis[i] = (dist){0, 0};
		cnt1 = cnt2 = 0;
		F(int, i, 1, n) F(int, j, 1, n) {
			if(t1[i][j] == '#') p[0][++cnt1] = (node){i, j};
			if(t2[i][j] == '#') p[1][++cnt2] = (node){i, j};
		}
		if(cnt1 != cnt2) return 0;
		F(int, i, 1, cnt1) dis[i] = (dist){p[0][i].x - p[1][i].x, p[0][i].y - p[1][i].y};
		F(int, i, 2, cnt1) if(dis[i].x != dis[1].x || dis[i].y != dis[1].y) return 0;
		return 1;
	}
	
	iv Main() {
		read(n);
		F(int, i, 1, n) scanf("%s", a[i] + 1);
		F(int, i, 1, n) scanf("%s", b[i] + 1);
		int precnt1 = 0, precnt2 = 0;
		F(int, i, 1, n) F(int, j, 1, n) {
			if(a[i][j] == '#') precnt1++;
			if(b[i][j] == '#') precnt2++;
		}
		if(precnt1 != precnt2) return No, void();
		F(int, i, 1, n) F(int, j, 1, n) a1[i][j] = a[n - j + 1][i];
		F(int, i, 1, n) F(int, j, 1, n) a2[i][j] = a[j][n - i + 1];
		F(int, i, 1, n) F(int, j, 1, n) a3[i][j] = a1[n - j + 1][i];
//		F(int, i, 1, n) {F(int, j, 1, n) putchar(a3[i][j]); puts("");}
		if(solve(a, b) || solve(a1, b) || solve(a2, b) || solve(a3, b)) return Yes, void();
		return No, void();
	}
}

→ Reply

spookywooky

3 years ago, # ^ |

Thats a lot code for a C in abc.

→ Reply

3 years ago, # ^ |

Expecting for a shorter solution then...

→ Reply

utr491

3 years ago, # ^ |

smol?

#include "bits/stdc++.h"
using namespace std;

#define ll long long int
#define pb(a) push_back(a)
#define vll vector<ll>
#define loop(i, n) for (ll i = 1; i <= n; i++)
#define loop0(i, n) for (ll i = 0; i < n; i++)
#define in(i) cin>>i
#define out(i) printf("%lld", i)
#define pll pair<ll, ll>
#define vpll vector<pair<ll, ll>>
#define mp(i, j) make_pair(i, j)
#define google cout << "Case #" << tc - t << ": ";
const ll mod = 1000000007;
const ll big = 2999999999999999999;
const ll small = -2999999999999999999;
void in2(ll &a, ll &b) { cin >> a >> b; }
void in3(ll &a, ll &b, ll &c) {cin >> a >> b >> c; }
void arrayIn(vll &a, ll &n) { loop0(i, n) in(a[i]); }


void rotate90(vpll& a, ll n)
{
  loop0(i, a.size())
  {
    ll ty = a[i].second;
    a[i].second = a[i].first;
    a[i].first = -ty + n;
  }
}

void translate(vpll& a, ll xb, ll yb)
{
  loop0(i, a.size())
  {
    a[i].first -= xb;
    a[i].second -= yb;
  }
}

int main()
{
  ll n;
  cin>>n;
  vpll s, t;
  char c;
  loop0(i, n)
  {
    loop0(j, n)
    {
      cin>>c;
      if(c == '#') s.push_back({i, j});
    }
  }
  loop0(i, n)
  {
    loop0(j, n)
    {
      cin>>c;
      if(c == '#') t.push_back({i, j});
    }
  }
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  if(s == t)
  {
    cout<<"Yes\n";
    return 0;
  }
  loop0(i, 4)
  {
    rotate90(t, n);
    sort(t.begin(), t.end());
    translate(t, t[0].first - s[0].first, t[0].second-s[0].second);
    if (s == t)
    {
      cout << "Yes\n";
      return 0;
    }
  }
  cout<<"No\n";
}

→ Reply

ssvb

3 years ago, # ^ |

Seems like it makes sense to have some code templates for 2D array rotation and maybe other simple transformations to avoid wasting extra time on problems like this. It's not the first problem of this kind.

→ Reply

dhruv7888

3 years ago, # ^ |

For me G was easier than C , as it required a good amount of code and had much less points than C ( Unluckily I missed G as I had value of infinity as 998245353 rather than 10^9+7)

→ Reply

rezidentura

3 years ago, # ^ |

← Rev. 5 →

I think my answer is wrong for problem C, but It has been accepted.

Those test cases are giving me : Yes.

3
. # .
# . .
. . .
. . #
# . .
. . .

5
. . . . .
. . . . .
. . # . .
. . # # #
. . # . .
. . . . .
. . . . .
. . . # #
. . . # #
. . . # .

Am I wrong ?

Most of the people in the first page of the standings are getting "Yes" you can check if you want : https://atcoder.jp/contests/abc218/submissions/25773980

→ Reply

master._.mind

3 years ago, # ^ |

Yeah, you are right, these cases must give a "No" Output. My Submission

chokudai Please look into this.

→ Reply

rezidentura

3 years ago, # ^ |

I want to add something the test case has spaces in between.

but even after fixing that like this :

3
.#.
#..
...
..#
#..
...

I still get Yes.

→ Reply

master._.mind

3 years ago, # ^ |

The spaces wont matter as most people take the input character by character (including me).

→ Reply

3 years ago, # ^ |

My code output "No" for both the test cases. It seems that my approach is right :D

→ Reply

Hogwarts.dropout

3 years ago, # |

plz explain C,D

→ Reply

TimeTraveler

3 years ago, # ^ |

check out the editorials

→ Reply

3 years ago, # ^ |

← Rev. 3 →

→ Reply

MuheshKumar

3 years ago, # ^ |

I implemented the same logic, but getting WA on one test case and the rest of the test cases have passed.

Submission

Are there any bugs in my implementation?

→ Reply

inceptionabhi

3 years ago, # ^ |

yes, I also got WA on the same test case,

you can check, for reference

19AC1WA Submission

20AC Submission

→ Reply

Rudro25

3 years ago, # ^ |

which type of test case failed first time ??

→ Reply

3 years ago, # ^ |

← Rev. 2 →

For C, First, if only 90 degree rotation is considered, there may be only 4 patterns s at most. Then consider the translation. It can be found that you only need to see which of the four patterns mentioned above can be translated to completely match t. Specifically, we list the positions of all characters # in S and T in sequence, and then compare them one by one. Let set pattern $$$S$$$ have a amount of $$$c_1$$$ #, the position of the $$$i$$$-th # is $$$(x_{0,i},y_{0,i})$$$; pattern $$$T$$$ have a amount of $$$c_2$$$ #, the position of the $$$i$$$-th # is $$$(x_{1,i},y_{1,i})$$$, and then we just need to find out whether the following conditions are met:

$$$\forall i\in[2,n],x_{0,i}-x_{1,i}=x_{0,1}-x_{1,1}$$$
$$$\forall i\in[2,n],y_{0,i}-y_{1,i}=y_{0,1}-y_{1,1}$$$
$$$c_1=c_2$$$

Just follow this implemention. It may be a bit hard.

Code(C++)

namespace Solution {
	const int N = 207;
	int n, cnt1, cnt2; char a[N][N], b[N][N], a1[N][N], a2[N][N], a3[N][N];
	struct dist {int x, y;}dis[N * N];
	struct node {int x, y;}p[2][N * N];
	
	ib solve(char t1[N][N], char t2[N][N]) {
		F(int, i, 1, cnt1) p[0][i] = (node){0, 0};
		F(int, i, 1, cnt2) p[1][i] = (node){0, 0};
		F(int, i, 1, max(cnt1, cnt2)) dis[i] = (dist){0, 0};
		cnt1 = cnt2 = 0;
		F(int, i, 1, n) F(int, j, 1, n) {
			if(t1[i][j] == '#') p[0][++cnt1] = (node){i, j};
			if(t2[i][j] == '#') p[1][++cnt2] = (node){i, j};
		}
		if(cnt1 != cnt2) return 0;
		F(int, i, 1, cnt1) dis[i] = (dist){p[0][i].x - p[1][i].x, p[0][i].y - p[1][i].y};
		F(int, i, 2, cnt1) if(dis[i].x != dis[1].x || dis[i].y != dis[1].y) return 0;
		return 1;
	}
	
	iv Main() {
		read(n);
		F(int, i, 1, n) scanf("%s", a[i] + 1);
		F(int, i, 1, n) scanf("%s", b[i] + 1);
		int precnt1 = 0, precnt2 = 0;
		F(int, i, 1, n) F(int, j, 1, n) {
			if(a[i][j] == '#') precnt1++;
			if(b[i][j] == '#') precnt2++;
		}
		if(precnt1 != precnt2) return No, void();
		F(int, i, 1, n) F(int, j, 1, n) a1[i][j] = a[n - j + 1][i];
		F(int, i, 1, n) F(int, j, 1, n) a2[i][j] = a[j][n - i + 1];
		F(int, i, 1, n) F(int, j, 1, n) a3[i][j] = a1[n - j + 1][i];
//		F(int, i, 1, n) {F(int, j, 1, n) putchar(a3[i][j]); puts("");}
		if(solve(a, b) || solve(a1, b) || solve(a2, b) || solve(a3, b)) return Yes, void();
		return No, void();
	}
}

For D, we only need to enumerate two points, not four. Let the two points we enumerated be $$$i$$$ and $$$j$$$, and then you just need to see whether the two points $$$(x_i, y_j)$$$ and $$$(x_j,y_i)$$$ exist. Be careful not to repeat the enumeration.

Code(C++)

namespace Solution {
	int n, ans, in[2007];
	struct node {int x, y;}a[2007];
	map<pii, int> vis;
	map<pair<int, pair<int, pii> > , int> v2;
	
	iv Main() {
		read(n);
		F(int, i, 1, n) read(a[i].x, a[i].y), vis[mp(a[i].x, a[i].y)] = i;
		F(int, i, 1, n) F(int, j, i + 1, n) {
			int id1 = vis[mp(a[i].x, a[i].y)], id2 = vis[mp(a[j].x, a[j].y)], id3 = vis[mp(a[i].x, a[j].y)], id4 = vis[mp(a[j].x, a[i].y)];
			if(id1 && id2 && id3 && id4 && !(!(id1 ^ id2) || !(id1 ^ id3) || !(id1 ^ id4) || !(id2 ^ id3) || !(id2 ^ id4) || !(id3 ^ id4))) {
				int id[5] = {0, id1, id2, id3, id4};
				sort(id + 1, id + 5);
				if(!v2[mp(id[1], mp(id[2], mp(id[3], id[4])))]) ans++, v2[mp(id[1], mp(id[2], mp(id[3], id[4])))] = 1;
			}
		}
		write(ans);
		return;
	}
}

→ Reply

wowsuchempty

3 years ago, # ^ |

← Rev. 2 →

You could use a hashmap for D,(checking whether it is possible to form a rectangle with every pair of points). That would be a slightly clean implementation.

→ Reply

3 years ago, # ^ |

Yeah I know my implemention is not that simple :(

→ Reply

_runtimeTerror_

3 years ago, # |

+10

I assumed that alien trick is applicable in H and it worked lol.

→ Reply

chaudhary_19

3 years ago, # |

← Rev. 3 →

In problem E — Destruction, I got 13 tc passed and 10 wrong, can you please help me with what's wrong with my code. (When I submit, I assumed it will give me TLE)

Code

import sys
from heapq import heappush, heappop, heapify
from math import ceil
from collections import defaultdict, deque

def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_array(): return list(get_ints())
def input(): return sys.stdin.readline().strip()

n, m = get_ints()
graph = defaultdict(list)
Arr = []
ans = 0
for i in range(m):
    a, b, c = get_ints()
    if a == b:
        if c >= 0:
            ans += c
    else:
        graph[a].append(b)
        graph[b].append(a)
        Arr.append((c, a, b))

Arr.sort(reverse = True)
for i in range(len(Arr)):
    c, a, b = Arr[i][0], Arr[i][1], Arr[i][2]
    if c <= 0:
        continue
    if len(graph[a]) > 1 and len(graph[b]) > 1:
        ans += c
        graph[a].remove(b)
        graph[b].remove(a)

print(ans)

→ Reply

BlueTulpis

3 years ago, # ^ |

Just find the minimum spanning tree for E(be careful while dealing with loops and multiple edges), your answer will be $$$max(0,total\ cost-cost\ of\ MST)$$$.

→ Reply

semicolonised

3 years ago, # ^ |

I got 4 penalty's because I removed all edges even those which had negative weight. I guess that's your error too. Sort edges in non-decreasing order of weights and form a graph. If the edge forms a cycle and doesn't have weight <= 0, remove it, else add to the graph. Final answer is (Total sum of edge weights — sum of weights of included edges of graph).

Submission

→ Reply

Ray_Striker

3 years ago, # |

Is F brute force?

→ Reply

3 years ago, # ^ |

Kinda, you can bruteforce all edges inside the shortest path (at most $$$N-1$$$), for all other edges the answer remains the same.

→ Reply

3 years ago, # ^ |

Yeah, it's kinda brute force.

Spoiler

→ Reply

Ray_Striker

3 years ago, # ^ |

Thanks got it!

→ Reply

https://atcoder.jp/contests/abc218/submissions/25770296.

3 years ago, # ^ |

Oh, silly me! I didn't think of such a way in the game!

→ Reply

Math_is_Good

3 years ago, # |

C was the hardest for me :_:

→ Reply

Gary2005

3 years ago, # |

← Rev. 2 →

I use "divide and conquer" + "max,add convolution " to solve H. Bug why the answer is convex QwQ?

→ Reply

rehan_amaan_how_so_good

3 years ago, # ^ |

+17

ngl most of the in-contest solvers who use convexity often rely on proof by AC :P

→ Reply

_runtimeTerror_

3 years ago, # ^ |

+10

I saw submissions using priority queue also where they are greedily converting to red which gives maximum profit. Btw can you please elaborate your solution. Thanks

→ Reply

Gary2005

3 years ago, # ^ |

+16

dp[l][r][x][cl][cr] means considering the range from l to r , you use x red ,cl,cr is the color of two endpoints .

You can speed it up use divide and conquer .

Now you only need to solve the following problem in O(n):

Given A,B,(A,B is convex ),find C. Where

$$$ C[i]=\max_{x+y=i} (A[x]+B[y]) $$$

you can find the implement in my code :

→ Reply

3 years ago, # ^ |

I always thought that it is impossible to make $$$(max, +)$$$ convolution faster than $$$ O(n \sqrt{n} ) $$$. What is the complexity of your solution?

→ Reply

Gary2005

3 years ago, # ^ |

O(n log n).

→ Reply

3 years ago, # ^ |

Oh, so you are using convexity of the arrays to make $$$(max, +)$$$ convolution faster. That's interesting, thanks!

If someone is interested: here you can find more about this problem.

→ Reply

3 years ago, # |

← Rev. 3 →

+11

I'm pretty sure that once upon a time I've seen the problem like today's F with a weighted graph and $$$ N, M \leq 2 \cdot 10^5 $$$. Does anyone remember a similar problem and has a link to it? I think that it was at Hackerrank, but not sure.

UPD: It's basically this problem. Thanks to this solution from AtCoder :)

→ Reply

dhruv7888

3 years ago, # ^ |

← Rev. 2 →

True , I too think I have seen something very similar to this somewhere.

→ Reply

xuanji

3 years ago, # ^ |

Do you know how to solve the question for your constraints ($$$N, M \le 2 \cdot 10^5$$$)?

→ Reply

3 years ago, # ^ |

← Rev. 2 →

+13

I do! Let's take any shortest path $$$ P = ( e_1, \dots, e_k ) $$$ between $$$ s $$$ and $$$ t $$$. Obviously, we already know the solution for the edges not in $$$ P $$$. Now, for every $$$ i $$$ we want to omit the edge $$$ e_i $$$ in the shortest possible way. Let's take a moment to think what does it actually mean "to omit" $$$ e_i = (v_1, u_1) $$$. It means that there should exist another edge $$$ e = (v_2, u_2) $$$ such that $$$ d(s, v_2) \leq d(s, v_1) $$$ and $$$ d(s, v_2) + len(e) > d(s, v_1) $$$. Between all such edges we want to find one that minimizes $$$ d(s, v_2) + len(e) + d(u_2, t) $$$. We can calculate the distances from $$$ s $$$ and to $$$ t $$$ at the beginning of the algorithm and create a sweep-line-like algorithm which will be solving the problem for all edges $$$ e_i $$$ one by one by maintaining all the "good" edges $$$ e $$$ at a given moment in time. We can do that with a segment tree (probably, an ordinary set is enough but I didn't bother much). The final complexity would be $$$ O ((N + M) \log N) $$$.

My explanation is probably horrible, so I implemented the solution. Enjoy!

→ Reply

satyam343

3 years ago, # ^ |

Link

I solved this problem few days back. I copied my code to find the edges that will always be in the shortest path.

→ Reply

3 years ago, # ^ |

Thanks! Although your problem is similar and uses a lot of related ideas, I don't really see how it implies the today's F. How do you proceed after you found the edges that always are in a shortest path?

→ Reply

satyam343

3 years ago, # ^ |

There can be atmost n-1 such edges.

For each such edge, I ran a bfs from 1 and didn't use that edge. The shortest distance of n (if n is reachable) will be the answer for that edge.

→ Reply