chokudai's blog

By chokudai, history, 5 weeks 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

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Why no editorial for ABC 175 yet?!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope SecondThread uploads his screencast :( <3

»
5 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

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

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

    Atcoder people should start tagging SecondThead Videos in the editorials.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +9 Vote: I do not like it
      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    uwu

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

    Seriously I thought you are not going to take part in that beginner contest but thank you mate.

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

    Can you please point out the reason for the error in https://atcoder.jp/contests/abc176/submissions/16135523

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Questions are not opening

»
5 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

has anyone checked-out the E bomber problem. What are the targets ?

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

    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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Jesus the number of tests on Problem E. It is taking like 5 mins to test out a solution.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -22 Vote: I do not like it

    I found it interesting btw.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -6 Vote: I do not like it

      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.

»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
5 weeks 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.

»
5 weeks 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...

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

help me with D after the contest

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

    You can solve it with recursion

  • »
    »
    5 weeks 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

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

      0-1 bfs is very useful here!

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

      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?

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

        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.

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

          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.

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

    Use simple dijkastra

  • »
    »
    5 weeks 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).

    • »
      »
      »
      5 weeks 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?

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

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

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

          so a node can appear multiple time in queue? CMIIW

          • »
            »
            »
            »
            »
            »
            5 weeks 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.

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

      beautifully written code nmnsharma007

  • »
    »
    5 weeks 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

  • »
    »
    5 weeks 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

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    Dijkstra

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

    Search for 0-1 bfs.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ok solution of F plz

»
5 weeks 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

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

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

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

      it took me approx 25 minutes to write the code.

      • »
        »
        »
        »
        5 weeks 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.

  • »
    »
    5 weeks 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

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

Is F a dp problem?

  • »
    »
    5 weeks 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..)

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

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    DSU +BFS WAS One good option to solve it!

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

      hoW can you explain a bit??

      • »
        »
        »
        »
        5 weeks 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!

»
5 weeks 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.

  • »
    »
    5 weeks 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.

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

      Same logic , maps TLED my solution!

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

        Not for me

        I get Ac

        Link

      • »
        »
        »
        »
        5 weeks 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

        • »
          »
          »
          »
          »
          5 weeks 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!

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

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

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks 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

    • »
      »
      »
      5 weeks 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?

      • »
        »
        »
        »
        5 weeks 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

        • »
          »
          »
          »
          »
          5 weeks 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.

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

    edit- my solution is wrong tho it was AC

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

      What's the idea behind it? I did exactly same as Amir_Reza

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

        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.

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

      I did the same approach

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +14 Vote: I do not like it
      Countertest

      I really can't believe problemsetters made 130 tests and couldn't defeat this solution

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

        is the answer 4?

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

        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.

  • »
    »
    5 weeks 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)).

  • »
    »
    5 weeks 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)$$$.

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

    were you using unordered_map?

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

    I did this and got AC

    Code
  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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;
      }
      
