### chokudai's blog

By chokudai, history, 8 months 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! Comments (225)
 » Why no editorial for ABC 175 yet?!
•  » » I think this blog can compensate the editorial till it comes out.https://codeforces.com/blog/entry/81458
•  » » Yes,I am waiting for this__
•  » » Moreover, there is no english editorial for abc 174, which was three weeks ago
 » I hope SecondThread uploads his screencast :( <3
 » See you all on the scoreboard! (and on Youtube after contest)
•  » » Atcoder people should start tagging SecondThead Videos in the editorials.
•  » » » 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!
•  » » » » 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.
•  » » » » » 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.
•  » » uwu
•  » » Seriously I thought you are not going to take part in that beginner contest but thank you mate.
•  » » Can you please point out the reason for the error in https://atcoder.jp/contests/abc176/submissions/16135523
•  » » » Did you get a runtime error?
•  » » » » Yes
•  » » » » » Very likely because you were using too much space.
 » Questions are not opening
 » has anyone checked-out the E bomber problem. What are the targets ?
•  » » Position of M targets are given in M lines the first integer is X coordinate and second int is Y coordinate. Be careful though as it uses 1 based indexing
 » Jesus the number of tests on Problem E. It is taking like 5 mins to test out a solution.
•  » » I found it interesting btw.
•  » » » Yeah no doubt that the problem is very fun! But it is not fun to wait for 5 mins just to see a TLE or RE. That is why multitests are important.
 » Please provide Editorials to learn new concepts.After the contests ended_
 » Is it only me or the standing is loading forever. Nice problems by the way.
 » Is AtCoder predictor broken today? Seems like the performance of everyone is 2400...
•  » » Can you give the link to download ?
•  » » »
 » help me with D after the contest
•  » » You can solve it with recursion
•  » » » https://atcoder.jp/contests/abc176/submissions/16137218My recursive solution with TLE
•  » » » Why is this dp solution for D giving WA https://atcoder.jp/contests/abc176/submissions/16169002 Pls help.
•  » » 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
•  » » » 0-1 bfs is very useful here!
•  » » » » actually I don't know 0-1 bfs. thanks for the info. I will learn it.
•  » » » » » This is my code for problem D : https://atcoder.jp/contests/abc176/submissions/16119228
•  » » » » » » What's the use of if(dp[i][j]!=val) continue; I cannot see if anytime this condition will be true.
•  » » » » » » » Maybe it is useless...
•  » » » » » » » » That's what i think too. They have even used that in emaxx..
•  » » » » what is 0/1 bfs ??
•  » » » » »
•  » » » 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?
•  » » » » 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.
•  » » » » » okay thanks I got it, I thought they meant using the magic trick magician will turn all cells of 5*5 square being at the center into roads which is wrong. What they meant is he can go at any road place which is in 5*5 square using a magic trick. Thank you.
•  » » Use simple dijkastra
•  » » I used 0-1 bfs to solve the problem. Pretty easy implementation (for me atleast).
•  » » » 8 months ago, # ^ | ← Rev. 2 →   why we add to beginning of queue if it is reachable by current node without magic otherwise at last?
•  » » » » Google 0-1 bfs. Its kinda the same concept as Dijkstra.
•  » » » » » so a node can appear multiple time in queue? CMIIW
•  » » » » » » 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.
•  » » » beautifully written code nmnsharma007
•  » » lol i used something like two level bfs and it got pretty complicated
•  » » 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
 » Please set problems such that it's possible to come back after going back-foot or at least possible to try.
 » how to solve problem D please help??????????????????????????
•  » » 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={-2,-1,0,+1,+2},dy={-2,-1,0,+1,+2}; int n,m,r1,c1,r2,c2,dp; string s; 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 #"<
•  » » » can u explain a bit please?
•  » » Search for 0-1 bfs.
 » ok solution of F plz
 » 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
•  » » I had the same idea but couldn't implement it in time
•  » » » 8 months ago, # ^ | ← Rev. 2 →   it took me approx 25 minutes to write the code.
•  » » » » I saw SecondThread used 0-1BFS. Its a much cleaner solution in retrospect.
•  » » 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
 » Is F a dp problem?
•  » » I'm also wondering if it's dp or greedy (just can't solve it..)
•  » » » well, I read dreamoon's code. It's a dp problem...
 » can problem D solved by DP?????????
•  » » DSU +BFS WAS One good option to solve it!
•  » » » 8 months ago, # ^ | ← Rev. 2 →   hoW can you explain a bit??
•  » » » » 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!
 » how to solve E? I was trying something like O(nsqrtn) which was timing out.
•  » » 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.
•  » » » Same logic , maps TLED my solution!
•  » » » » Not for meI get AcLink
•  » » » » I see your codeit is $O(n ^ 2)$ and should get TLE
•  » » » » » 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!
•  » » » Thank You for the great explanation. Made things up clear.
• »
»
»
8 months ago, # ^ |
Rev. 2

# 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

•  » » » » 8 months ago, # ^ | ← Rev. 2 →   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
•  » » » 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?
•  » » » » 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
•  » » » » » 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.
•  » » » » » » Exactly! Glad that you understand this bit. Cheers
•  » » 8 months ago, # ^ | ← Rev. 2 →   edit- my solution is wrong tho it was AC
•  » » » What's the idea behind it? I did exactly same as Amir_Reza
•  » » » » 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.
•  » » » I did the same approach
•  » » » 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
•  » » » » is the answer 4?
•  » » » » » Yes
•  » » » » Yeah, when I was implementing the code for E, I had a case like this in the back of my mind (A case with multiple maximums, where a later maximum is optimal) but I submitted my code anyway and it passed ! I thought that If i implemented that version it would take too much time but I hadn't noticed the 3 second time limit.
•  » » 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)).
•  » » 8 months ago, # ^ | ← Rev. 4 →   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)$.
•  » » were you using unordered_map?
•  » » 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() 
•  » » 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
•  » » » #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.F; int cmax = cc.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<
 » How to solve E???
