We will hold AtCoder Beginner Contest 292.

- Contest URL: https://atcoder.jp/contests/abc292
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230304T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: m_99, Nyaan, physics0523, PCTprobability, yuto1115
- Tester: m_99, Nyaan, physics0523
- Rated range: ~ 1999

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

We are looking forward to your participation!

How to solve problem E anyone please help me!.

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.

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

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

do u use floyed warshal?

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.

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

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

Same with me 4 TLE..

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)$$$.

CodeTks!

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

Is G a dp problem ?

Spoilerwith possible states [n, m, digit]

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)

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.

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

geometry :puke:

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.

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

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

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

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.

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

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

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.

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.

how u implemented check funcion can u brief 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 codeFor F task Math Exchange

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

seems to be mentioned in one user editiorial in japanese

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