chokudai's blog

By chokudai, history, 12 months ago,

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!

• +19

 » 12 months ago, # | ← Rev. 2 →   0 How to solve problem E anyone please help me!.
•  » » 12 months ago, # ^ | ← Rev. 5 →   0 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 →   0 lol, bday moment: G is problem you prepared 5 years ago, Ex is $O(qlog^2n)$ passed in 500 ms,
 » 12 months ago, # |   +8 What is the intended solution for E? I wrote a naive solution and got AC within 1927ms.
•  » » 12 months ago, # ^ |   0 do u use floyed warshal?
•  » » » 12 months ago, # ^ |   +8 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, # ^ |   +3 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 →   0 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, # ^ |   0 Same with me 4 TLE..
•  » » 12 months ago, # ^ |   +3 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... int n,m,cnt,vis[N]; vectore[N]; void dfs(int x){ cnt+=vis[x]=1; for(int y:e[x]) if(!vis[y]) dfs(y); } ... for(int i=1;i<=n;i++) memset(vis,0,sizeof vis),dfs(i); cout<
•  » » » 12 months ago, # ^ |   0 Tks!
•  » » 12 months ago, # ^ |   0 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, # |   +8 Is G a dp problem ? Spoilerwith possible states [n, m, digit]
•  » » 12 months ago, # ^ | ← Rev. 3 →   +19 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, # |   +35 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, # ^ |   +13 I hope there are more good counting problems on Ex instead of boring data structures
 » 12 months ago, # |   +5 geometry :puke:
 » 12 months ago, # |   0 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, # ^ |   0 Wow. If you came up with that at a contest, that's pretty cool.
•  » » » 12 months ago, # ^ |   +8 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, # ^ |   0 i found that on SE but did it have the minimum with 2/root3 l i only found the second formula
•  » » » » » 12 months ago, # ^ |   0 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, # ^ |   0 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, # |   +4 I think F is a maths problem instead of programming problem.
•  » » 12 months ago, # ^ |   +14 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.
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 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, # ^ |   0 how u implemented check funcion can u brief it?
 » 12 months ago, # | ← Rev. 2 →   0 can someone help me with my Ex solutionthe 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 codeupdate: solved, forgot to push lazy tags when access the last prefix sum directly. ac code
 » 12 months ago, # | ← Rev. 2 →   0 For F task Math Exchange
 » 12 months ago, # |   0 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, # ^ |   0 seems to be mentioned in one user editiorial in japanese
 » 12 months ago, # |   -28 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. ....