Блог пользователя chokudai

Автор chokudai, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

Is G a dp problem ?

Spoiler
  • »
    »
    4 года назад, скрыть # ^ |
    ← 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 \lt S_{l+1} \lt \ldots \lt 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)

»
4 года назад, скрыть # |
 
Проголосовать: нравится +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.

»
4 года назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

geometry :puke:

»
4 года назад, скрыть # |
 
Проголосовать: нравится 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.

»
4 года назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

For F task Math Exchange

»
4 года назад, скрыть # |
 
Проголосовать: нравится 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})$$$?

»
4 года назад, скрыть # |
 
Проголосовать: нравится -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. ....