chokudai's blog

AtCoder Beginner Contest 275 Announcement
By chokudai, history, 18 months ago, In English

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!

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

Comments Comments (19)
| Write comment?
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve task d?

→ Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

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

Is there an elegant way to solve C?

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

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

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

    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

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

    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.

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

    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

    → Reply
»
18 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

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

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

      → Reply
    • »
      »
      »
      18 months ago, # ^ |
      ← Rev. 6   Vote: I like it +9 Vote: I do not like it

      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.

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

        This is something new I learned today. Thanks a lot!!

        → Reply
»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

How to solve today's C?

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

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

    → Reply
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do F ?

→ Reply
  • »
    »
    18 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
18 months ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply