We will hold AtCoder Beginner Contest 176.

- Contest URL: https://atcoder.jp/contests/abc176
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200822T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: kort0n, kyopro_friends, YoshikaMiyafuji
- Rated range: ~ 1999

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

We are looking forward to your participation!

Why no editorial for ABC 175 yet?!

I think this blog can compensate the editorial till it comes out.

https://codeforces.com/blog/entry/81458

Yes,I am waiting for this__

Moreover, there is no english editorial for abc 174, which was three weeks ago

I hope SecondThread uploads his screencast :( <3

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

Atcoder people should start tagging SecondThead Videos in the editorials.

No editorial for me for problem F this time, but solutions to A-E and my commentary are available here for people who are interested!

Could you elaborate on what your time complexity for the E question is(in the average case)? At first, I thought it would be O(R*C), but then I realized that it could not be so, because, in case of massive R, C, we restrict K such to be less than equal to 2e5, so that situation gets taken care of, then I thought it would be something along the lines of O(M), but then I thought that, in case of small R and C, we can make all the cells as target cells, and then your program will go through all combinations(R*C) to find the answer.

Worst case it is O(number of points). The for loop that looks n^2 only runs as long as there is a point at ever intersection it has checked. Once it has run n+1 times, it will find some intersection that doesn’t have a point in it, and break out.

uwu

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

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

Did you get a runtime error?

Yes

Very likely because you were using too much space.

Questions are not opening

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

Position of M targets are given in M lines the first integer is X coordinate and second int is Y coordinate. Be careful though as it uses 1 based indexing

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

I found it interesting btw.

Yeah no doubt that the problem is very fun! But it is not fun to wait for 5 mins just to see a TLE or RE. That is why multitests are important.

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

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

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

Can you give the link to download ?

https://ac-predictor.com/

help me with D after the contest

You can solve it with recursion

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

My recursive solution with TLE

Why is this dp solution for D giving WA https://atcoder.jp/contests/abc176/submissions/16169002 Pls help.

First, give all connected components a number then put an edge between two connected components i and j if you can go from i to j using magic.

In which magician initial is standing call that connected component source and the connected component in which ending point is call it destination component.

Do bfs from source components and find a depth of other components. if you can reach the destination component then answer is the depth of destination component and if we can't reach the destination component then answer is -1

Link to the bad implemented code

0-1 bfs is very useful here!

actually I don't know 0-1 bfs. thanks for the info. I will learn it.

This is my code for problem D : https://atcoder.jp/contests/abc176/submissions/16119228

What's the use of

`if(dp[i][j]!=val) continue;`

I cannot see if anytime this condition will be true.Maybe it is useless...

That's what i think too. They have even used that in emaxx..

what is 0/1 bfs ??

https://cp-algorithms.com/graph/01_bfs.html

Can you please help me understanding the 2nd test case of D problem, I mean why the magician can't go at (3,1) using his 1 magic spell and then move downward at (4,1)? Or It is compulsory to use move-A first and then move-B?

There is wall on (3,1). So you can't go there. Read the problem statement again. You can only walk on the road.

It is not compulsory to use move A first and then move B. You can use any move first.

okay thanks I got it, I thought they meant using the magic trick magician will turn all cells of 5*5 square being at the center into roads which is wrong. What they meant is he can go at any road place which is in 5*5 square using a magic trick. Thank you.

Use simple dijkastra

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

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

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

so a node can appear multiple time in queue? CMIIW

Yes I think it can and will.If the node was already in the queue and we just found a better distance towards it just like Dijkstra, If the edge reaching towards it was 0 weighted, it goes in the front else it goes in the back.We always process first the nodes which have 0-weighted edges reaching to them. When they are exhausted, we start using the 1-weighted edges.I hope I am not wrong.

beautifully written code nmnsharma007

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

I did a very badly written bfs. Even I was surprised when it came AC. Idea was to use an extra waiting queue for storing all possible cells by using magic. If you don't add any cell twice in your bfs queue you should be in time limits. If bfs queue is empty I check for waiting queue elements in case they can be used. Even I am confused why it works. I am looking for some elegant solution. code

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

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

Dijkstra

code...#include <bits/stdc++.h>

can u explain a bit please?

Search for 0-1 bfs.

ok solution of F plz

For D, first separate all the different regions using DFS.

Then construct a graph between different regions using the trick that the magician can use.

Finally ,find the shortest distance between the region of initial point and the region of final point using

simple bfs (by maintaining a 'level' array).

Here's my submission:

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

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

it took me approx 25 minutes to write the code.

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

I had the quite similiar idea, I just wanted to give similiar integer to connected components and then increase the integer for next connected component, and just return the difference of values of source and destination cells. the only problem was unreachability for this I again needed to iterate and do heck of implementation. So I rather choose to leave this problem.XD

Is F a dp problem?

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

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

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

DSU +BFS WAS One good option to solve it!

hoW can you explain a bit??

See connect all possible .s which can be connected as one component! then we have some partitions in whole matrix!. Now the cost of moving from one partition to other is to be determined , if the source and the destination dont belong to same group or cluster which we made using DSU. Put first partition in bfs queue. means the partition of the source! and from each node in this partition ,connect all other partitions that can be connected. the thing you will get is now a graph.In this graph do bfs from the source partition to the destination partition using Single Source Shortest Path Bfs!

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

hint 1answer is

`maximum number of bombs in a row`

+`maximum number of bombs in a column`

or

`maximum number of bombs in a row`

+`maximum number of bombs in a column`

— 1hint 2You should choose a point with row has

`maximum number of bombs in a row`

and col`maximum number of bombs in a column`

because :

In this way you get atleast

`maximum number of bombs in a row`

+`maximum number of bombs in a column`

— 1otherwise you will get atmost

`maximum number of bombs in a row`

+`maximum number of bombs in a column`

— 1create two vectors with :

1. rows with maximum number of bombs

2. cols with maximum number of bombs

hint 3if

`size of first vector`

*`size of second vector`

> 300000then output

`maximum number of bombs in a row`

+`maximum number of bombs in a column`

otherwise :

bruteforce on every row with maximum number of bombs and every col with maximum number of bombs

`hint in hint`

: Use a map to know you have a bomb in one cell or notcodeAnd sorry for my poor English.

Same logic , maps TLED my solution!

Not for me

I get Ac

Link

I see your code

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

Ya I just saw the problem wrong ! and brute forced , but now I got AC using sets instead of matrices , concept is yet same but!, nice proof is that we will iterate in the nested loop at max 3e5 times due to pigeonhole principle. This principle I saw just now!,good problem a very good problem , nice proof involved!

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

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

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

if size of first vector * size of second vector > 300000then output maximum number of bombs in a row + maximum number of bombs in a column.if size <300000 then how can we be sure that ans is maximum number of bombs in a row + maximum number of bombs?if size < 300000 then of course you can iterate through all the combinations of row and column in the first vector and second vector...then find out if the pair from the combination, for example (r, c), exists in the input. If so, then ans = max num of bombs in a row + max num of bombs in a column — 1

Ops typo I wanted to ask if size>300000.But I got my ans as there is atmost 300000 bombs so if size>300000 then we can be sure that there must be at least one maxrow and maxcol without intersecting bomb.

Exactly! Glad that you understand this bit. Cheers

edit- my solution is wrong tho it was AC

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

The idea is that we are trying to fix one row and then choosing the column which have maximum number of bombs and vice versa for column.

I did the same approach

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

is the answer 4?

Yes

Yeah, when I was implementing the code for E, I had a case like this in the back of my mind (A case with multiple maximums, where a later maximum is optimal) but I submitted my code anyway and it passed ! I thought that If i implemented that version it would take too much time but I hadn't noticed the 3 second time limit.

My solution is choosing the coordinate x,y that could maximize the target.

The answer is the number of targets that x hit + the number of targets that y hit — (there is a target at coordinate (x,y)).

Let $$$r[i]$$$ be the number of targets in row $$$i$$$, and $$$c[j]$$$ be the number of targets in columns $$$j$$$. Then the answer is $$$\max(r) + \max(c)$$$ unless for every pair $$$i, j$$$ such that $$$r[i] == \max(r)$$$ and $$$c[j] == \max(c)$$$, we have a target at $$$(i, j)$$$ (if the intersection of a pair doesn't have a target, we can simply choose that pair). Otherwise, the answer is $$$\max(r)+\max(c)-1$$$ (no matter what, we overcount the target at the intersection).

This is equivalent to the following: If $$$x$$$ is the number of rows $$$i$$$ with $$$r[i] == \max(r)$$$, $$$y$$$ is the number of columns $$$j$$$ with $$$c[j] == \max(c)$$$, and $$$z$$$ is the number of targets with coordinates $$$(i, j)$$$ satisfying $$$i == \max(r)$$$ and $$$j == \max(c)$$$, then the answer is $$$\max(r)+\max(c)-(x*y == z)$$$.

were you using unordered_map?

I did this and got AC

CodeMy 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

How to solve E???

The final answer would be either be the

maxRowsum + maxColSumormaxRowsum + maxColSum -1(where maxRowSum means maximum number of targets in a row considering all rows and maxColSum means maximum number of targets in a column considering all columns).We need to find all rows having number of targets equal to maxRowSum and all columns having number of targets equal to maxColSum and then check for each one of them whether there exists a combination of them where the common element isn't a target.If such combination exists then answer would be maxRowsum + maxColSum otherwise maxRowsum + maxColSum -1.We could use map to check whether a co-ordinate is a target or not.

My submission:-E — Bomber

Understood.Thanks a lot.

could u plz tell that i am wrong or not that i think ur soln will be o(h*w) in worst case ..?plz clear it.

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

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.

Just one word(break) and it was AC !

Btw thanx!

My D TLEd on just 1 test-case.

Simple bfs like this won't work. You have to use dijkastra

0-1 bfs passed easily.

What is 0-1 BFS?

I learned it from this blog

Solved problem D using it too.

I got TLE in 9/130 TCs in Problem E. Anyway to optimise this? Finding whether the node has a target or not is taking a lot of time for some test cases I think. https://atcoder.jp/contests/abc176/submissions/16148903

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

Give problems where you need to at least think. Not put D where you need to just write a dijkastra without even thinking

Sir I had to think, maybe I'm dumb

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

Your solution isn't handling updates. Like let's say you can go to node $$$x$$$ from node $$$y$$$ in $$$3$$$ sec but from node $$$z$$$ to node $$$y$$$ in $$$2$$$ sec. And you processed node $$$x$$$ before node $$$z$$$. Then, you are not updating with $$$z$$$ and that produces WA.

To handle updates efficiently, we use dijkastra algorithm.

dijkastra

All you have to do is doing the same thing you did, just applying dijkastra instead of dfs

But sir at every node "n", I'm storing the minimum magic needed to reach (dh, dw) from n.

So I won't matter right, in how many magic I reached n.

Hope i didn't misinterpreted what you said. If you could give a testcase that'll be helpful.

I don't have testcase anyway, but I think this is why it's incorrect. You obviously updated $$$dp[y] = 3$$$ via $$$x$$$ then you went to $$$z$$$ after some operations. Now, since $$$dp[y] != INF$$$ then, you are not updating according to your code if I understood your code correctly.

That's why it is called beginner contest.

I couldn't able to solve D because I don't know dijkastra, but now I got some insight of this algorithm due to this problem.

It's better to give a dijkastra problem with little insight in E instead. They can give same difficulty level binary search or greedy problem where you need to think before applying binary search. Even div3 problems consider having some insights. Otherwise, it's like saying, implement dijkastra algorithm.

And yeah, you could have still learnt dijkastra if they put a problem on this algo with a little insight.

I solved with bfs only think of each connected without magic roads as a single cluster, using DSU and then applying bfs over the connected components. This took me around 1 hour for me to think of and implement heavily ,but I think that it wasnt required as ya Dijskarts is applicable.

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

warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]

I am getting this error on question E: Bomber. Can anyone help me out?

Can you give a link to your submission?

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

It's just a warning and you should be fine! https://stackoverflow.com/questions/7271939/warning-ignoring-return-value-of-scanf-declared-with-attribute-warn-unused-r Check the above link for more information!

Yes I checked that page already and tried to get rid of that. Since it is just a warning, I think the actual error is coming from some other line. Still cant figure it out :(

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

Why editorials is not posted in atcoder now-a-days?? I am waiting for previous ABC-175 contest for 8 days but still there is no editorial.

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

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

How to solve D?

Clean solution using Dijkstra

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

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

but do wait atleast 10 contests for an actual rating

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

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

Problem E is really nice and simple, liked it

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

True, i took 40 min, finally solved. I want to know if there is a space optimized solution though, coz i used 2 unordered sets, 2 unordered maps, 1 ordered set

I liked the main idea. Real cool problem

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

You cannot make a matrix of size h*w, as h and w can both be equal to 3*10^5

oh i missed it what is the approach then?

Refer this : https://codeforces.com/blog/entry/81776?#comment-684899

https://atcoder.jp/contests/abc176/submissions/16135523 Can you please suggest me also why I get RE?

bro ,the size of the matrix you created is very large of the order 10^10

Oh, So how can I tackle it? And also what is the max size of array possible?

size of Array <= 10^7also you can follow this for solving problem E.check this out https://atcoder.jp/contests/abc176/submissions/16156313

how to solve F

At first, I was trying to solve in anyway. After every move we will have two items left. We can do a $$$dp[i][left_1][left_2]$$$ where we do the operation on items $$$left_1$$$, $$$left_2$$$, $$$i$$$, $$$i+1$$$, $$$i+2$$$. This way we can solve in $$$O(n^3)$$$ which is too large. But I started thinking about these pairs $$$(left_1, left_2)$$$ because we can iterate over them.

So I tried to somehow store all pairs $$$(j, k)$$$ for $$$j, k \lt i$$$ and update the answers using items $$$i$$$, $$$i+1$$$, $$$i+2$$$, as well as insert new pairs.

To solve all transitions we just need these 5 functions. I will call color as the number written on a card.

All of them can be implemented in O(1). Let me know if this is enough.

SpoilerWe process the cards in groups of three — we hold two cards, pick the next three cards, then decide which two we want to keep. We can solve it in $$$O(N^3)$$$ using DP with states $$$dp(position, card1, card2)$$$, and optimize it to $$$O(N^2)$$$ with states $$$dp(card1, card2)$$$ with the additional constraint that either the first or second card must be at the last group of three we processed.

From the current state, we can either transition to the next immediate group of three, or find the next occurrence of the first (or second) card type and transition to that group of three, ignoring the groups in between. The intuition behind the second transition is that we decided to keep the first (or second) card type for future points, so we can ignore all groups not containing it.

My submission: https://atcoder.jp/contests/abc176/submissions/16141029

What $$$dp(card1, card2)$$$ means?

are there any system tests in atcoder?

No

For D, I treated each connected component as a node of a graph and then used bfs to find the shortest path.Lengthy implementation. Is this the intended solution or is there a easier way to do this?

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

It's better to print your debug statements in standard error stream. That may increase the runtime to a certain extent(if you print a lot of lines), however it is highly likely that it gets AC.

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

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

same with c++

check this out..

`from collections import deque def good(x,y): if (x>=0 and x<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])`

can anybody please help me out to find error in my solution of problem E https://atcoder.jp/contests/abc176/submissions/16135136

There could be different indices for which values is maximize.

thanks bro it really works

For problem E, I get we have to find the row and column with maximum number of targets, and the answer is at least (sum of targets in the selected row and column)-1.

But the maximum possible answer could be sum of targets in selected row and column, in case there is no target at the intersection of the chosen row and column.

Since AtCoder has apparently stopped releasing English editorials, could anyone explain how to find this maximal answer?

Count pairs from given points

CodeStore the rows with maximum bombs, same for columns. What I did is $$$rowsize * colsize > m$$$ then, $$$ans = rowmax + colmax - 1$$$, else, we can iterate over rows and cols and check the possible outcome.

Thanks, this is what I wasn't able to think of, I was thinking there would be some clever way without brute-force.

PS. I think you made a small typo, the condition should be: $$$rowsize∗colsize>m$$$ then, $$$ans=rowmax+colmax$$$.

No, think of $$$(1, 1)$$$, $$$(2, 2)$$$, $$$(3, 3)$$$. Here, $$$m = 3$$$, $$$rowsize = 3$$$, $$$colsize = 3$$$, $$$rowmax = 1$$$, $$$colmax = 1$$$, $$$ans = 1$$$

Place the bomb in (1,3) or (3,1) — ans is 2 (= rowmax + colmax).

The condition makes sense because corresponding to $$$rowmax$$$ rows and $$$colmax$$$ columns, there are $$$rowmax * colmax$$$ points of intersections of the rows and columns. If $$$rowmax * colmax > m$$$, then at least one of these intersections doesn't have a target, and then you can actually have $$$rowmax + colmax$$$ targets destroyed.

And I also got AC using this condition (line 28): https://atcoder.jp/contests/abc176/submissions/16158977

Ohh, I said $$$rowsize$$$ and $$$colsize$$$, my approach is somewhat different than yours.

Looks like I am not being able to get my words. Here is my one.

This

There is a solution that doesn't require iterating over all possible combinations of

best rowsandbest 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.

That is the same thing as brute-force.

Hello sir, I did it using the following steps: 1. Find the maximum number of the target present in any row 2. Find the maximum number of the target present in any column 3. I iterated over the columns and see how much score we can get if we choose the row which we get from step 1 and given column, but if we get any target at the intersection point of these two we need to subtract one from the score and find the maximum score in all the chosen columns with the row from step 1 4. I iterated over the rows and see how much score we can get if we choose the column which we get from step 2 and given row, but if we get any target at the intersection point of these two we need to subtract one from the score and find the maximum score in all the chosen rows with the column from step 2

CodeCheck for every row and column indices for which it gives maximum values, there will not be more than 3 X 10 ^ 5 such pairs.

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

In problem E, What if all the cells in the given matrix contain targets ? How many pairs of row and columns will be there containing maximum number of targets.

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

Now I got it, I was missing the constraints.

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

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

that's why i'm confused , i implemented same approach as SecondThread in C++ with queue but it got TLE . but with Set it doesn't

I see in my crystal ball that your line 136 is not optimized. Correct it.

If you want more details, be smarter, paste your code on some pastebin or something, so we can analyze it -_-

Big chances that you fucked up at your "already visited structure" (when you check or you update this, maybe you're not doing it at the best time, so you have a lot of duplicated nodes with the same distance and coordinates in your queue).

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

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

If you have a graph like this:

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).

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 (?)

They aren't doing the same :

when no teleportations

when teleportations.

I let you find by yourself why is it better.

Hint: try to proove by induction that the resulting deque will always treat nodes by increasing distances (the proof only works because it's a "0-1 BFS" as said previously).

what dp are you talking about?

you can check this : https://pastebin.com/uKndTwVJ

Screencast of getting a thousand wrong ideas for F, rambling about Dial's algorithm, and somehow beating my last performance with 1/4 the effort (+ (possibly overly elaborate) editorial for A-E)

Can you explain the correct approach of F also?

Sorry, I don't know how to do it :(

I got a few ideas but none of them worked out in a passable complexity.

WHY mifafaovo is not in top rated list?

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

Probably not helpful even with google translate, but the person who got first AC for F wrote an editorial for the round in japanese: https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2020-08-22abc-176

Google Translate works fine for me, Try again

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.

dont do that

Since I can read Japanese, I will do. If you don't want to read it, just ignore me.

ABC176-E

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.

What's wrong in this code: https://atcoder.jp/contests/abc176/submissions/16165157 All i did was get the number of targets in each row and each column in two separate maps and if we see the sq with bomb the destroyed are 1 less than the sum of the two maps for the given key else it would be the sum. Thank you for helping!

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

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

Try this test :

Test7 4 8

1 1

1 2

2 4

3 1

4 3

4 4

6 2

7 1

Picturebomb should be on green 'a'.

sorry my drawing is not good.

Your answer : 4

Correct answer : 5

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

What's wrong with this method for D? I first do a BFS from starting point and mark all the reachable nodes as visited and it would take 0 moves to move to any of them. Then I do a BFS from ending point and find distance to all the reachable nodes. Now, I do a brute force over all reachable nodes from starting point, and the number of moves required to reach that point would be 0 as we go there from starting point without using any move B and then to reach end point from that node, I find distance of ending point from this node which would be same as distance of this node from ending point, and then take minimum over all possible answers.

I think the normal BFS approach will not work in this situation. You should either use BFS 0-1 or Dijkstra algorithm.

For me, I use the Dijkstra algorithm to solve it. You can see it in here.

An useful link to learn about BFS 0-1: here

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

I had not understood the statement of problem C

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

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?

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

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

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

The height of i-th person must be taller or same as the one standing in front of him. For example, in the first test case — 2 1 5 4 3, you can see that the first person has height 2 while the second one has height 1. Hence the condition is not true and the second person needs a stool to increase his height to 2. In other word, the second person needs a stool of height 1 (2-1).

You can check the height of each person, starting the second one, and that of the previous one to see if A[i]<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.

codePersonal editorial for ABC176

Looks quite good. How did you make the blog. Its look and feel is good. Which framework did you use as I also want to put my blog like yours.

I use vuepress.

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

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

can anyone tell me what is wrong with my code for problem D? code Link : https://atcoder.jp/contests/abc176/submissions/16215981

It's only problem in 4 test case..

Edit: It is resolved. I did not look at the constraints properly :(.

Do you know why my code gets TLE in problem D ?

https://www.ideone.com/1LKnsI