»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E???

  • »
    »
    5 weeks 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

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

      Understood.Thanks a lot.

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

      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.

    • »
      »
      »
      5 weeks 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();
          }
      } 
      
      • »
        »
        »
        »
        5 weeks 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.

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

          Just one word(break) and it was AC !

          Btw thanx!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My D TLEd on just 1 test-case.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    You can store the nodes that has targets into set of pairs (set<pair<int,int>> 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

»
5 weeks 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

  • »
    »
    5 weeks 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

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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.

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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.

»
5 weeks 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?

»
5 weeks 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.

»
5 weeks 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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
5 weeks 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 ?

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

    https://atcoder.jp/users/ handle>/history

    but do wait atleast 10 contests for an actual rating

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

      How much time we should to wait until ratings updates , are there any system testing?

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

      What do you mean by actual rating? Is the rating shown currently in atcoder not true?

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Problem E is really nice and simple, liked it

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

    I also liked problem E and able to solve it in the contest but I can't able to solve D.

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

    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

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

    I liked the main idea. Real cool problem

»
5 weeks 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

»
5 weeks ago, # |
  Vote: I like it +82 Vote: I do not like it

how to solve F

  • »
    »
    5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +29 Vote: I do not like it
    Spoiler
»
5 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

are there any system tests in atcoder?

»
5 weeks 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?

  • »
    »
    5 weeks 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

»
5 weeks 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...**

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why am i getting TLE in python — https://atcoder.jp/contests/abc176/submissions/16154022

while the java solution passes? — https://atcoder.jp/contests/abc176/submissions/16120490

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

    same with c++

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

    check this out.. from collections import deque def good(x,y): if (x>=0 and x<h) and (y>=0 and y<w): return (mat[x][y] != "#") h, w = map(int,input().split()) sh, sw = map(int,input().split()) eh, ew = map(int,input().split()) mat = [] for _ in range(h): s = input() mat.append(s) x = [1,-1,0,0] y = [0,0,-1,1] dist = [[float('inf') for i in range(w)]for j in range(h)] sh -= 1 sw -= 1 eh -= 1 ew -= 1 dist[sh][sw] = 0 queue = deque() queue.appendleft((sh,sw)) while queue: m = queue.popleft() for d in range(4): nx = m[0] + x[d] ny = m[1] + y[d] if good(nx,ny): if dist[nx][ny] > dist[m[0]][m[1]]: dist[nx][ny] = dist[m[0]][m[1]] queue.appendleft((nx,ny)) for i in range(m[0]-2,m[0]+3): for j in range(m[1]-2,m[1]+3): if good(i,j): if dist[i][j] > dist[m[0]][m[1]] + 1: dist[i][j] = dist[m[0]][m[1]] + 1 queue.append((i,j)) if dist[eh][ew] == float('inf'): print(-1) else: print(dist[eh][ew])

»
5 weeks 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

»
5 weeks 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?

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

    Count pairs from given points

    Code
  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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$$$.

      • »
        »
        »
        »
        5 weeks 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$$$

        • »
          »
          »
          »
          »
          5 weeks 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

          • »
            »
            »
            »
            »
            »
            5 weeks 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

      • »
        »
        »
        »
        5 weeks 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.

        • »
          »
          »
          »
          »
          5 weeks 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.

  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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)

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

        Now I got it, I was missing the constraints.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks 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.

    • »
      »
      »
      5 weeks 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

      • »
        »
        »
        »
        5 weeks 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).

        • »
          »
          »
          »
          »
          5 weeks 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

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

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

          • »
            »
            »
            »
            »
            »
            5 weeks 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).

            • »
              »
              »
              »
              »
              »
              »
              5 weeks 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 (?)

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks 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).

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

    what dp are you talking about?

»
5 weeks 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)

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

    Can you explain the correct approach of F also?

    • »
      »
      »
      5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

WHY mifafaovo is not in top rated list?

  • »
    »
    5 weeks 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

»
5 weeks 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

»
5 weeks 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.

»
5 weeks 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.

»
5 weeks 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!

  • »
    »
    5 weeks 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

»
5 weeks 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

  • »
    »
    5 weeks 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

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

      Thank you for helping. Now I got where i did wrong in my code. Thank you again <3

»
5 weeks 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.

  • »
    »
    5 weeks 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

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

      I solved it using 0-1 BFS only but was looking for a flaw in that approach which I got now.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I had not understood the statement of problem C

»
5 weeks 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

  • »
    »
    5 weeks 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?

    • »
      »
      »
      5 weeks 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.

  • »
    »
    5 weeks 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!

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

can anyone please explain me the problem c?? I hadn't understood that...

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

    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]<A[i-1], if so, increase ans by their difference (A[i-1]-A[i]). Also, you need to update A[i] to A[i-1] to make the calculation correct.

    code
»
5 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Personal editorial for ABC176

  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my soln with problem D ?? Submission

»
5 weeks 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

»
5 weeks 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 :(.