•  » » 8 months ago, # ^ | ← Rev. 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
•  » » » Understood.Thanks a lot.
•  » » » could u plz tell that i am wrong or not that i think ur soln will be o(h*w) in worst case ..?plz clear it.
•  » » » 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(); } } 
•  » » » » 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.
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   Just one word(break) and it was AC !Btw thanx!
 » My D TLEd on just 1 test-case.
•  » » Simple bfs like this won't work. You have to use dijkastra
•  » » » 0-1 bfs passed easily.
•  » » » » What is 0-1 BFS?
•  » » » » » I learned it from this blogSolved problem D using it too.
 » I got TLE in 9/130 TCs in Problem E. Anyway to optimise this? Finding whether the node has a target or not is taking a lot of time for some test cases I think. https://atcoder.jp/contests/abc176/submissions/16148903
•  » » You can store the nodes that has targets into set of pairs (set> s). Now for each node in that set, you can check if it can be produce the answer, if it does then subtract 1 from the no.of answer producing nodes. After iterating through whole set, if the answer producing nodes become 0 that means we should print (maxx_row + maxx_col — 1), else print (maxx_row + maxx_col)I can explain more clearer if you need
 » Give problems where you need to at least think. Not put D where you need to just write a dijkastra without even thinking
•  » » Sir I had to think, maybe I'm dumbCould you please help me? https://atcoder.jp/contests/abc176/submissions/16151561
•  » » » 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
•  » » » » 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.
•  » » » » » 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.
•  » » 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.
•  » » » 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.
•  » » 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.
•  » » » It's a lot of implementation anyway. They can give this kind of problems in unrated contests like educational dp contest.
 » 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?
