### chokudai's blog

By chokudai, history, 4 years ago,

We will hold AtCoder Beginner Contest 176.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +93

| Write comment?
 » 4 years ago, # |   +12 Why no editorial for ABC 175 yet?!
•  » » 4 years ago, # ^ |   0 I think this blog can compensate the editorial till it comes out.https://codeforces.com/blog/entry/81458
•  » » 4 years ago, # ^ |   0 Moreover, there is no english editorial for abc 174, which was three weeks ago
 » 4 years ago, # |   +35 See you all on the scoreboard! (and on Youtube after contest)
•  » » 4 years ago, # ^ |   0 Atcoder people should start tagging SecondThead Videos in the editorials.
•  » » » 4 years ago, # ^ |   +9 No editorial for me for problem F this time, but solutions to A-E and my commentary are available here for people who are interested!
•  » » » » 4 years ago, # ^ |   0 Could you elaborate on what your time complexity for the E question is(in the average case)? At first, I thought it would be O(R*C), but then I realized that it could not be so, because, in case of massive R, C, we restrict K such to be less than equal to 2e5, so that situation gets taken care of, then I thought it would be something along the lines of O(M), but then I thought that, in case of small R and C, we can make all the cells as target cells, and then your program will go through all combinations(R*C) to find the answer.
•  » » » » » 4 years ago, # ^ |   +10 Worst case it is O(number of points). The for loop that looks n^2 only runs as long as there is a point at ever intersection it has checked. Once it has run n+1 times, it will find some intersection that doesn’t have a point in it, and break out.
 » 4 years ago, # |   +5 Please provide Editorials to learn new concepts.After the contests ended_
 » 4 years ago, # |   +9 Is it only me or the standing is loading forever. Nice problems by the way.
 » 4 years ago, # |   0 Is AtCoder predictor broken today? Seems like the performance of everyone is 2400...
•  » » 4 years ago, # ^ |   +3 Can you give the link to download ?
 » 4 years ago, # |   0 help me with D after the contest
•  » » 4 years ago, # ^ |   +5 First, give all connected components a number then put an edge between two connected components i and j if you can go from i to j using magic.In which magician initial is standing call that connected component source and the connected component in which ending point is call it destination component.Do bfs from source components and find a depth of other components. if you can reach the destination component then answer is the depth of destination component and if we can't reach the destination component then answer is -1Link to the bad implemented code
•  » » » 4 years ago, # ^ |   0 0-1 bfs is very useful here!
•  » » » » 4 years ago, # ^ |   0 actually I don't know 0-1 bfs. thanks for the info. I will learn it.
•  » » » » » 4 years ago, # ^ |   0 This is my code for problem D : https://atcoder.jp/contests/abc176/submissions/16119228
•  » » » » » » 4 years ago, # ^ |   0 What's the use of if(dp[i][j]!=val) continue; I cannot see if anytime this condition will be true.
•  » » » » » » » 4 years ago, # ^ |   0 Maybe it is useless...
•  » » » » » » » » 4 years ago, # ^ |   0 That's what i think too. They have even used that in emaxx..
•  » » » » 4 years ago, # ^ |   0 what is 0/1 bfs ??
•  » » » » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   0 Can you please help me understanding the 2nd test case of D problem, I mean why the magician can't go at (3,1) using his 1 magic spell and then move downward at (4,1)? Or It is compulsory to use move-A first and then move-B?
•  » » » » 4 years ago, # ^ |   +1 There is wall on (3,1). So you can't go there. Read the problem statement again. You can only walk on the road.It is not compulsory to use move A first and then move B. You can use any move first.
•  » » 4 years ago, # ^ |   +6 Use simple dijkastra
•  » » 4 years ago, # ^ |   0 I used 0-1 bfs to solve the problem. Pretty easy implementation (for me atleast).
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 why we add to beginning of queue if it is reachable by current node without magic otherwise at last?
•  » » » » 4 years ago, # ^ |   0 Google 0-1 bfs. Its kinda the same concept as Dijkstra.
•  » » » » » 4 years ago, # ^ |   0 so a node can appear multiple time in queue? CMIIW
•  » » » » » » 4 years ago, # ^ |   0 Yes I think it can and will.If the node was already in the queue and we just found a better distance towards it just like Dijkstra, If the edge reaching towards it was 0 weighted, it goes in the front else it goes in the back.We always process first the nodes which have 0-weighted edges reaching to them. When they are exhausted, we start using the 1-weighted edges.I hope I am not wrong.
•  » » » 4 years ago, # ^ |   0 beautifully written code nmnsharma007
•  » » 4 years ago, # ^ |   0 lol i used something like two level bfs and it got pretty complicated
•  » » 4 years ago, # ^ |   0 I did a very badly written bfs. Even I was surprised when it came AC. Idea was to use an extra waiting queue for storing all possible cells by using magic. If you don't add any cell twice in your bfs queue you should be in time limits. If bfs queue is empty I check for waiting queue elements in case they can be used. Even I am confused why it works. I am looking for some elegant solution. code
 » 4 years ago, # |   -18 Please set problems such that it's possible to come back after going back-foot or at least possible to try.
 » 4 years ago, # |   0 how to solve problem D please help??????????????????????????
