Блог пользователя chokudai

Автор chokudai, история, 7 лет назад, По-английски

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
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +38 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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 :)

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

every Sundy holding a contest?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Are contests always held on weekends and last 100 minutes?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Where will we get the english editorial?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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:

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F??

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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 :(

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Hints for E, please.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +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.

    • »
      »
      »
      7 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

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

      Somebody spot my bug?

      Code
    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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!

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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?

  • »
    »
    7 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +3 Проголосовать: не нравится

    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?

    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 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?

    • »
      »
      »
      7 лет назад, скрыть # ^ |
      ← 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 2

      Answer should be 6

      • »
        »
        »
        »
        6 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 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 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

    • »
      »
      »
      7 лет назад, скрыть # ^ |
      ← 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.

  • »
    »
    7 лет назад, скрыть # ^ |
    ← 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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +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 :/

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

is there a way to see failed test in atcoder?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Give me hint for D, please!

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve E ?

»
7 лет назад, скрыть # |
← 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?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

c & d were nice..

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
»
7 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

How to solve E ?

»
7 лет назад, скрыть # |
← 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 submission

Thanks !

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

»
7 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +23 Проголосовать: не нравится

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

A
B
C
D
E
F
»
7 лет назад, скрыть # |
← 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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

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

https://youtu.be/HN_9VTFwiVM

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 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

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 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.

  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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.

    Spoiler
»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

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