Not necessarily. Sometimes Atcoder contests are on Saturdays.

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

convert the japanese editorial to english using google translate

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

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 :(

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

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

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.

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 :((

We need to "normalize" the fraction, something like

pii norm(pii p) {
    if(p.first==0 && p.second==0)
        return p;
    else if(p.first==0) {
        p.second=1;
        return p;
    } else if(p.second==0) {
        p.first=1;
        return p;
    } else {
        int g=__gcd(abs(p.first), abs(p.second));
        p.first/=g;
        p.second/=g;
        if(p.first<0) {
            p.first=-p.first;
            p.second=-p.second;
        }
        return p;
    }
    assert(false);
}

Then 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?

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

I also applied same but couldn't solve further

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.

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

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

please help in C question

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.

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.

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

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.

If Graph is not connected answer is "No".

Graph not connected.

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 ?

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

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

1. Cut the hole plan into rectangular pieces(Based on the inputted x and y s). There are at most O(N^2) pieces.
2. BFS or DFS to find the accessible rectangular pieces.

UPD: my submission

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 F including me.

My F was very different: submission

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

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 array

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.

void bfs(){
    queue<int> q;
    q.push(1);
    visited[1] = true;
    
    while(q.size()){
        int cur = q.front(); q.pop();
        for(auto i : adj[cur]){
            if(!visited[i]){
                ans[i] = cur;
                q.push(i);
                visited[i] = true;
            }
        }
    }
}