•  » » 4 years ago, # ^ |   0 Dijkstra code...#include #include #include using namespace __gnu_pbds; using namespace std; #define int long long // [9,223,372,036,854,775,807 to -9.....808] 19 digits #define pb push_back #define all(x) (x).begin(),(x).end() #define mp make_pair #define vi vector #define vpi vector> #define mii map #define x first #define y second #define mem(a,x) memset(a,x,sizeof(a)) #define rep(i,a,b) for(int i=a;i, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order() // order_of_key //const int32_t hellhsh = 444440583533; const double pi=2*acos(0.0); const int32_t mod = 1e9+7; const int32_t maxn=2e5+5; int inf=1e18; int dx[5]={-2,-1,0,+1,+2},dy[5]={-2,-1,0,+1,+2}; int n,m,r1,c1,r2,c2,dp[1005][1005]; string s[1005]; void solve(){ cin>>n>>m>>r1>>c1>>r2>>c2; rep(i,0,n) cin>>s[i]; rep(i,0,n) rep(j,0,m) dp[i][j]=LLONG_MAX; r1--;r2--;c1--;c2--; dp[r2][c2]=0; priority_queue>> q; q.push(mp(0,mp(r2,c2))); while(sz(q)){ auto d=-q.top().x; auto pos=q.top().y; q.pop(); rep(i,0,5){ rep(j,0,5){ if(!dx[i] and !dy[j]) continue; int x=dx[i]+pos.x; int y=dy[j]+pos.y; if(x<0 or y<0 or x>=n or y>=m or s[x][y]=='#') continue; if((abs(dx[i])==1 and !dy[j]) or (abs(dy[j])==1 and !dx[i])){ if(dp[x][y]>d){ dp[x][y]=d; q.push(mp(-d,mp(x,y))); } } else{ if(dp[x][y]>d+1){ dp[x][y]=d+1; q.push(mp(-d-1,mp(x,y))); } } } } } if(dp[r1][c1]==LLONG_MAX) cout<<-1; else cout<>tc; while(tc--){ //cout<<"Case #"<
•  » » » 4 years ago, # ^ |   +1 can u explain a bit please?
•  » » 4 years ago, # ^ |   0 Search for 0-1 bfs.
 » 4 years ago, # |   0 ok solution of F plz
 » 4 years ago, # |   0 For D, first separate all the different regions using DFS.Then construct a graph between different regions using the trick that the magician can use.Finally ,find the shortest distance between the region of initial point and the region of final point using simple bfs (by maintaining a 'level' array).Here's my submission:https://atcoder.jp/contests/abc176/submissions/16143722
•  » » 4 years ago, # ^ |   0 I had the same idea but couldn't implement it in time
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 it took me approx 25 minutes to write the code.
•  » » » » 4 years ago, # ^ |   0 I saw SecondThread used 0-1BFS. Its a much cleaner solution in retrospect.
•  » » 4 years ago, # ^ |   0 I had the quite similiar idea, I just wanted to give similiar integer to connected components and then increase the integer for next connected component, and just return the difference of values of source and destination cells. the only problem was unreachability for this I again needed to iterate and do heck of implementation. So I rather choose to leave this problem.XD
 » 4 years ago, # |   +20 Is F a dp problem?
•  » » 4 years ago, # ^ |   0 I'm also wondering if it's dp or greedy (just can't solve it..)
•  » » » 4 years ago, # ^ |   0 well, I read dreamoon's code. It's a dp problem...
 » 4 years ago, # |   0 can problem D solved by DP?????????
•  » » 4 years ago, # ^ |   0 DSU +BFS WAS One good option to solve it!
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 hoW can you explain a bit??
•  » » » » 4 years ago, # ^ |   0 See connect all possible .s which can be connected as one component! then we have some partitions in whole matrix!. Now the cost of moving from one partition to other is to be determined , if the source and the destination dont belong to same group or cluster which we made using DSU. Put first partition in bfs queue. means the partition of the source! and from each node in this partition ,connect all other partitions that can be connected. the thing you will get is now a graph.In this graph do bfs from the source partition to the destination partition using Single Source Shortest Path Bfs!
 » 4 years ago, # |   0 how to solve E? I was trying something like O(nsqrtn) which was timing out.
•  » » 4 years ago, # ^ |   +15 hint 1answer is maximum number of bombs in a row + maximum number of bombs in a column or maximum number of bombs in a row + maximum number of bombs in a column — 1 hint 2You should choose a point with row has maximum number of bombs in a row and col maximum number of bombs in a column because : In this way you get atleast maximum number of bombs in a row + maximum number of bombs in a column — 1 otherwise you will get atmost maximum number of bombs in a row + maximum number of bombs in a column — 1 create two vectors with : 1. rows with maximum number of bombs 2. cols with maximum number of bombs hint 3if size of first vector * size of second vector > 300000 then output maximum number of bombs in a row + maximum number of bombs in a column otherwise : bruteforce on every row with maximum number of bombs and every col with maximum number of bombs hint in hint : Use a map to know you have a bomb in one cell or not code#include using namespace std; const int N = 300004; int cnth[N], cntw[N], x[N], y[N]; map mp[N]; int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int h, w, m; cin >> h >> w >> m; for (int i = 0; i < m; i++) { cin >> x[i] >> y[i]; mp[x[i]][y[i]] = true; cnth[x[i]]++, cntw[y[i]]++; } int mxh = 0, mxw = 0; for (int i = 0; i < N; i++) { mxh = max(mxh, cnth[i]); mxw = max(mxw, cntw[i]); } vector hall, wall; for (int i = 0; i < N; i++) { if (cnth[i] == mxh) { hall.push_back(i); } if (cntw[i] == mxw) { wall.push_back(i); } } int cnt = 0, mx = 0; for (int i = 0; i < hall.size(); i++) { for (int j = 0; j < wall.size(); j++) { cnt++; if (cnt > N * 2) break; mx = max(mx, mxh + mxw - mp[hall[i]][wall[j]]); } if (cnt > N * 2) break; } cout << mx; } And sorry for my poor English.
•  » » » 4 years ago, # ^ |   +3 Same logic , maps TLED my solution!
•  » » » » 4 years ago, # ^ |   +4 Not for meI get AcLink
•  » » » » 4 years ago, # ^ |   +4 I see your codeit is $O(n ^ 2)$ and should get TLE
•  » » » » » 4 years ago, # ^ |   0 Ya I just saw the problem wrong ! and brute forced , but now I got AC using sets instead of matrices , concept is yet same but!, nice proof is that we will iterate in the nested loop at max 3e5 times due to pigeonhole principle. This principle I saw just now!,good problem a very good problem , nice proof involved!
•  » » » 4 years ago, # ^ |   +2 Thank You for the great explanation. Made things up clear.
• »
»
»
4 years ago, # ^ |
Rev. 2   -6

