We will hold AtCoder Beginner Contest 168.

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

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

We are looking forward to your participation!

Unfortunately, the contest clashes with Kickstart Round C. Can you reschedule it?

It would be considerate of you if you can reschedule the contest, as it collides with Kickstart round. During the quarantine time, we really wish to attend contest.

Thank you :)

It would be great if you guys reschedule the event, the number of participants will reduce due to the clash with Google Kickstart Round C.We really wish to participate in the maximum number of contests.

Thank you.

every Sundy holding a contest?

Not necessarily. Sometimes Atcoder contests are on Saturdays.

Could the Atcoder round be delayed by some hours, to allow Google Kickstart participants to compete in the same?

Are contests always held on weekends and last 100 minutes?

not necessary

Where will we get the english editorial?

On the contest site in a couple of days. Just open the "Editorial" tab.

convert the japanese editorial to english using google translate

Should have delayed the contest.

What's with AtCoder standings? They seem to keep loading since the last few contests

Basically, have to see this screen for most of the contest:

Works just fine for me, try a different browser perhaps?

It's working fine for me.

How to solve F??

It looked like a monstrous casework problem where you first de-sparseify the x and y coordinates into a range 1 ~ 4000, and then do a BFS. I didn't debug my code in time though, since it was too complex :(

Hints for E, please.

$$$A_i$$$ * $$$A_j$$$ + $$$B_i$$$ * $$$B_j$$$ = 0 can be written as

$$$A_i$$$/$$$B_i$$$ = -$$$B_j$$$/$$$A_j$$$ = -1/($$$A_j$$$/$$$B_j$$$)

Handle cases with A = 0 or B = 0 separately and simply multiply no. of choices from each "pool". A pool is values of $$$A_i$$$/$$$B_i$$$ that are x/y and -y/x.

In second testcase I get 575 with this, which is 96 else than the expected ans.

Somebody spot my bug?

CodeHow did you make a pool? Can DSU be used? And how to rapidly search the values that would be grouped together?

I used a HashMap. You should also store over ai/bi in reduced form, and you can do that by dividing by the gcd.

hELP IN PROBLEM E TESTCASE

I finished A B D in 10 min but could not solve C in 90 min. In the second sample test case, the angel is 60 degree, and a = 3, b = 4. why the input is 4,56... instead of sqrt(13)? Could anyone explain me? Thank a lot!

you need to also consider the movement of hour hand due to the movement of minute hand

angle is not 60 degree its 80 degree

10h40, so the hour hand is equivalent to 50m and the minute hand is 40m, so the degree is ((50 — 40) / 60) * 360? Isn't it?

Hour hand is not at 50m. It has moved 2/3rd of the way from 10 to 11 in the 40 minutes.

