### chokudai's blog

By chokudai, history, 5 months ago,

We will hold AtCoder Beginner Contest 168.

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

We are looking forward to your participation!

• +23

 » 5 months ago, # |   +38 Unfortunately, the contest clashes with Kickstart Round C. Can you reschedule it?
 » 5 months ago, # |   +10 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 :)
 » 5 months ago, # |   +4 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.
 » 5 months ago, # |   0 every Sundy holding a contest?
•  » » 5 months ago, # ^ |   +3 Not necessarily. Sometimes Atcoder contests are on Saturdays.
 » 5 months ago, # |   +6 Could the Atcoder round be delayed by some hours, to allow Google Kickstart participants to compete in the same?
 » 5 months ago, # |   +1 Are contests always held on weekends and last 100 minutes?
•  » » 5 months ago, # ^ |   0 not necessary
 » 5 months ago, # |   0 Where will we get the english editorial?
•  » » 5 months ago, # ^ |   0 On the contest site in a couple of days. Just open the "Editorial" tab.
•  » » 5 months ago, # ^ |   0 convert the japanese editorial to english using google translate
 » 5 months ago, # |   0 Should have delayed the contest.
 » 5 months ago, # |   0 What's with AtCoder standings? They seem to keep loading since the last few contestsBasically, have to see this screen for most of the contest:
•  » » 5 months ago, # ^ |   0 Works just fine for me, try a different browser perhaps?
•  » » 5 months ago, # ^ |   0 It's working fine for me.
 » 5 months ago, # |   0 How to solve F??
•  » » 5 months ago, # ^ |   +1 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 :(
 » 5 months ago, # |   +3 Hints for E, please.
•  » » 5 months ago, # ^ |   +3 $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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 In second testcase I get 575 with this, which is 96 else than the expected ans.Somebody spot my bug? Code#include using namespace std; const bool ready = [](){ std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout << std::fixed << std::setprecision(12); return true; }(); const double PI = acos(-1); typedef long long ll; #define int ll #define fori(n) for(int i=0; i>i; #define cins(s) string s; cin>>s; #define cind(d) double d; cin>>d; #define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; } #define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; } #define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; } typedef pair pii; typedef pair pdd; typedef vector vd; typedef vector vb; typedef vector vi; typedef vector vvi; typedef vector vs; const int MOD=1e9+7; int mul(const int v1, const int v2, int mod=MOD) { return (int)((1LL * v1 * v2) % mod); } int pl(int v1, int v2, int mod=MOD) { int res = v1 + v2; while(res < 0) res += mod; while(res>=mod) res-=mod; return res; } /* int pow */ int toPower(int a, int p, int mod=MOD) { int res = 1; while (p != 0) { if (p & 1) res = mul(res, a, mod); p >>= 1; a = mul(a, a, mod); } return res; } 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); } int tPow(int i) { assert(i>=0); if(i==0) return 1; return toPower(2,i); } /* find pairs with * p1.a*p2.a==-p1.b*p2.b * p1.a=(-p1.b*p2.b)/p2.a; * p1.a/-p1.b=p2.b/p2.a; * * foreach sardine * combis=toPower(2, n-opposite); */ void solve() { cini(n); vector p(n); map f; for(int i=0; i>p[i].first>>p[i].second; p[i]=norm(p[i]); f[p[i]]++; } int ans=0; for(pii ab : p) { //ans++; f[ab]--; n--; pii r={ -ab.second, ab.first}; r=norm(r); int g=tPow(n-f[r]); //cerr<<"gaus: "<
•  » » » 5 months ago, # ^ |   0 How did you make a pool? Can DSU be used? And how to rapidly search the values that would be grouped together?
•  » » » » 5 months ago, # ^ |   0 I used a HashMap. You should also store over ai/bi in reduced form, and you can do that by dividing by the gcd.
•  » » » 5 months ago, # ^ |   0
 » 5 months ago, # |   +2 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!
•  » » 5 months ago, # ^ |   +8 you need to also consider the movement of hour hand due to the movement of minute hand
•  » » 5 months ago, # ^ |   +5 angle is not 60 degree its 80 degree
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 5 months ago, # ^ |   0 Hour hand is not at 50m. It has moved 2/3rd of the way from 10 to 11 in the 40 minutes.
•  » » » » » 5 months ago, # ^ |   0 Oops... my bad :(( Thank a lot!
•  » » » » » 5 months ago, # ^ |   0 Can you help me in my Solution. I'm getting correct angle between clock hands but some test cases are showing WA.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 months ago, # ^ |   0 I used abs() and mine was AC ?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 5 months ago, # ^ |   0 Probably because I passed the angle in degrees in abs() then changed it into radians.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 5 months ago, # ^ |   +1 Don't forget that clock hands won't travel instantly between two consecutive values!
•  » » 5 months ago, # ^ |   0 Thank you guys! I forgot the movement of the hour hand :((
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Check out this step by step explanation!https://youtu.be/MMIsHmZyAxkThis video provides a step by step of the code as well. #define pi 3.14159265358979323846 #include #include #include using namespace std; int main(){ long double a, b, h, m; cin >> a >> b >> h >> m; //calculating deg long double hdeg = h*30; long double mdeg= m*6; hdeg+=mdeg/12; long double deg = abs(hdeg-mdeg); //apply law of cosines long double cosdeg = cos(deg* pi/180); long double asqr = a*a; long double bsqr= b*b; long double c = sqrt(asqr+bsqr-2*a*b*cosdeg); cout << fixed << showpoint; cout << setprecision(20); cout << c << endl; return 0; 
 » 5 months ago, # |   +1 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?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 We need to "normalize" the fraction, something like codepii 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?
•  » » » 5 months ago, # ^ |   0 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?
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 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 2Answer should be 6
•  » » » » 5 months ago, # ^ |   0 For tc 10 3 2 3 2 -1 1 2 -1 -3 -9 -8 12 7 7 8 1 8 2 8 4 my output of program i=0 no. of bad values=0 bad sets till now=0 i=1 no. of bad values=0 bad sets till now=0 i=2 no. of bad values=0 bad sets till now=0 i=3 no. of bad values=0 bad sets till now=0 i=4 no. of bad values=0 bad sets till now=0 i=5 no. of bad values=2 bad sets till now=24 i=6 no. of bad values=1 bad sets till now=56 i=7 no. of bad values=0 bad sets till now=112 i=8 no. of bad values=0 bad sets till now=224 i=9 no. of bad values=0 bad sets till now=448 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 thatSo 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
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 5 months ago, # ^ |   0 can u help in this Problem E
•  » » 5 months ago, # ^ | ← Rev. 2 →   +5 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
 » 5 months ago, # |   +6 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 :/
•  » » 5 months ago, # ^ |   0 I know! From this logic there would be atmost n^2 ways but it wasn't the case in sample test-2 it self.
•  » » 5 months ago, # ^ |   +5 I also applied same but couldn't solve further
•  » » 5 months ago, # ^ |   0 same problem
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   0 i think we also need to multiply (2^remaining numbers) with your product. what do you think?
•  » » 5 months ago, # ^ |   +4 It looks like people are counting pairs but it needs the number of subsets.
•  » » » 5 months ago, # ^ |   0 I summed up for every sardine pow(2, numMatching).
 » 5 months ago, # |   0 is there a way to see failed test in atcoder?
•  » » 5 months ago, # ^ |   +3 Usually, test cases will be uploaded after few days ig in here
•  » » 5 months ago, # ^ |   +1 please help in C question
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ |   0 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
•  » » » » » 5 months ago, # ^ |   0 BTW the test case was3 4 10 40 so the angle between hr and min hand must be 60 degrees or pie/3 rad
•  » » » » » 5 months ago, # ^ |   0 After 10 hours the hour hand moves 300 degrees. But for the 40 minutes, it moves another 20 degrees.
•  » » » » » » 5 months ago, # ^ |   0 OK! I never thought about that thanks for the help
•  » » » 5 months ago, # ^ |   0 Find the angle between hours hand and minutes hand, then c^2 = a^2 + b^2 — 2*a*b*cos(theta) is your answer.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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)
•  » » » » 5 months ago, # ^ |   0 bro, i am getting wrong answer
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Give the link of ur code.i got ac submitting using this logic
•  » » » » » » 5 months ago, # ^ |   0 done dude thanks for the help
•  » » » 5 months ago, # ^ |   0 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
•  » » » » 5 months ago, # ^ |   0 thanks for the help
 » 5 months ago, # |   0 Give me hint for D, please!