# include<stdio.h>

int main() { long long a,b,c,d,e,f,g,h,i,j,k,l; scanf("%lli",&a,&b,&c); int z[a][b]; for(d=0;d<a;d++) { for(e=0;e<b;e++)z[d][e]=0; } for(;c;c--) { scanf("%lli%lli",&d,&e); z[d-1][e-1]=1; } long long y[a],x[b]; for(d=0;d<a;d++) { for(e=f=0;e<b;e++) { if(z[d][e])f++; } y[d]=f; } for(d=0;d<b;d++) { for(e=f=0;e<a;e++) { if(z[e][d])f++; } x[d]=f; } for(d=f=0;d<a;d++) { for(e=0;e<b;e++) { g=y[d]+x[e]; if(z[d][e])g--; if(g>f)f=g; } } printf("%lli\n",f); return 0; }

I wrote this for E. But I got error : warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]

What is the reason for that? Only some test sets return this error, rest give AC. Do you have any suggestion?

https://atcoder.jp/contests/abc176/submissions/16135523 Submission link. Sorry for the wrong formatting

•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +10 This error, which is not actually an error but a warning, has nothing to do with why your solution fails.scanf returns the number of variables that were succesfully parsed and set or EOF if none were due to reaching end of file and is declared with attribute((warn_unused_result)) because if you're using it outside competitive programming you should to some extend keep in mind the possibility that the file you're reading is corrupted or something and at least check if the value is what it is supposed to be, but for competitive programming you can pretty much just ignore this warning.If you don't want it to pop up to have better chance of spotting a warning referring to something which actually might be wrong, or just because it's annoying you can use -Wno-unused-result flag for compilationAnd the reason your solution gets RE verdict is pretty simple. int z[a][b]; declares an array with $a\cdot b$ elements which can be up to $9\cdot 10^{10}$ and by far exceed memory limit
•  » » » 4 years ago, # ^ |   +6 if size of first vector * size of second vector > 300000 then output maximum number of bombs in a row + maximum number of bombs in a column.if size <300000 then how can we be sure that ans is maximum number of bombs in a row + maximum number of bombs?
•  » » » » 4 years ago, # ^ |   +3 if size < 300000 then of course you can iterate through all the combinations of row and column in the first vector and second vector...then find out if the pair from the combination, for example (r, c), exists in the input. If so, then ans = max num of bombs in a row + max num of bombs in a column — 1
•  » » » » » 4 years ago, # ^ |   +3 Ops typo I wanted to ask if size>300000.But I got my ans as there is atmost 300000 bombs so if size>300000 then we can be sure that there must be at least one maxrow and maxcol without intersecting bomb.
•  » » » » » » 4 years ago, # ^ |   0 Exactly! Glad that you understand this bit. Cheers
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 edit- my solution is wrong tho it was AC
•  » » » 4 years ago, # ^ |   0 What's the idea behind it? I did exactly same as Dorost
•  » » » » 4 years ago, # ^ |   0 The idea is that we are trying to fix one row and then choosing the column which have maximum number of bombs and vice versa for column.
•  » » » 4 years ago, # ^ |   0 I did the same approach
•  » » » 4 years ago, # ^ |   +14 Countertest3 3 5 1 1 1 2 2 1 2 3 3 2 I really can't believe problemsetters made 130 tests and couldn't defeat this solution
•  » » » » 4 years ago, # ^ |   0 is the answer 4?
•  » » » » » 4 years ago, # ^ |   0 Yes
•  » » 4 years ago, # ^ |   +3 My solution is choosing the coordinate x,y that could maximize the target.The answer is the number of targets that x hit + the number of targets that y hit — (there is a target at coordinate (x,y)).
•  » » 4 years ago, # ^ | ← Rev. 4 →   +8 Let $r[i]$ be the number of targets in row $i$, and $c[j]$ be the number of targets in columns $j$. Then the answer is $\max(r) + \max(c)$ unless for every pair $i, j$ such that $r[i] == \max(r)$ and $c[j] == \max(c)$, we have a target at $(i, j)$ (if the intersection of a pair doesn't have a target, we can simply choose that pair). Otherwise, the answer is $\max(r)+\max(c)-1$ (no matter what, we overcount the target at the intersection). This is equivalent to the following: If $x$ is the number of rows $i$ with $r[i] == \max(r)$, $y$ is the number of columns $j$ with $c[j] == \max(c)$, and $z$ is the number of targets with coordinates $(i, j)$ satisfying $i == \max(r)$ and $j == \max(c)$, then the answer is $\max(r)+\max(c)-(x*y == z)$.
•  » » 4 years ago, # ^ |   0 were you using unordered_map?
•  » » 4 years ago, # ^ |   0 I did this and got AC Codeimport sys,bisect from sys import stdin,stdout from bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right from math import gcd,ceil,floor,sqrt from collections import Counter,defaultdict,deque,OrderedDict from queue import Queue,PriorityQueue from string import ascii_lowercase sys.setrecursionlimit(10**6) INF = float('inf') MOD = 998244353 mod = 10**9+7 def mp(): return map(int,stdin.readline().split()) def pr(n): stdout.write(str(n)+"\n") def solve(): r,c,m=mp() row={} col={} dd={} d={} for i in range(m): a,b=mp() row[a]=row.get(a,0)+1 col[b]=col.get(b,0)+1 if a in d: d[a].add(b) else: d[a]={b} if b in dd: dd[b].add(a) else: dd[b]={a} miR,miC=float('-inf'),float('-inf') for i in row: if row[i]>miR: miR=row[i] R=i for i in col: if col[i]>miC: miC=col[i] C=i ans=float('-inf') for i in col: c=miR+col[i] if i in d[R]: c-=1 ans=max(ans,c) for i in row: c=miC+row[i] if i in dd[C]: c-=1 ans=max(ans,c) pr(ans) for _ in range(1): solve() 
•  » » 4 years ago, # ^ |   0 My submission : https://atcoder.jp/contests/abc176/submissions/16163575 Count number of points for in each row and each column. Then find the columns and rows that have maximum points (Sort). In case there are multiple rows(columns) with max value, find if there is atleast one point among them that doesn't have target. If you found such a point answer is max row value + max column value. Else just subtract 1 from it
•  » » » 4 years ago, # ^ |   +10 #include #define ll long long #define fo(i,n) for(int i=0;i=0;i--) #define Fo(i,q,n) for(int i=q;i=q;i--) #define fO(i,n,k) for(int i=0;i void print(T var1, Types... var2){cout << var1 << " " ;print(var2...) ;} //ceil of a/b template T fceil(T a,T b){return (T)(a+b-1)/b;} //const int N=2e5; //int arr[N+1]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int h,w,m; cin>>h>>w>>m; vector rows(h,0); vector cols(w,0); int x,y; map< pair ,int>dict; fo(i,m){ cin>>x>>y; x--;y--; rows[x]+=1; cols[y]+=1; dict[mp(x,y)]=1; } vector< pair > rc; fo(i,h){ rc.pb(mp(rows[i],i)); } vector< pair > cc; fo(i,w){ cc.pb(mp(cols[i],i)); } sort(rc.rbegin(),rc.rend()); sort(cc.rbegin(),cc.rend()); vector< pair > rcp; vector< pair > ccp; int rmax = rc[0].F; int cmax = cc[0].F; int k=0; while(k<(int)rc.size() && rc[k].F==rmax){ rcp.pb(rc[k]); k++; } k=0; while(k<(int)cc.size() && cc[k].F==cmax){ ccp.pb(cc[k]); k++; } int flag=1; fo(i,(int)rcp.size()){ fo(j,(int)ccp.size()){ if(dict[mp(rcp[i].S,ccp[j].S)]==0){ flag=0; break; } } } cout<
 » 4 years ago, # |   +1 How to solve E???
