chokudai's blog

AtCoder Beginner Contest 292 Announcement
By chokudai, history, 22 months ago, In English

We will hold AtCoder Beginner Contest 292.

The point values will be 100-200-300-400-500-500-600-600.

We are looking forward to your participation!

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

Comments Comments (28)
| Write comment?
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

lol, bday moment: G is problem you prepared 5 years ago, Ex is $$$O(qlog^2n)$$$ passed in 500 ms,

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

What is the intended solution for E? I wrote a naive solution and got AC within 1927ms.

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

    do u use floyed warshal?

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

      No, I just answered what the problem asks. if there are directed edges from vertex a to vertex b and from vertex b to vertex c, add a -> c to the graph if it does not exist yet.

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

        I did so too, but I got 4 test cases which are TLE. The intended solution is N times BFS/DFS.

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

          I used 2 vectors to maintain the incoming and outgoing vertices of every vertex. Stil, the time complexity is quite large. Not sure why it works My ugly code

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

          Same with me 4 TLE..

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

    Do DFS on each node $$$i$$$ and calculate the sum of the amount of node $$$j(j\neq i)$$$ which can be reached by node $$$i$$$. ​The time complexity is $$$O(n^2)$$$.

    Code
    → Reply
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Is G a dp problem ?

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

    Let us consider suffixes of $$$S_l, S_{l+1} \ldots S_r$$$ having length $$$m-pos+1$$$.

    Now you can have $$$dp$$$ such that $$$dp[pos][c][l][r]$$$ gives number of ways to put numbers in suffixes such that $$$S_l < S_{l+1} < \ldots < S_r$$$ if we only consider their suffixes of length $$$m-pos+1$$$ with the retsriction that $$$S_l[pos] \geq c$$$.

    So finally the answer is $$$dp[0]['0'][0][n-1]$$$ ($$$0-$$$ basex indexing)

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

According to my predictor, the difficulty (by Kenkoooo AtCoder Problems) of Ex is below 2400 again, which does not happen before ABC291. ​Finally, ABC is closer to a beginner contest.

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

    I hope there are more good counting problems on Ex instead of boring data structures

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

geometry :puke:

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

F is solvable with a single formula. Let us assume the two sides are $$$l$$$ and $$$w$$$, and $$$l \le w$$$. Then the answer is $$$\min ( \frac{2}{\sqrt{3}} l , \sqrt{l^2 + (2w-\sqrt{3}l)^2})$$$. It would be great practice to prove why this works.

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

    Wow. If you came up with that at a contest, that's pretty cool.

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

      Well, tbh the same question turned out to be on math.SE (And I wasn't surprised, fitting one basic shape into another is a very common problem in math). This ain't my fault though, lol

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

        i found that on SE but did it have the minimum with 2/root3 l i only found the second formula

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

          You are right, it didn't have the lefthand part in the minimum. But clearly, equilateral triangles with side length longer than $$$\frac{2}{\sqrt{3}}l$$$ can't fit in any such rectangle.

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

            i see now that does make sense i didnt really think after i found the formula i though it is precision issues thats why my soln aint passing

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

I think F is a maths problem instead of programming problem.

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

    I won't disagree that it's a maths problem. But, for those people who don't the maths formula (like me), the problem can be solved with binary search on the answer, so being specific, it's a programming problem for me.

    My submission.

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

can someone help me with my Ex solution

the general idea is same as the editorial, find the first position where the prefix sum is 0 or greater. but more bruteforcely i use range-add to mantain the prefix-sum, and do a binary search on tree with range-max.

currently it pass 34 cases and WA on other 20 cases. seems not completely wrong?

wa code

update: solved, forgot to push lazy tags when access the last prefix sum directly. ac code

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

For F task Math Exchange

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

In problem F, for the case where the equilateral triangle does not share an edge with the rectangle, did anyone else equate $$$\frac{a}{\cos(\theta)}$$$ and $$$\frac{b}{\cos(30^\circ - \theta)}$$$ and use the sum/difference of angles identity to get that $$$\theta = \tan^{-1}(\frac{b-\frac{\sqrt{3}}2 a}{\frac12 a})$$$?

→ Reply
»
22 months ago, # |
  Vote: I like it -28 Vote: I do not like it

People on codeforces: Oh look this problem had appeared on this chinese website some years ago. MAKE THE CONTEST UNRATED.

People on atcoder: Solution to F(!) is one line easily found by a google search. ....

→ Reply