chokudai's blog

By chokudai, history, 5 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +23
  • Vote: I do not like it

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

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

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like 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 :)

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

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, # |
  Vote: I like it 0 Vote: I do not like it

every Sundy holding a contest?

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

    Not necessarily. Sometimes Atcoder contests are on Saturdays.

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

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

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

Are contests always held on weekends and last 100 minutes?

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

Where will we get the english editorial?

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

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

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

    convert the japanese editorial to english using google translate

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

Should have delayed the contest.

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

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:

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

How to solve F??

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

    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, # |
  Vote: I like it +3 Vote: I do not like it

Hints for E, please.

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

    $$$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   Vote: I like it 0 Vote: I do not like it

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

      Somebody spot my bug?

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
        Vote: I like it 0 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

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

    angle is not 60 degree its 80 degree

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I used abs() and mine was AC ?

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

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

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

    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, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

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

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

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

    Check out this step by step explanation!

    https://youtu.be/MMIsHmZyAxk

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

    #define pi 3.14159265358979323846
    
    #include <iostream>
    #include <cmath>
    #include <iomanip>
    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, # |
  Vote: I like it +1 Vote: I do not like it

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   Vote: I like it +3 Vote: I do not like it

    We need to "normalize" the fraction, something like

    code

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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   Vote: I like it +3 Vote: I do not like it

      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

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

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

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

      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   Vote: I like it 0 Vote: I do not like it

        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, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    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, # |
  Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I also applied same but couldn't solve further

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

    same problem

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

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

is there a way to see failed test in atcoder?

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

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

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

    please help in C question

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

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

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

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

            OK! I never thought about that

            thanks for the help

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

      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   Vote: I like it 0 Vote: I do not like it

      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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

Give me hint for D, please!

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

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

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

How to solve E ?

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

    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, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

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

        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   Vote: I like it +2 Vote: I do not like it

        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

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

          by second set do you mean -Bj/Aj?

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

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

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

            i am also stuck with the same problem

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

            agrawal117

            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   Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If Graph is not connected answer is "No".

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

    Graph not connected.

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

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

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

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    Answer always exists

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

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

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

c & d were nice..

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

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

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

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

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

    cos takes radians here, but your angle is in degrees

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

How to solve E ?

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

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 !

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

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

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

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        DFS is wrong when there is a cycle in the graph

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

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

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

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

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

            consider this test case:

            6 6

            1 2

            2 3

            3 4

            4 5

            5 6

            6 1

            Try to figure yourself!

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

            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   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

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

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

      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   Vote: I like it +28 Vote: I do not like it

        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.

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

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

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

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

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

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

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

    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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months ago, # |
Rev. 3   Vote: I like it +23 Vote: I do not like it

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

A
B
C
D
E
F
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it -13 Vote: I do not like it

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

#define pi 3.14159265358979323846

#include <iostream>
#include <cmath>
#include <iomanip>
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, # |
  Vote: I like it -13 Vote: I do not like it

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

https://youtu.be/JUpcm4SRhEs

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

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

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

      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, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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