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

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

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

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve task d?

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

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

Is there an elegant way to solve C?

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

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

    → Ответить
  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 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

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

    → Ответить
  • »
    »
    19 месяцев назад, # ^ |
    ← 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

    → Ответить
»
19 месяцев назад, # |
← 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.

→ Ответить
  • »
    »
    19 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    The problem is that the priority of * is higher than the one of %.

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

      This is something new I learned today. Thanks alot!!

      → Ответить
    • »
      »
      »
      19 месяцев назад, # ^ |
      ← Rev. 6   Проголосовать: нравится +9 Проголосовать: не нравится

      No. The precedence of the operators * and % are the same (see row 5). The fact is that since they are left-associative, A % P * B % P is parsed as ( (A%P) * B ) % P. Since A%P $$$\sim 10^9$$$ and B $$$\sim 10^{18}$$$, (A%P) * B possibly causes an overflow in a 64-bit integer type, resulting in a wrong answer.

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

How to solve today's C?

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

    Other than check 4 sides are equal, also need to check if 2 adjacent sides are at right angle.

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

How to do F ?

→ Ответить
  • »
    »
    19 месяцев назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    let dp[i][j] be the minimum no.of operations required on the array A[i..N] to get the sum j. Take the transitions accordingly. Here is the link to my submission

    → Ответить
»
19 месяцев назад, # |
← 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

→ Ответить