Oops... my bad :(( Thank a lot!

Can you help me in my Solution. I'm getting correct angle between clock hands but some test cases are showing WA.

The angle should be $$$\theta = 80^{\circ}$$$, not $$$\theta = 60^{\circ}$$$. From here, I believe that you can just use the Law of Cosines. Also, using $$$\verb!abs()!$$$ instead of $$$\verb!fabs()!$$$ would have caused WA.

I used abs() and mine was AC ?

I'm not too sure then. Switching $$$\verb!abs()!$$$ to $$$\verb!fabs()!$$$ (and leaving everything else the same) took me from WA to AC. It must have been something else in my code.

Probably because I passed the angle in degrees in abs() then changed it into radians.

Use this formula for angle between minutes and hours hand:- theta = fabs((60*H-11*M)/2) and then use cosine rule for third side.

Don't forget that clock hands won't travel instantly between two consecutive values!

Thank you guys! I forgot the movement of the hour hand :((

Check out this step by step explanation!

https://youtu.be/MMIsHmZyAxk

This video provides a step by step of the code as well.

For E I stored the values of each

`A[i]/B[i]`

and`B[i]/A[i]`

in 2 maps. Then it seemed like I have to exclude the ones not possible from the total possible ways...but I was not able to think of how to do that. Can somebody tell how or suggest a better method?We need to "normalize" the fraction, something like

codeThen we can search for every sardine the matching ones in a map. From that the number of possible sets should be toPower(2,n).

But that gave wrong result for me. I done know why?

The "normalizing" part is for handling division by 0 right?

Wouldn't the number of sets be

`pow(2,n)-1`

as we should exclude null set?I think it is due to 01 and 10 fractions, as they can't be in the same group. Try something like:

4 1 0 2 0 0 1 0 2

Answer should be 6

For tc

my output of program

what im doing is finding if no. of bad values is >0 then i am doing (2^(val)-1)*(2^(i-val)) and adding them to ans and if val is zero then ans+=ans as that zero can be appended to any set prior to that

So for i=5 (2^2-1)*(2^3)=24,for i=6 (2^1-1)(2^5)=32;so ans =24+56 till i=6; after that we are simply appending zeros so adding ans=ans+ans but i am counting less bad sets ,dont know where i am wrong

can you explain the part where if p.first<0 then you are changing the sign of p.first and p.second?I have seen this earlier also but unable to understand the reason to change the signs.

To make a fraction negative one can negate both parts. $$$\frac{-a}{b} = \frac{a}{-b}$$$

But in this problem we need to find the inverted fraction in a map or set. For the comparator it makes a difference on which part the sign is, so we manually put the minus sign to the first or second part.

can u help in this Problem E

I guess pair {A[i],B[i]} and {B[i],A[i]} storing will be better than your above approach as A[i],B[i]<=1e18 ,may be error came due to precision and don't forgete to divide A[i] and B[i] by their gcd before insert

C not so nice, had enough geometry for today. How works E?

I tried to find number of matching sardines by searching the frequency of the negative inverse of current sardine.

$$$s1.a/s1.b == -s2.a/s2.b$$$

Somehow this did not work :/

I know! From this logic there would be atmost n^2 ways but it wasn't the case in sample test-2 it self.

I also applied same but couldn't solve further

same problem

This is supposed to work. In that way didn't we find the answer for test case 1 as (2^3-1)-(2^2-1)? Where 2^3-1 would be the total ways of choosing one or more pairs and 2^2-1 will be ways of choosing 1 or more of invalid pairs? I'm stuck at E too.

i think we also need to multiply (2^remaining numbers) with your product. what do you think?

It looks like people are counting pairs but it needs the number of subsets.

I summed up for every sardine pow(2, numMatching).

is there a way to see failed test in atcoder?

Usually, test cases will be uploaded after few days ig in here

please help in C question

You had to use the cosine rule. Let the distance be d then, d^2 = a^2 + b^2 — 2*a*b*cos(theta) , theta being the angle between the 2 hands.

I used cosine formula but still couldn't get this test case right (I was getting square root 13 as answer but you can clearly see that this answer his more than that)

Please help

BTW the test case was

3 4 10 40

so the angle between hr and min hand must be 60 degrees or pie/3 rad

After 10 hours the hour hand moves 300 degrees. But for the 40 minutes, it moves another 20 degrees.

OK! I never thought about that

thanks for the help

Find the angle between hours hand and minutes hand, then c^2 = a^2 + b^2 — 2*a*b*cos(theta) is your answer.

first find the angle bet h & m. angle=.5*(60*h-11*m) if(angle>180)then angle=360-angle then convert it into radian and then use cosine rule.. c^2=a^2+b^2-2*a*b*cos(angle)

bro, i am getting wrong answer

Give the link of ur code.i got ac submitting using this logic

done dude thanks for the help

at first find out the angle between two stricks then imagine a triangle and find out last arm of the triangle , cos(C) = (a*a+b*b-c*c)/2*a*b you need c

thanks for the help

Give me hint for D, please!

You just need to do BFS and check whether the graph is connected if it is not then the answer is No. else you need to also store the parents of each of the vertex and output them.

thanks you, I didn't understand problem statement fully. So, I printed shortest path:)

I also did the same and got WA :(

One weird thing I noticed is that if I don't keep a provision to check if the Graph is connected or not, my solution passes. Maybe weak test cases.

The problem mentioned that "One can travel between any two rooms by traversing passages". So the graph is always connected and an ans always exists.

SpoilerI used BFS, ShortestPathFirst.

I first made a undirected graph, and then found the distance from 1 to all nodes. After this was done, I had the distances and then I simply found the adjacent node for a given node that was at the least distance from 1. This would be the answer for that node.

There you go: Subpaths of shortest paths are shortest paths.

You can use Dijkstra to solve it.

To judge Yes or No, you can traverse every points. If every points can be reached, it's Yes. To print all prev, You need to create a new array ans[] to store the prev of every points(except 1) and update them.

It is easier to use BFS, because the weight of each edge is 1.

D is quite dumb, you just need to print parent list of dfs tree

Or simple bfs =)

How to solve E ?

it's a straightforward bfs, but took me 1 hour to finish, guess i'm rusty now.

basically you record the predecessors when you perform bfs, finally check if every vertex got a predecessor.

Umm that sounds like D lol. I was asking the solution for E

opps I posted at the wrong place, but I guess this explains the idea for E: https://codeforces.com/blog/entry/77505?#comment-624918

My approach :

$$$A_i.A_j+B_i.B_j=0$$$ can be converted into $$$A_i/B_i = -B_j/A_j$$$

Total number of set is $$$2^n-1$$$ (-1 empty set).

bad set when given condition violets :

create a map having count of $$$A_i/B_i$$$ (Note : consider for cases $$$(0,0),(a,0),(0,a))$$$ , iterate over map and for every $$$mp[i]$$$ find count of $$$-1/mp[i]$$$ now we have three set

first : $$$A_i/B_i = mp[i],$$$ second : $$$A_i/b_i = -1/mp[i],$$$ third : all renaming

Total = Total — no. of set having at least 1 mp[i] and 1 -1/mp[i]

sorry for my English

by second set do you mean -Bj/Aj?

but how will you find the no. of sets having atleast 1 of mp[i] type

and 1 of-1/mp[i] type, without overcounting . ?

will u please elaborate this part ??

i am also stuck with the same problem

agrawal117

if c1 = count of first type and c2 = count of second type, then no. of sets = (2^c1 + 2^c2 — 1)

Problem D stated that "One can travel between any two rooms by traversing passages" so an answer should always exist , isn't it ? What did I miss?

Passages denote edges. So let's say if a node is isolated from the rest of the graph, then there is no way to reach 1

If Graph is not connected answer is "No".

Graph not connected.

if u can reach all the node from 1 then yes,otherwise no

But as he said, the problem mentioned "One can travel between any two rooms by traversing passages". So that means the graph is always connected ?

But if the components are not connected you can't move. hence first check if the graph is connected then use BFS for answer

I'm not sure but in my solution, I considered the case when the graph is not connected

Answer always exists

"Any two rooms" doesn't it mean every pair of room from n rooms are somehow connected ?

I just resubmitted my solution for D. At this time, I assume that the answer always exist. And yes, it actually always exist. https://ideone.com/vW3Igv

c & d were nice..

What's wrong in my solution for C ? https://atcoder.jp/contests/abc168/submissions/13348558

You are passing the angle in cos(angle) as degrees. You need to pass it in radians

Damn.....submitted D after so long, because I was stuck on this . Thanx

`cos`

takes radians here, but your angle is in degreesHow to solve E ?

My approach for Problem D ->

For every node from 2..n , I found it's adjacent node that has smallest level from root i.e 1 using dfs and printed it. Can anybody give a test case where this will fail or tell why would this fail? Link to submission

Thanks !

Since "after traversing the minimum number of passages possible", it should be BFS instead of DFS.

but any node among the neighbors that is closest to the root(1) must be the one that we show using signpost ? isn't it ?

DFS is wrong when there is a cycle in the graph

you can't get the exact level of node by DFS if there is a cycle

why would dfs not give exact level or to say distance from root ? can you give an example ?

consider this test case:

6 6

1 2

2 3

3 4

4 5

5 6

6 1

Try to figure yourself!

If there is a circle in the graph you do not know in wich direction the dfs goes throug the circle. If it is the wrong one, you get the wrong result.

Hello

Well if graph is not connected then u cannot reach 1 in that case there u should print 'No'

Stay safe, Have a nice day

How to solve F?

UPD: my submissionCan you please explain your approach a little more? and can you please just briefly tell me what do you do in your code after you separate out unique coordinates on both axes.

After getting

`vector<int>`

xs and ys, split the plan into blocks like this. (UPD: note that the index in the picture is a little different from the one used in my code)The yellow mark means that you cannot pass between the two blocks. I used l[x][y], r[x][y], u[x][y], dd[x][y] to denote wether block (x, y) cannot go left, right, up, down.

Do a DFS/BFS to know which blocks are reachable.

The answer is the sum of areas of the reachable blocks. Because there is -INF, and INF in xs and ys, if I can reach block (0, 0), the answer mush be INF.

Thank you very much! Now I was able to understand the approach and most of the code.

will not it get TLE? Because the maximum size of the points might be 1e9.

Oh I got it, you divide the blocks first, thanks you!

These days Atcoder is not publishing editorials in English, at least not anytime soon after contest finishes. I guess there are a lot of people who would want solution to

Fincluding me.How long it takes to get rid of the provisional thing?

Brief solution sketches, before the editorial in English comes out:

ADo exactly what the problem tells you to.

BSee A.

CSome trigonometry allows you to work out a formula like this for the points: Compute $$$\theta$$$ for each hand by determining the ratio of how much it's spun to a full rotation (initially, both angles are $$$90$$$ degrees), then you just have to find the distances between the two points.

DRun a BFS from room $$$1$$$, and the sign from each node should point to the parent in the BFS tree of the node. The graph is connected, so there's always a solution.

EI represent a sardine $$$i$$$ as $$$(A_i, B_i)$$$. Sardines that are $$$(0, 0)$$$ will be on bad terms with all other sardines, and can only be in a subset by themselves, so treat them separately. Otherwise, a sardine $$$(a, b)$$$ will be compatible with all other sardines except those of the form $$$(-b, a)$$$ (more on that later). These sardines are independent of other sardines because taking a sardine doesn't affect any other sardine that's compatible with it. For a single type of sardine, you can take any subset of that, any subset of the complement, or none at all. So the answer is $$$\prod_i (2^{count(i)} + 2^{count(complement(i))} - 1)$$$, subtracting 1 because that formula double-counts the option of taking nothing. Be careful not to overcount (because this formula will double-multiply due to $$$i$$$ being considered both as itself and as a complement).

The only remaining issue is that $$$(a, b)$$$ should also be incompatible with something like $$$(-2a, 2b)$$$. This can be dealt with by dividing by the GCDs and being careful with zeroes. Something like this will work.

(nested spoiler)FThis problem should not exist. But because it does, I'll give my solution.

Run a sweepline on $$$x$$$ (or $$$y$$$) and maintain a set of segments that represents each component. When you encounter a new horizontal line, possibly split one segment into two (but keep them in the same component). When you encounter a vertical line, if it blocks off the entirety of (at least one) segment, cut off that segment's component and start a new one. When you encounter the end of a horizontal line, merge the two components that were split by it (I used DSU to do this). Update areas as you go (keep track of the last $$$x$$$-coordinate seen before the current one). There are only $$$O(M)$$$ possible segments at each point of interest and $$$O(N + M)$$$ points of interest, so the complexity is something like $$$O(M(N + M)\alpha(NM))$$$. I would share my code, but I think it's too messy to be helpful. Feel free to ask about this one (or E, or others).

(Note: this approach also requires merging intersecting horizontal/vertical lines into one)

My F was very different: submission

Damn, that's so much smoother. Nice :)

Can someone help me to figure out what is wrong with my solution for E ?

https://atcoder.jp/contests/abc168/submissions/13345624

My logic is almost similar to the one given by galen_colin but is failing from test cases 11 to 19 .

I am dividing coordinates (a,b after dividing by gcd) to 3 cases:

1)Origin(0,0)

2)either on x-axis or on y-axis but not origin

3)Neither of the above

I think you run into overflow when you multiply

`a[i]`

and`b[i]`

or`num`

and`denom`

.Thanks for pointing it out galen_colin

I have fixed it but still gives wrong answer. Any ideas ??

https://atcoder.jp/contests/abc168/submissions/13358103

newbie here, forgive me asking, I did not understand problem D, If anyone can give me any explanation that would be great. thanks

Read comment.

Problem E. Here's my solution .(it's giving AC for half of the test cases).

