chokudai's blog

By chokudai, history, 4 years ago, In English

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!

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Why no editorial for ABC 175 yet?!

»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

See you all on the scoreboard! (and on Youtube after contest)

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

    Atcoder people should start tagging SecondThead Videos in the editorials.

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

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

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

Please provide Editorials to learn new concepts.After the contests ended_

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Is it only me or the standing is loading forever. Nice problems by the way.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is AtCoder predictor broken today? Seems like the performance of everyone is 2400...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

help me with D after the contest

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 -1

    Link to the bad implemented code

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Use simple dijkastra

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

    I used 0-1 bfs to solve the problem. Pretty easy implementation (for me atleast).

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

      why we add to beginning of queue if it is reachable by current node without magic otherwise at last?

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

        Google 0-1 bfs. Its kinda the same concept as Dijkstra.

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

          so a node can appear multiple time in queue? CMIIW

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

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

      beautifully written code nmnsharma007

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

    lol i used something like two level bfs and it got pretty complicated

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

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

Please set problems such that it's possible to come back after going back-foot or at least possible to try.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve problem D please help??????????????????????????

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

    Dijkstra

    code
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      can u explain a bit please?

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

    Search for 0-1 bfs.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ok solution of F plz

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

    I had the same idea but couldn't implement it in time

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

      it took me approx 25 minutes to write the code.

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

        I saw SecondThread used 0-1BFS. Its a much cleaner solution in retrospect.

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

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

