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

AtCoder Beginner Contest 275 Announcement
Автор chokudai, история, 4 года назад, По-английски

We will hold AtCoder Beginner Contest 275.

The point values will be 100-200-300-400-500-500-600-600. We are looking forward to your participation!

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

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

how to solve task d?

→ Ответить
»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +24 Проголосовать: не нравится

Me: Problem C takes more time than E and F combined.

Is there an elegant way to solve C?

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

    I found C a lot harder than E,F as well, so I'm also wondering :)

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

    You can store all pawns and go through all possible 4 pawns('#') and check whether you can form a square using these 4 pawns or not.

    Condition to check whether we can form a square:-

    A). The set of distances for each point to its 3 neighbors must be the same.

    One possible example:-

    B). The 2 shortest distances among 3 distances must be the same ( In the above example it is 1 ).

    My submission:- https://atcoder.jp/contests/abc275/submissions/36069709

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

    Iterate over all the pairs of squares, consider this pair as a side and rotate this 90 degrees (counterclockwise, to do this : note that the slopes of perpendicular lines multiply to -1. so we need to swap dx and dy, multiply dx by -1) twice to get all four coordinates of the square. If all four coordinates have s[i][j] = '#', increase the answer by 1. Final answer will be ans/4 since all 4 sides generate the same square by counterclockwise rotation. Code. I learned this trick from Heno239's submission.

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

    maybe you can try to fixed the "left upper" corner of the square, and enumrate the "top" edge. that's enough and no duplicate.

    sample code. note that another point of top edge is relative to the top right of the first point. see inner for loops

    → Ответить
»
4 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

math957963 Can you help me out, For Problem B. Why is the following piece of code giving WA. It is exactly the same as editorial.

ll A,B,C,D,E,F;
cin>>A>>B>>C>>D>>E>>F;
    
ll v1 = ( (A%P * B%P)%P * C%P)%P;
ll v2 = ( (D%P * E%P)%P * F%P)%P;
    
cout<<(v1 - v2 + P)%P<<"\n";

PS: New to codeforces so don`t know how to wrap a code in block.

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

How to solve today's C?

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

How to do F ?

→ Ответить
»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

Here provide a different solution of $$$G$$$.
$$$Binary Search$$$
Assume the answer is $$$mid$$$. we need to check if $$$X$$$ exist.

$$$ \frac{\sum_{i=1}^n X[i] * c[i]}{\max(\sum_{i=1}^n X[i] * b[i],\sum_{i=1}^n X[i] * a[i]) } \ge mid $$$

$$$X[i]$$$ is real-valued number.
let $$$P[i]=(c[i] - mid * b[i], c[i] - mid * a[i])$$$. The conditions becomes

$$$ \begin{cases} \sum_{i=1}^n X[i] * P[i].first \ge 0 \\ \sum_{i=1}^n X[i] * P[i].second \ge 0 \end{cases} $$$

let $$$G[i] = (\frac{P[i].y}{P[i].x}, [P[i].x\ge0])$$$. if $$$G[i].y=true$$$ and $$$G[i].x \ge 0$$$, $$$X$$$ exist.
Or we check if

$$$-\min(\{g \in G | g.y = false\}).x \ge -\max(\{g \in G | g.y = true\}).x$$$

code

→ Ответить