•  » » 4 years ago, # ^ | ← Rev. 2 →   +2 The final answer would be either be the maxRowsum + maxColSum or maxRowsum + maxColSum -1(where maxRowSum means maximum number of targets in a row considering all rows and maxColSum means maximum number of targets in a column considering all columns).We need to find all rows having number of targets equal to maxRowSum and all columns having number of targets equal to maxColSum and then check for each one of them whether there exists a combination of them where the common element isn't a target.If such combination exists then answer would be maxRowsum + maxColSum otherwise maxRowsum + maxColSum -1.We could use map to check whether a co-ordinate is a target or not. My submission:-E — Bomber
•  » » » 4 years ago, # ^ |   +1 Understood.Thanks a lot.
•  » » » 4 years ago, # ^ |   0 I did the same thing I think, then why tle for 3 cases? #include using namespace std; #define ll long long #define in(a) ll a; cin>>a; #define in2(a,b) ll a,b; cin>>a>>b; #define in3(a,b,c) ll a,b,c; cin>>a>>b>>c; #define in4(a,b,c,d) ll a,b,c,d; cin>>a>>b>>c>>d; #define in5(a,b,c,d,e) ll a,b,c,d,e; cin>>a>>b>>c>>d>>e; #define lelo(b) for(auto &i:b)cin>>i; #define ff first #define ss second #define call(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define show(x) for(auto t:x)cout< pii; typedef vector vii; typedef vector vi; const ll mod=1e9+7; const ll N=4e5+5; void solve(){ in3(h,w,m); ll s=m; vii cor; while(s--){ in2(x,y); cor.pb({x,y}); } vi row(h+1,0),col(w+1,0); map hash; for(ll i=0;imaxi1){ maxi1=row[i]; } } for(ll i=1;i<=h;i++){ if(row[i]==maxi1){ ind1.pb(i); } } ll maxi2=-1e9; vi ind2; for(ll i=1;i<=w;i++){ if(col[i]>maxi2){ maxi2=col[i]; } } for(ll i=1;i<=w;i++){ if(col[i]==maxi2){ ind2.pb(i); } } bool f=0; for(auto j:ind1){ for(auto i:ind2){ if(!hash[{j,i}]){ f=1; } } } ll ans=maxi1+maxi2-(f==0); ce(ans); } int32_t main(){ // jaldi ll t; // cin>>t; t=1; while(t--){ solve(); } } 
•  » » » » 4 years ago, # ^ |   0 I think you need to break as soon as f = 1 happens because the number of empty cells you find can be huge but non empty ones have a limit as mentioned in the question.
 » 4 years ago, # |   0 My D TLEd on just 1 test-case.