Is F a dp problem?

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

    I'm also wondering if it's dp or greedy (just can't solve it..)

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

      well, I read dreamoon's code. It's a dp problem...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can problem D solved by DP?????????

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

    DSU +BFS WAS One good option to solve it!

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

      hoW can you explain a bit??

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

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

how to solve E? I was trying something like O(nsqrtn) which was timing out.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it
    hint 1
    hint 2
    hint 3
    code

    And sorry for my poor English.

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

      Same logic , maps TLED my solution!

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        Not for me

        I get Ac

        Link

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I see your code

        it is $$$O(n ^ 2)$$$ and should get TLE

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

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

      Thank You for the great explanation. Made things up clear.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it -6 Vote: I do not like it

      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   Vote: I like it +10 Vote: I do not like it

        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 compilation

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

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

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

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

    edit- my solution is wrong tho it was AC

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

    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   Vote: I like it +8 Vote: I do not like it

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

    were you using unordered_map?

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

    I did this and got AC

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

    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, # ^ |
        Vote: I like it +10 Vote: I do not like it
      #include<bits/stdc++.h>
      #define ll long long
      #define fo(i,n) for(int i=0;i<n;i++)
      #define rfo(i,n) for(int i=n-1;i>=0;i--)
      #define Fo(i,q,n) for(int i=q;i<n;i++)
      #define rFo(i,q,n) for(int i=n-1;i>=q;i--)
      #define fO(i,n,k) for(int i=0;i<n;i+=k)
      #define FO(i,q,n,k) for(int i=q;i<n;i+=k)
      #define zero(a,n) memset(a,0,sizeof(a[0])*n)
      #define pb push_back
      #define mp make_pair
      #define F first
      #define S second
      #define endl "\n"
      #define Endl "\n"
      #define trace(x) cerr<<#x<<": "<<x<<" "<<endl;
      using namespace std;
      const int MOD=1000000007;
      void print(){cout <<endl;}
      template <typename T, typename... Types> 
      void print(T var1, Types... var2){cout << var1 << " " ;print(var2...) ;}
      //ceil of a/b
      template <typename T>
      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<int> rows(h,0);
      	vector<int> cols(w,0);
      	int x,y;
      	map< pair<int,int> ,int>dict;
      	fo(i,m){
      		cin>>x>>y;
      		x--;y--;
      		rows[x]+=1;
      		cols[y]+=1;
      		dict[mp(x,y)]=1;	
      	}
      	vector< pair<int,int> > rc;
      	fo(i,h){
      		rc.pb(mp(rows[i],i));	
      	}
      	vector< pair<int,int> > cc;
      	fo(i,w){
      		cc.pb(mp(cols[i],i));
      	}
      	sort(rc.rbegin(),rc.rend());
      	sort(cc.rbegin(),cc.rend());
      	vector< pair<int,int> > rcp;
      	vector< pair<int,int> > 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<<rmax+cmax-flag<<endl;
      	return 0;
      }
      
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E???

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

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

      Understood.Thanks a lot.

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

      I did the same thing I think, then why tle for 3 cases?

      #include<bits/stdc++.h>
      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<<t<<" ";
      #define pb                          push_back
      #define bhar(s,v)                   memset(s,v,sizeof(s))
      #define endl                        "\n"                       
      #define ce(x)                       cout<<x<<"\n";
      #define nl                          cout<<endl;
      #define jaldi                       ios_base::sync_with_stdio(false);cin.tie(NULL);
      #define dekh_lo                     ce("dekh_lo");
      #define sz(x)                       (ll)x.size()
      #define re                          return
      
      typedef pair<ll,ll> pii;
      typedef vector<pii> vii;
      typedef vector<ll> 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<pii,bool> hash;
      
          for(ll i=0;i<sz(cor);i++){
              row[cor[i].ff]++;
              col[cor[i].ss]++;
              hash[{cor[i].ff,cor[i].ss}]=1;
          }
      
          ll maxi1=-1e9;
          vi ind1;
          for(ll i=1;i<=h;i++){
              if(row[i]>maxi1){
                  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, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

My D TLEd on just 1 test-case.

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

    Sir I had to think, maybe I'm dumb

    Could you please help me? https://atcoder.jp/contests/abc176/submissions/16151561

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

      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.
      dijkastra
      All you have to do is doing the same thing you did, just applying dijkastra instead of dfs

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

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

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

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

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

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

      It's a lot of implementation anyway. They can give this kind of problems in unrated contests like educational dp contest.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

    That isn't the problem. h * w can be 1e10 and you can't have array with that size.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

Could someone please tell why my ans for D is failing?

https://atcoder.jp/contests/abc176/submissions/16151561

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

This is my first time participating in atcoder contest , and how can i see my rating change or rating changes later ?

»
4 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Problem E is really nice and simple, liked it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with my submission of Problem E? It shows Runtime Error https://atcoder.jp/contests/abc176/submissions/16150109

»
4 years ago, # |
  Vote: I like it +82 Vote: I do not like it

how to solve F

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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, # ^ |
      Vote: I like it +29 Vote: I do not like it
    Spoiler
»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

are there any system tests in atcoder?

»
4 years ago, # |
Rev. 2   Vote: I like it -6 Vote: I do not like it

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

    I solved D with 0-1 bfs. Or compress roads with DSU and BFS

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

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

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

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

    Count pairs from given points

    Code
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

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

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

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

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

        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]<size_r$$$ for any column, then we know that it is possible to avoid the $$$-1$$$.

        In the end though, the complexity turns out to be the same as brute forcing because of the pigeonhole principle.

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

    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

    Code
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

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

If anyone need short explanation & implementation for A-E Here

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

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

      3e5 as there can be at most 3e5 target , See the constraint m is min(h*w,3e5)

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Now I got it, I was missing the constraints.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why does simple (bfs || dfs) && dp get TLE on problem D ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    depends what you mean by simple. Most poeple's "simple" bfs or dfs didn't TLE.

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

      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   Vote: I like it +2 Vote: I do not like it

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

          people already posted tled submissions and mine is also same approach . here : https://pastebin.com/uKndTwVJ

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

            Its 0-1BFS using deque, you are running normal BFS.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            If you have a graph like this:

            8 13
            1 1
            1 13
            .#.#.#.#.#.#.
            .#.#.#.#.#.#.
            .#.#.#.#.#.#.
            .#.#.#.#.#.#.
            .#.#.#.#.#.#.
            .#.#.#.#.#.#.
            .#.#.#.#.#.#.
            .............
            

            with https://ideone.com/IfvPuG

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

              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   Vote: I like it +1 Vote: I do not like it

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

    what dp are you talking about?

»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

    Can you explain the correct approach of F also?

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

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

WHY mifafaovo is not in top rated list?

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

    As she haven't competed in last 6 months and old users are not included in ranklist at Codeforces

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

ABC175 A-E, ABC174 E, ABC174 C, ABC174 D,

I’m writing an unofficial editorial for ABC176 too. I’m going to post it tomorrow or the day after tomorrow.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, can someone please help me on D?

https://atcoder.jp/contests/abc176/submissions/16163382

I've tried basically all the ideas I had but still get WA on the max case.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

    $$$h$$$ and $$$w$$$ can be up to $$$3*10^5$$$ you cant declare array of that size. MLE + TLE

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

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/16166033

For any kind of help, thanks in advance

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

    Try this test :

    Test
    Picture

    bomb should be on green 'a'.
    sorry my drawing is not good.

    Your answer : 4

    Correct answer : 5

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Here's my solution for F that I got in contest but couldn't implement in time :P

Problem 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<j$$$. This means you've just considered exchanging with the group $$$label[j]$$$, and you currently have the cards at indices $$$i, j$$$ in your hand. $$$dp[i][j]$$$ stores the maximum points you could have at this state. You have two transitions:

Transition 1: You will swap with the next group. This means you will exchange at least one card in group $$$label[j]+1$$$. We can process all transitions of this form by examining all possible exchanges.

Transition 2: You move to the closest next group that shares a card that has a value equal to at least one of the cards in your hand. To see why this is the only other type of transition, note that if we don't exchange with the next group $$$label[j]+1$$$, we can assume we are planning to use the cards in our hand to get a point in the future. We go to the closest possible location where we could possible get a point (the next group that shares a value with at least one card in our hand), and we process exchanges there. Since we've removed all groups with all $$$3$$$ cards equal, if we don't plan on using a card in our hand to try to gain a point in the future, there's no reason we can't just swap it out in the next group, so this is the only other type of transitions. We can similarly process the transitions here as before.

Some care is needed to process the last group with only $$$1$$$ card, but it isn't that difficult.

Thus, the overall time complexity is $$$\mathcal O(N^2)$$$ since there are $$$\mathcal O(N^2)$$$ states and $$$\mathcal O(1)$$$ transition. There is a bit of a constant overhead from processing every possible swapping, but it runs in time still.

Here's my commented code, hopefully any confusion by my bad explanation is cleared up here: Submission

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

    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<j) can be tied to the group number k?

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

      Yes, we only need to consider $$$k = label[j]$$$, the group the card $$$j$$$ is in.

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

    Thanks a lot for taking out the time to write this detailed explanation!

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Personal editorial for ABC176

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

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

Can anyone please provide me DFS solution for ques D please...

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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