•  » » Can you give a link to your submission?
•  » » »
•  » » » » It's just a warning and you should be fine! https://stackoverflow.com/questions/7271939/warning-ignoring-return-value-of-scanf-declared-with-attribute-warn-unused-r Check the above link for more information!
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   Yes I checked that page already and tried to get rid of that. Since it is just a warning, I think the actual error is coming from some other line. Still cant figure it out :(
•  » » That isn't the problem. h * w can be 1e10 and you can't have array with that size.
 » 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.
 » Could someone please tell why my ans for D is failing?https://atcoder.jp/contests/abc176/submissions/16151561
 » How to solve D?
•  » » Clean solution using Dijkstra
 » This is my first time participating in atcoder contest , and how can i see my rating change or rating changes later ?
•  » » https://atcoder.jp/users/ handle>/historybut do wait atleast 10 contests for an actual rating
•  » » » How much time we should to wait until ratings updates , are there any system testing?
•  » » » What do you mean by actual rating? Is the rating shown currently in atcoder not true?
 » Problem E is really nice and simple, liked it
•  » » I also liked problem E and able to solve it in the contest but I can't able to solve D.
•  » » True, i took 40 min, finally solved. I want to know if there is a space optimized solution though, coz i used 2 unordered sets, 2 unordered maps, 1 ordered set
•  » » I liked the main idea. Real cool problem
 » Can anyone help me with my submission of Problem E? It shows Runtime Error https://atcoder.jp/contests/abc176/submissions/16150109
•  » » You cannot make a matrix of size h*w, as h and w can both be equal to 3*10^5
•  » » » oh i missed it what is the approach then?
•  » » » »
•  » » » https://atcoder.jp/contests/abc176/submissions/16135523 Can you please suggest me also why I get RE?
•  » » » » bro ,the size of the matrix you created is very large of the order 10^10
•  » » » » » 8 months ago, # ^ | ← Rev. 2 →   Oh, So how can I tackle it? And also what is the max size of array possible?
•  » » » » » » size of Array <= 10^7 also you can follow this for solving problem E.
•  » » » » » » check this out https://atcoder.jp/contests/abc176/submissions/16156313
 » how to solve F
•  » » 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.
•  » » 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
•  » » » What $dp(card1, card2)$ means?
 » are there any system tests in atcoder?
•  » » No
 » 8 months ago, # | ← Rev. 2 →   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?
•  » » I solved D with 0-1 bfs. Or compress roads with DSU and BFS
 » **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...** •  » » 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.
 » Can someone tell me why am i getting TLE in python — https://atcoder.jp/contests/abc176/submissions/16154022while the java solution passes? — https://atcoder.jp/contests/abc176/submissions/16120490
•  » » same with c++
•  » » check this out.. from collections import deque def good(x,y): if (x>=0 and x=0 and y dist[m][m]: dist[nx][ny] = dist[m][m] queue.appendleft((nx,ny)) for i in range(m-2,m+3): for j in range(m-2,m+3): if good(i,j): if dist[i][j] > dist[m][m] + 1: dist[i][j] = dist[m][m] + 1 queue.append((i,j)) if dist[eh][ew] == float('inf'): print(-1) else: print(dist[eh][ew])
 » can anybody please help me out to find error in my solution of problem E https://atcoder.jp/contests/abc176/submissions/16135136
•  » » There could be different indices for which values is maximize.
•  » » » thanks bro it really works
 » 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?
•  » » 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; } 
•  » » 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.
•  » » » 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$.
•  » » » » No, think of $(1, 1)$, $(2, 2)$, $(3, 3)$. Here, $m = 3$, $rowsize = 3$, $colsize = 3$, $rowmax = 1$, $colmax = 1$, $ans = 1$
•  » » » » » 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
•  » » » » » » 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
•  » » » » 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] •  » » » » » 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. •  » » 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()  •  » » 8 months ago, # ^ | ← Rev. 2 → 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.  » If anyone need short explanation & implementation for A-E Here •  » » 8 months ago, # ^ | ← Rev. 2 → 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. •  » » » 3e5 as there can be at most 3e5 target , See the constraint m is min(h*w,3e5) •  » » » » Now I got it, I was missing the constraints.  » why does simple (bfs || dfs) && dp get TLE on problem D ? •  » » depends what you mean by simple. Most poeple's "simple" bfs or dfs didn't TLE. •  » » » 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 •  » » » » 8 months ago, # ^ | ← Rev. 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). •  » » » » » people already posted tled submissions and mine is also same approach . here : https://pastebin.com/uKndTwVJ •  » » » » » » Its 0-1BFS using deque, you are running normal BFS. •  » » » » » » 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). •  » » » » » » » 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 (?) •  » » » » » » » » 8 months ago, # ^ | ← Rev. 4 → 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). •  » » what dp are you talking about? •  » » » you can check this : https://pastebin.com/uKndTwVJ  » 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) •  » » Can you explain the correct approach of F also? •  » » » Sorry, I don't know how to do it :(I got a few ideas but none of them worked out in a passable complexity.  » WHY mifafaovo is not in top rated list? •  » » As she haven't competed in last 6 months and old users are not included in ranklist at Codeforces  » 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 •  » » Google Translate works fine for me, Try again  » I’m writing an unofficial editorial for ABC176 too. I’m going to post it tomorrow or the day after tomorrow. •  » » dont do that •  » » » Since I can read Japanese, I will do. If you don't want to read it, just ignore me. •  » »  » 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.  » 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! •  » »$h$and$w$can be up to$3*10^5$you cant declare array of that size. MLE + TLE  » 8 months ago, # | ← Rev. 2 → 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 •  » » 8 months ago, # ^ | ← Rev. 2 → Try this test : Test7 4 8 1 1 1 2 2 4 3 1 4 3 4 4 6 2 7 1 Picture bomb should be on green 'a'. sorry my drawing is not good.Your answer : 4Correct answer : 5 •  » » » Thank you for helping. Now I got where i did wrong in my code. Thank you again <3  » 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. •  » » 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 •  » » » I solved it using 0-1 BFS only but was looking for a flaw in that approach which I got now.  » I had not understood the statement of problem C  » 8 months ago, # | ← Rev. 2 → 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
•  » » 8 months ago, # ^ | ← Rev. 2 →   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
•  » » » Yes, we only need to consider $k = label[j]$, the group the card $j$ is in.
•  » » Thanks a lot for taking out the time to write this detailed explanation!
 » 8 months ago, # | ← Rev. 2 →   can anyone please explain me the problem c?? I hadn't understood that...
•  » » The height of i-th person must be taller or same as the one standing in front of him. For example, in the first test case — 2 1 5 4 3, you can see that the first person has height 2 while the second one has height 1. Hence the condition is not true and the second person needs a stool to increase his height to 2. In other word, the second person needs a stool of height 1 (2-1). You can check the height of each person, starting the second one, and that of the previous one to see if A[i]
 » 8 months ago, # | ← Rev. 2 →   Personal editorial for ABC176
•  » » 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.
•  » » » I use vuepress.
 » Can anyone please provide me DFS solution for ques D please...
 » What's wrong with my soln with problem D ?? Submission
 » can anyone tell me what is wrong with my code for problem D? code Link : https://atcoder.jp/contests/abc176/submissions/16215981
•  » » It's only problem in 4 test case..
 » 8 months ago, # | ← Rev. 2 →   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]=count; } for(int j=1;j<=w;j++){ int count=0; for(int i=1;i<=h;i++){ count+=a[i][j]; } a[j]=count; } int ans=0; for(int i=1;i<=h;i++){ for(int j=1;j<=w;j++){ int curr=a[j]+a[i]; 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 :(.
 » Do you know why my code gets TLE in problem D ?https://www.ideone.com/1LKnsI