Could anyone please tell me my MISTAKE. (apart from the fact that i need to take care of the {0,y} or {y,0} case separately).

https://atcoder.jp/contests/abc168/submissions/13350298

Here is a link to a solution to the problem INCLUDING code for C++

https://youtu.be/MMIsHmZyAxk

This video provides an in-depth solution to the problem as well as a step by step explanation of the code

Check Out my solution to problem 1 with a step by step code explanation!

https://youtu.be/JUpcm4SRhEs

Check out my solution to problem B in this contest with a step by step code explanation!

https://youtu.be/HN_9VTFwiVM

I have tried On D using Bfs and finding the depth of each node, then I for each node I find the minimum depth in it's adjacent nodes with O(logn) and print it, so we get complexity of O(nlogn), but still I'm getting WA And TLE. can anyone help? Link to My submition: https://atcoder.jp/contests/abc168/submissions/13368080

when you find depth you do

`depth[currentNode] = 1 + depth[parent]`

you don't need the depth. You just have to know who the parent of that node is, so just take`depth[currentNode] = parent`

and print the depth arrayBut we want to minimize the distance from vertex 1, so I think parent is not always best signpost for each vertex.

Why do you think your logic to find the depth of a node works using bfs? because bfs always finds shortest path. Hence, if you found a node using bfs, going through that parent gives you the shortest path. My AC code

Yeahh! I got my mistake thank you for your help :)

Can someone please tell me why my code is wrong for problem D? I don't have much experience in graphs yet so I can't figure out the mistake.Here is the link to my submission.

what are you making pair for? you probably don't know how a bfs works, read on it and try coding it. I changed your bfs method and this works. check if you're still stuck after reading on bfs.

SpoilerUnderstood.Thanks. I will definitely try to learn bfs more. BTW,I found this approach on geeksforgeeks. The pair is of child and parent.

Can someone please tell me what is wrong with my code for problem E?

https://atcoder.jp/contests/abc168/submissions/13534282

how to solve problem F ?? does anyone have any approach with explanation??

the question d is simple bfs right?? please correct me if im wrong