chokudai's blog

By chokudai, history, 12 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

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve problem E anyone please help me!.

  • »
    »
    12 months ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    So, if we see that question says if there exists an edge from a to b and from b to c, then there must exist an edge from a to c. That is, if there exists a node which is reachable from the other node via a minimum of 2 steps, then we should connect a direct edge between two. I used BFS starting from each of the nodes as source. And then everytime you update the shortest distance during BFS, you check if the distance of the node from the source ==2. If the minimum distance turns out to be 2, means you need to add an edge from the source to that node. So, change the distance from 2 to 1 instead.

»
12 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,

»
12 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.

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

    do u use floyed warshal?

    • »
      »
      »
      12 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.

      • »
        »
        »
        »
        12 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.

        • »
          »
          »
          »
          »
          12 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

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

          Same with me 4 TLE..

  • »
    »
    12 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did BFS for every vertex and checked the other vertices. If the vertex is reachable from source and its distance is greater than 1 then add that to the answer. I hope that it makes sense

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Is G a dp problem ?

Spoiler
  • »
    »
    12 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)

»
12 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.

  • »
    »
    12 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

»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

geometry :puke:

»
12 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.

  • »
    »
    12 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.

    • »
      »
      »
      12 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

      • »
        »
        »
        »
        12 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

        • »
          »
          »
          »
          »
          12 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.

          • »
            »
            »
            »
            »
            »
            12 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

»
12 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    12 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.

    • »
      »
      »
      12 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      does binary search make it a programming problem? Your checker function still uses a lot of geometry. I bet the binary search idea was obvious, but having to check if the triangle fits is still a lot of geometry.

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

      how u implemented check funcion can u brief it?

»
12 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

»
12 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

For F task Math Exchange

»
12 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})$$$?

»
12 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. ....