•  » » 4 years ago, # ^ |   0 Simple bfs like this won't work. You have to use dijkastra
•  » » » 4 years ago, # ^ |   +20 0-1 bfs passed easily.
•  » » » » 4 years ago, # ^ |   0 What is 0-1 BFS?
•  » » » » » 4 years ago, # ^ |   0 I learned it from this blogSolved problem D using it too.
 » 4 years ago, # |   -11 Give problems where you need to at least think. Not put D where you need to just write a dijkastra without even thinking
•  » » 4 years ago, # ^ |   0 Sir I had to think, maybe I'm dumbCould you please help me? https://atcoder.jp/contests/abc176/submissions/16151561
•  » » » 4 years ago, # ^ |   0 Your solution isn't handling updates. Like let's say you can go to node $x$ from node $y$ in $3$ sec but from node $z$ to node $y$ in $2$ sec. And you processed node $x$ before node $z$. Then, you are not updating with $z$ and that produces WA.To handle updates efficiently, we use dijkastra algorithm.dijkastraAll you have to do is doing the same thing you did, just applying dijkastra instead of dfs
•  » » » » 4 years ago, # ^ |   0 But sir at every node "n", I'm storing the minimum magic needed to reach (dh, dw) from n.So I won't matter right, in how many magic I reached n.Hope i didn't misinterpreted what you said. If you could give a testcase that'll be helpful.
•  » » » » » 4 years ago, # ^ |   +3 I don't have testcase anyway, but I think this is why it's incorrect. You obviously updated $dp[y] = 3$ via $x$ then you went to $z$ after some operations. Now, since $dp[y] != INF$ then, you are not updating according to your code if I understood your code correctly.
•  » » 4 years ago, # ^ |   +11 That's why it is called beginner contest.I couldn't able to solve D because I don't know dijkastra, but now I got some insight of this algorithm due to this problem.
•  » » » 4 years ago, # ^ |   +1 It's better to give a dijkastra problem with little insight in E instead. They can give same difficulty level binary search or greedy problem where you need to think before applying binary search. Even div3 problems consider having some insights. Otherwise, it's like saying, implement dijkastra algorithm.And yeah, you could have still learnt dijkastra if they put a problem on this algo with a little insight.
•  » » 4 years ago, # ^ |   0 I solved with bfs only think of each connected without magic roads as a single cluster, using DSU and then applying bfs over the connected components. This took me around 1 hour for me to think of and implement heavily ,but I think that it wasnt required as ya Dijskarts is applicable.
•  » » » 4 years ago, # ^ |   0 It's a lot of implementation anyway. They can give this kind of problems in unrated contests like educational dp contest.
 » 4 years ago, # |   0 warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]I am getting this error on question E: Bomber. Can anyone help me out?
•  » » 4 years ago, # ^ |   0 That isn't the problem. h * w can be 1e10 and you can't have array with that size.
 » 4 years ago, # |   +6 Why editorials is not posted in atcoder now-a-days?? I am waiting for previous ABC-175 contest for 8 days but still there is no editorial.
 » 4 years ago, # |   0 Could someone please tell why my ans for D is failing?https://atcoder.jp/contests/abc176/submissions/16151561
 » 4 years ago, # |   0 How to solve D?
•  » » 4 years ago, # ^ |   +3 Clean solution using Dijkstra
 » 4 years ago, # |   -8 This is my first time participating in atcoder contest , and how can i see my rating change or rating changes later ?
•  » » 4 years ago, # ^ |   0 https://atcoder.jp/users//historybut do wait atleast 10 contests for an actual rating
 » 4 years ago, # |   +14 Problem E is really nice and simple, liked it
•  » » 4 years ago, # ^ |   0 I also liked problem E and able to solve it in the contest but I can't able to solve D.
•  » » 4 years ago, # ^ |   0 I liked the main idea. Real cool problem
 » 4 years ago, # |   0 Can anyone help me with my submission of Problem E? It shows Runtime Error https://atcoder.jp/contests/abc176/submissions/16150109
•  » » 4 years ago, # ^ |   -6 You cannot make a matrix of size h*w, as h and w can both be equal to 3*10^5
•  » » » 4 years ago, # ^ |   +3 oh i missed it what is the approach then?
•  » » » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   0 https://atcoder.jp/contests/abc176/submissions/16135523 Can you please suggest me also why I get RE?
•  » » » » 4 years ago, # ^ |   0 bro ,the size of the matrix you created is very large of the order 10^10
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Oh, So how can I tackle it? And also what is the max size of array possible?
•  » » » » » » 4 years ago, # ^ |   +1 size of Array <= 10^7 also you can follow this for solving problem E.
•  » » » » » » 4 years ago, # ^ |   0 check this out https://atcoder.jp/contests/abc176/submissions/16156313
 » 4 years ago, # |   +82 how to solve F
•  » » 4 years ago, # ^ |   +14 At first, I was trying to solve in anyway. After every move we will have two items left. We can do a $dp[i][left_1][left_2]$ where we do the operation on items $left_1$, $left_2$, $i$, $i+1$, $i+2$. This way we can solve in $O(n^3)$ which is too large. But I started thinking about these pairs $(left_1, left_2)$ because we can iterate over them.So I tried to somehow store all pairs $(j, k)$ for $j, k \lt i$ and update the answers using items $i$, $i+1$, $i+2$, as well as insert new pairs.To solve all transitions we just need these 5 functions. I will call color as the number written on a card. add(i, j, val): insert the pair (i, j) with value val get_max(c): returns the maximum value of a pair with both cards equal to the color c get_max(id, c): returns the maximum value of a pair where one card has index id and the other has color c get_max(id): returns the maximum value of a pair where one card has index id lazy_inc(): lazily increments the value of all pairs by one All of them can be implemented in O(1). Let me know if this is enough.
•  » » 4 years ago, # ^ |   +29 SpoilerWe process the cards in groups of three — we hold two cards, pick the next three cards, then decide which two we want to keep. We can solve it in $O(N^3)$ using DP with states $dp(position, card1, card2)$, and optimize it to $O(N^2)$ with states $dp(card1, card2)$ with the additional constraint that either the first or second card must be at the last group of three we processed. From the current state, we can either transition to the next immediate group of three, or find the next occurrence of the first (or second) card type and transition to that group of three, ignoring the groups in between. The intuition behind the second transition is that we decided to keep the first (or second) card type for future points, so we can ignore all groups not containing it.My submission: https://atcoder.jp/contests/abc176/submissions/16141029
 » 4 years ago, # |   -11 are there any system tests in atcoder?
•  » » 4 years ago, # ^ |   +2 No
 » 4 years ago, # | ← Rev. 2 →   -6 For D, I treated each connected component as a node of a graph and then used bfs to find the shortest path.Lengthy implementation. Is this the intended solution or is there a easier way to do this?
•  » » 4 years ago, # ^ |   0 I solved D with 0-1 bfs. Or compress roads with DSU and BFS
 » 4 years ago, # |   0 **See My Luck !!!** **contest end at 19:40 in my country..and i submit the right solution of E at 19:39 but forgot to remove my debug comment for rush...** 
•  » » 4 years ago, # ^ |   0 It's better to print your debug statements in standard error stream. That may increase the runtime to a certain extent(if you print a lot of lines), however it is highly likely that it gets AC.
 » 4 years ago, # |   0 can anybody please help me out to find error in my solution of problem E https://atcoder.jp/contests/abc176/submissions/16135136
•  » » 4 years ago, # ^ |   0 There could be different indices for which values is maximize.
•  » » » 4 years ago, # ^ |   0 thanks bro it really works
 » 4 years ago, # |   0 For problem E, I get we have to find the row and column with maximum number of targets, and the answer is at least (sum of targets in the selected row and column)-1. But the maximum possible answer could be sum of targets in selected row and column, in case there is no target at the intersection of the chosen row and column. Since AtCoder has apparently stopped releasing English editorials, could anyone explain how to find this maximal answer?
•  » » 4 years ago, # ^ |   +18 Count pairs from given points Code#include "bits/stdc++.h" using namespace std; #define sz(x) (int)(x.size()) #define FOR(i,L,R) for(int i = L; i <= R; i++) const int N = 3e5 + 2; int n, m, cnt_x[N], cnt_y[N]; set> given; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int32_t main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n >> m; int t; cin >> t; while(t--) { int x, y; cin >> x >> y; given.insert({x, y}); cnt_x[x]++; cnt_y[y]++; } int maxx = 0, maxy = 0; set whichx, whichy; FOR(i,1,N-1) { maxx = max(maxx, cnt_x[i]); maxy = max(maxy, cnt_y[i]); } FOR(i,1,N-1) { if(cnt_x[i] == maxx) { whichx.insert(i); } if(cnt_y[i] == maxy) { whichy.insert(i); } } int cnt_pairs = 0; for(auto& p : given) { int x = p.first; int y = p.second; if(whichx.count(x) && whichy.count(y)) cnt_pairs++; } if(cnt_pairs == sz(whichx) * sz(whichy)) cout << maxx + maxy - 1; else cout << maxx + maxy; } 
•  » » 4 years ago, # ^ |   +5 Store the rows with maximum bombs, same for columns. What I did is $rowsize * colsize > m$ then, $ans = rowmax + colmax - 1$, else, we can iterate over rows and cols and check the possible outcome.
•  » » » 4 years ago, # ^ |   0 Thanks, this is what I wasn't able to think of, I was thinking there would be some clever way without brute-force. PS. I think you made a small typo, the condition should be: $rowsize∗colsize>m$ then, $ans=rowmax+colmax$.
•  » » » » 4 years ago, # ^ |   0 No, think of $(1, 1)$, $(2, 2)$, $(3, 3)$. Here, $m = 3$, $rowsize = 3$, $colsize = 3$, $rowmax = 1$, $colmax = 1$, $ans = 1$
•  » » » » » 4 years ago, # ^ |   0 Place the bomb in (1,3) or (3,1) — ans is 2 (= rowmax + colmax).The condition makes sense because corresponding to $rowmax$ rows and $colmax$ columns, there are $rowmax * colmax$ points of intersections of the rows and columns. If $rowmax * colmax > m$, then at least one of these intersections doesn't have a target, and then you can actually have $rowmax + colmax$ targets destroyed. And I also got AC using this condition (line 28): https://atcoder.jp/contests/abc176/submissions/16158977
•  » » » » » » 4 years ago, # ^ |   +5 Ohh, I said $rowsize$ and $colsize$, my approach is somewhat different than yours.Looks like I am not being able to get my words. Here is my one.This
•  » » » » 4 years ago, # ^ |   0 There is a solution that doesn't require iterating over all possible combinations of best rows and best columns.First, store the row coordinates of every row that has the best/maximum value in an $unordered\text{_}set$. Let the size of this set be $size_r$. Note that a column is useless to us when every maximal row has a point in that column. So, all we need is a way to calculate the number of points in every column taking into account only maximal rows.We can do this by simply maintaining a $map$, where $map[i]$ gives us the number of points in the $i^{th}$ column for every maximal row. You can do this by iterating over every point and if the current point's $x$-coordinate belongs to a maximal row (which we can check using the unordered set) then we increment $map$ for this point's $y$-coordinate. In the end, loop over every maximal column $y_i$, and if $map[y_i] •  » » » » » 4 years ago, # ^ | 0 You can do this by iterating over every point and if the current point's x-coordinate belongs to a maximal row ...That is the same thing as brute-force. •  » » 4 years ago, # ^ | 0 Hello sir, I did it using the following steps: 1. Find the maximum number of the target present in any row 2. Find the maximum number of the target present in any column 3. I iterated over the columns and see how much score we can get if we choose the row which we get from step 1 and given column, but if we get any target at the intersection point of these two we need to subtract one from the score and find the maximum score in all the chosen columns with the row from step 1 4. I iterated over the rows and see how much score we can get if we choose the column which we get from step 2 and given row, but if we get any target at the intersection point of these two we need to subtract one from the score and find the maximum score in all the chosen rows with the column from step 2 Codeimport sys,bisect from sys import stdin,stdout from bisect import bisect_left,bisect_right,bisect,insort,insort_left,insort_right from math import gcd,ceil,floor,sqrt from collections import Counter,defaultdict,deque,OrderedDict from queue import Queue,PriorityQueue from string import ascii_lowercase sys.setrecursionlimit(10**6) INF = float('inf') MOD = 998244353 mod = 10**9+7 def mp(): return map(int,stdin.readline().split()) def pr(n): stdout.write(str(n)+"\n") def solve(): r,c,m=mp() row={} col={} dd={} d={} for i in range(m): a,b=mp() row[a]=row.get(a,0)+1 col[b]=col.get(b,0)+1 if a in d: d[a].add(b) else: d[a]={b} if b in dd: dd[b].add(a) else: dd[b]={a} miR,miC=float('-inf'),float('-inf') for i in row: if row[i]>miR: miR=row[i] R=i for i in col: if col[i]>miC: miC=col[i] C=i ans=float('-inf') for i in col: c=miR+col[i] if i in d[R]: c-=1 ans=max(ans,c) for i in row: c=miC+row[i] if i in dd[C]: c-=1 ans=max(ans,c) pr(ans) for _ in range(1): solve()  •  » » 4 years ago, # ^ | ← Rev. 2 → +5 Check for every row and column indices for which it gives maximum values, there will not be more than 3 X 10 ^ 5 such pairs.  » 4 years ago, # | 0 If anyone need short explanation & implementation for A-E Here •  » » 4 years ago, # ^ | ← Rev. 2 → 0 In problem E, What if all the cells in the given matrix contain targets ? How many pairs of row and columns will be there containing maximum number of targets. •  » » » 4 years ago, # ^ | 0 3e5 as there can be at most 3e5 target , See the constraint m is min(h*w,3e5) •  » » » » 4 years ago, # ^ | +1 Now I got it, I was missing the constraints.  » 4 years ago, # | 0 why does simple (bfs || dfs) && dp get TLE on problem D ? •  » » 4 years ago, # ^ | +17 depends what you mean by simple. Most poeple's "simple" bfs or dfs didn't TLE. •  » » » 4 years ago, # ^ | 0 that's why i'm confused , i implemented same approach as SecondThread in C++ with queue but it got TLE . but with Set it doesn't •  » » » » 4 years ago, # ^ | ← Rev. 2 → +2 I see in my crystal ball that your line 136 is not optimized. Correct it.If you want more details, be smarter, paste your code on some pastebin or something, so we can analyze it -_-Big chances that you fucked up at your "already visited structure" (when you check or you update this, maybe you're not doing it at the best time, so you have a lot of duplicated nodes with the same distance and coordinates in your queue). •  » » » » » 4 years ago, # ^ | 0 people already posted tled submissions and mine is also same approach . here : https://pastebin.com/uKndTwVJ •  » » » » » » 4 years ago, # ^ | 0 Its 0-1BFS using deque, you are running normal BFS. •  » » » » » » 4 years ago, # ^ | +1 If you have a graph like this: 8 13 1 1 1 13 .#.#.#.#.#.#. .#.#.#.#.#.#. .#.#.#.#.#.#. .#.#.#.#.#.#. .#.#.#.#.#.#. .#.#.#.#.#.#. .#.#.#.#.#.#. ............. You will see you treat a lot of times the same coordinates (each time finding all the neighbors of this coordinate and so on...).Even with a set you have risks to have the same problem (even if it migitates some cases, because of removing duplicates): you can visit way too many times the same coordinate, but not necesarily when the coordinate is already in queue (if you take my input again, you can visit (1,3) right after (1,1), but finding that there is a better distance after when you go down without crossing walls). •  » » » » » » » 4 years ago, # ^ | 0 thanks for reply , i get it but https://pastebin.com/ppdDPJFL this code didn't get TLE , aren't they doing same ? i guess java's ArrayDeque is faster (?) •  » » » » » » » » 4 years ago, # ^ | ← Rev. 4 → +1 They aren't doing the same : xs.addFirst(nx); ys.addFirst(ny); when no teleportations xs.addLast(x); ys.addLast(y); when teleportations.I let you find by yourself why is it better.Hint: try to proove by induction that the resulting deque will always treat nodes by increasing distances (the proof only works because it's a "0-1 BFS" as said previously). •  » » 4 years ago, # ^ | 0 what dp are you talking about?  » 4 years ago, # | +9 Screencast of getting a thousand wrong ideas for F, rambling about Dial's algorithm, and somehow beating my last performance with 1/4 the effort (+ (possibly overly elaborate) editorial for A-E) •  » » 4 years ago, # ^ | 0 Can you explain the correct approach of F also? •  » » » 4 years ago, # ^ | 0 Sorry, I don't know how to do it :(I got a few ideas but none of them worked out in a passable complexity.  » 4 years ago, # | -25 WHY mifafaovo is not in top rated list? •  » » 4 years ago, # ^ | 0 As she haven't competed in last 6 months and old users are not included in ranklist at Codeforces  » 4 years ago, # | +8 Probably not helpful even with google translate, but the person who got first AC for F wrote an editorial for the round in japanese: https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2020-08-22abc-176 •  » » 4 years ago, # ^ | -8 Google Translate works fine for me, Try again  » 4 years ago, # | +14 I’m writing an unofficial editorial for ABC176 too. I’m going to post it tomorrow or the day after tomorrow. •  » » 4 years ago, # ^ | -20 dont do that •  » » » 4 years ago, # ^ | 0 Since I can read Japanese, I will do. If you don't want to read it, just ignore me. •  » » 4 years ago, # ^ | 0  » 4 years ago, # | 0 Hello, can someone please help me on D?https://atcoder.jp/contests/abc176/submissions/16163382I've tried basically all the ideas I had but still get WA on the max case.  » 4 years ago, # | 0 What's wrong in this code: https://atcoder.jp/contests/abc176/submissions/16165157 All i did was get the number of targets in each row and each column in two separate maps and if we see the sq with bomb the destroyed are 1 less than the sum of the two maps for the given key else it would be the sum. Thank you for helping! •  » » 4 years ago, # ^ | 0$h$and$w$can be up to$3*10^5$you cant declare array of that size. MLE + TLE  » 4 years ago, # | ← Rev. 2 → 0 Can anyone help me with E number problem please? I can't figure out why i'm getting WA for 4 test cases for this solution. Link: https://atcoder.jp/contests/abc176/submissions/16166033For any kind of help, thanks in advance •  » » 4 years ago, # ^ | ← Rev. 2 → 0 Try this test : Test7 4 8 1 1 1 2 2 4 3 1 4 3 4 4 6 2 7 1 Picturebomb should be on green 'a'. sorry my drawing is not good.Your answer : 4Correct answer : 5  » 4 years ago, # | 0 What's wrong with this method for D? I first do a BFS from starting point and mark all the reachable nodes as visited and it would take 0 moves to move to any of them. Then I do a BFS from ending point and find distance to all the reachable nodes. Now, I do a brute force over all reachable nodes from starting point, and the number of moves required to reach that point would be 0 as we go there from starting point without using any move B and then to reach end point from that node, I find distance of ending point from this node which would be same as distance of this node from ending point, and then take minimum over all possible answers. •  » » 4 years ago, # ^ | 0 I think the normal BFS approach will not work in this situation. You should either use BFS 0-1 or Dijkstra algorithm.For me, I use the Dijkstra algorithm to solve it. You can see it in here. An useful link to learn about BFS 0-1: here •  » » » 4 years ago, # ^ | 0 I solved it using 0-1 BFS only but was looking for a flaw in that approach which I got now.  » 4 years ago, # | ← Rev. 2 → +73 Here's my solution for F that I got in contest but couldn't implement in time :PProblem F solution:View the problem as you always have a "hand" of two cards, and break the rest of the cards into groups of$3$(except the last group, which is group of size$1$). Index these groups from$1$to$n$. You can treat this as moving left to right from the groups, and each turn, you can exchange some of your cards for cards in the group (or do nothing). Each time you form a set of$3$equal cards in a group, you get a point. For the card at index$i$, let$label[i]$denote the index of the group it's in. Now, for any group with$3$cards of all the same value, we can ignore that group because it's optimal not to touch it and just take the point. For example, a list of cards$1, 1, 2, 3, 3, 2, 2, 2, 1$is broken into$(2, 3, 3), (2, 2, 2), (1)$with a starting hand of$(1, 1)$. We then remove the group$(2, 2, 2)$, so all we have to do is examine$(2, 3, 3), (1)$, where these groups are labeled$1, 2$. Consider the$dp$state$dp[i][j]$, where$i
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Am I understanding this right?Suppose we had a dp[i][j][k] where i and j denote the indices of the cards and k the group index.....now you claim that atleast one of the two cards will be from the group k thereby reducing complexity from n^3 to n^2 as then j(assuming i
•  » » » 4 years ago, # ^ |   0 Yes, we only need to consider $k = label[j]$, the group the card $j$ is in.
•  » » 4 years ago, # ^ |   0 Thanks a lot for taking out the time to write this detailed explanation!
 » 4 years ago, # | ← Rev. 2 →   +3 Personal editorial for ABC176
•  » » 4 years ago, # ^ |   0 Looks quite good. How did you make the blog. Its look and feel is good. Which framework did you use as I also want to put my blog like yours.
•  » » » 4 years ago, # ^ |   +8 I use vuepress.
 » 4 years ago, # |   -8 Can anyone please provide me DFS solution for ques D please...
 » 4 years ago, # |   0 can anyone tell me what is wrong with my code for problem D? code Link : https://atcoder.jp/contests/abc176/submissions/16215981
•  » » 4 years ago, # ^ |   0 It's only problem in 4 test case..
 » 4 years ago, # | ← Rev. 2 →   0 import java.io.IOException; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner s=new Scanner(System.in); int h=s.nextInt(); int w=s.nextInt(); int m=s.nextInt(); int a[][]=new int[h+1][w+1]; for(int i=1;i<=m;i++){ int x=s.nextInt(); int y=s.nextInt(); a[x][y]=1; } for(int i=1;i<=h;i++){ int count=0; for(int j=1;j<=w;j++){ count+=a[i][j]; } a[i][0]=count; } for(int j=1;j<=w;j++){ int count=0; for(int i=1;i<=h;i++){ count+=a[i][j]; } a[0][j]=count; } int ans=0; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ int curr=a[0][j]+a[i][0]; if(a[i][j]==1){ curr--; } ans=Math.max(ans,curr); } } System.out.println(ans); } } I am getting RE in problem E. If someone can help it would be great, I am new to atcoder. Edit: It is resolved. I did not look at the constraints properly :(.