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!
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)$$$.
Tks!
Is G a dp problem ?
with 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.
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 code
For 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. ....