•  » » 5 months ago, # ^ |   +1 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.
•  » » » 5 months ago, # ^ |   0 thanks you, I didn't understand problem statement fully. So, I printed shortest path:)
•  » » » » 5 months ago, # ^ |   +1 I also did the same and got WA :(
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 SpoilerI used BFS, ShortestPathFirst.
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 There you go: Subpaths of shortest paths are shortest paths.
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   0 It is easier to use BFS, because the weight of each edge is 1.
•  » » 5 months ago, # ^ |   +3 D is quite dumb, you just need to print parent list of dfs tree
•  » » » 5 months ago, # ^ |   0 Or simple bfs =)
 » 5 months ago, # |   0 How to solve E ?
•  » » 5 months ago, # ^ |   0 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.
•  » » » 5 months ago, # ^ |   +8 Umm that sounds like D lol. I was asking the solution for E
•  » » » » 5 months ago, # ^ |   0 opps I posted at the wrong place, but I guess this explains the idea for E: https://codeforces.com/blog/entry/77505?#comment-624918
•  » » » » 5 months ago, # ^ | ← Rev. 4 →   +2 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 renamingTotal = Total — no. of set having at least 1 mp[i] and 1 -1/mp[i]sorry for my English
•  » » » » » 5 months ago, # ^ |   0 by second set do you mean -Bj/Aj?
•  » » » » » 5 months ago, # ^ |   +6 but how will you find the no. of sets having atleast 1 of mp[i] typeand 1 of-1/mp[i] type, without overcounting . ?will u please elaborate this part ??
•  » » » » » » 5 months ago, # ^ |   0 i am also stuck with the same problem
•  » » » » » » 4 months ago, # ^ |   +3 if c1 = count of first type and c2 = count of second type, then no. of sets = (2^c1 + 2^c2 — 1)
 » 5 months ago, # | ← Rev. 3 →   +6 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?
•  » » 5 months ago, # ^ |   0 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
•  » » 5 months ago, # ^ |   0 If Graph is not connected answer is "No".
•  » » 5 months ago, # ^ |   0 Graph not connected.
•  » » 5 months ago, # ^ |   0 if u can reach all the node from 1 then yes,otherwise no
•  » » 5 months ago, # ^ |   0 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 ?
•  » » 5 months ago, # ^ |   0 But if the components are not connected you can't move. hence first check if the graph is connected then use BFS for answer
•  » » 5 months ago, # ^ |   0 I'm not sure but in my solution, I considered the case when the graph is not connected
•  » » 5 months ago, # ^ |   0 Answer always exists
•  » » 5 months ago, # ^ |   0 "Any two rooms" doesn't it mean every pair of room from n rooms are somehow connected ?
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +2 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
 » 5 months ago, # |   +3 c & d were nice..
 » 5 months ago, # |   0 What's wrong in my solution for C ? https://atcoder.jp/contests/abc168/submissions/13348558
•  » » 5 months ago, # ^ |   0 You are passing the angle in cos(angle) as degrees. You need to pass it in radians
•  » » » 5 months ago, # ^ |   0 Damn.....submitted D after so long, because I was stuck on this . Thanx
•  » » 5 months ago, # ^ |   0 cos takes radians here, but your angle is in degrees
 » 5 months ago, # |   +1 How to solve E ?
 » 5 months ago, # | ← Rev. 3 →   0 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 submissionThanks !
•  » » 5 months ago, # ^ |   0 Since "after traversing the minimum number of passages possible", it should be BFS instead of DFS.
•  » » » 5 months ago, # ^ |   0 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 ?
•  » » » » 5 months ago, # ^ |   0 DFS is wrong when there is a cycle in the graph
•  » » » » 5 months ago, # ^ |   0 you can't get the exact level of node by DFS if there is a cycle
•  » » » » » 5 months ago, # ^ |   0 why would dfs not give exact level or to say distance from root ? can you give an example ?
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +6 consider this test case:6 61 22 33 44 55 66 1Try to figure yourself!
•  » » » » » » 5 months ago, # ^ |   +3 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.
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 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
 » 5 months ago, # |   0 How to solve F?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +30 Cut the hole plan into rectangular pieces(Based on the inputted x and y s). There are at most O(N^2) pieces. BFS or DFS to find the accessible rectangular pieces. UPD: my submission
•  » » » 5 months ago, # ^ |   0 Can 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +28 After getting vector 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.
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 Thank you very much! Now I was able to understand the approach and most of the code.
•  » » » » » 5 months ago, # ^ |   0 will not it get TLE? Because the maximum size of the points might be 1e9.
•  » » » » » » 5 months ago, # ^ |   +3 Oh I got it, you divide the blocks first, thanks you!
•  » » 5 months ago, # ^ |   +3 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.
 » 5 months ago, # |   0 How long it takes to get rid of the provisional thing?
 » 5 months ago, # | ← Rev. 3 →   +23 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)using ll = long long; pair reduce(ll x, ll y) { if (x == 0) return make_pair(0, 1); if (y == 0) return make_pair(1, 0); if (x < 0 && y < 0) { x = -x; y = -y; } if (x < 0) { x = -x; y = -y; } ll g = __gcd(abs(x), abs(y)); return make_pair(x / g, y / g); } pair comp(pll frac) { pair r = make_pair(frac.s, frac.f); if (r.f < 0) r.f = -r.f; else r.s = -r.s; return r; }  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)
•  » » 5 months ago, # ^ |   +31 My F was very different: submission
•  » » » 5 months ago, # ^ |   0 Damn, that's so much smoother. Nice :)
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Can someone help me to figure out what is wrong with my solution for E ? https://atcoder.jp/contests/abc168/submissions/13345624My 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 origin3)Neither of the above
•  » » » 5 months ago, # ^ |   +3 I think you run into overflow when you multiply a[i] and b[i] or num and denom.
•  » » » » 5 months ago, # ^ |   +3 Thanks for pointing it out galen_colinI have fixed it but still gives wrong answer. Any ideas ??https://atcoder.jp/contests/abc168/submissions/13358103
 » 5 months ago, # |   0 newbie here, forgive me asking, I did not understand problem D, If anyone can give me any explanation that would be great. thanks
•  » » 5 months ago, # ^ |   0 Read comment.
 » 5 months ago, # | ← Rev. 2 →   0 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
 » 5 months ago, # |   -13 Here is a link to a solution to the problem INCLUDING code for C++https://youtu.be/MMIsHmZyAxkThis video provides an in-depth solution to the problem as well as a step by step explanation of the code #define pi 3.14159265358979323846 #include #include #include using namespace std; int main(){ long double a, b, h, m; cin >> a >> b >> h >> m; //calculating deg long double hdeg = h*30; long double mdeg= m*6; hdeg+=mdeg/12; long double deg = abs(hdeg-mdeg); //apply law of cosines long double cosdeg = cos(deg* pi/180); long double asqr = a*a; long double bsqr= b*b; long double c = sqrt(asqr+bsqr-2*a*b*cosdeg); cout << fixed << showpoint; cout << setprecision(20); cout << c << endl; return 0; } 
 » 5 months ago, # |   -13 Check Out my solution to problem 1 with a step by step code explanation!https://youtu.be/JUpcm4SRhEs
 » 5 months ago, # |   +7 Check out my solution to problem B in this contest with a step by step code explanation!https://youtu.be/HN_9VTFwiVM
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   0 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
•  » » » 5 months ago, # ^ |   0 But we want to minimize the distance from vertex 1, so I think parent is not always best signpost for each vertex.
•  » » » » 5 months ago, # ^ |   0 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
•  » » » » » 5 months ago, # ^ |   0 Yeahh! I got my mistake thank you for your help :)
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   0 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. Spoilervoid bfs(){ queue 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; } } } } 
•  » » » 5 months ago, # ^ |   0 Understood.Thanks. I will definitely try to learn bfs more. BTW,I found this approach on geeksforgeeks. The pair is of child and parent.
 » 5 months ago, # |   0 Can someone please tell me what is wrong with my code for problem E?https://atcoder.jp/contests/abc168/submissions/13534282
 » 4 months ago, # |   0 how to solve problem F ?? does anyone have any approach with explanation??
 » 4 months ago, # | ← Rev. 2 →   0 the question d is simple bfs right?? please correct me if im wrong