atcoder_official's blog

AtCoder Beginner Contest 400 Announcement
By atcoder_official, history, 18 months ago, In English

We will hold AtCoder Beginner Contest 400.

We are looking forward to your participation!

  • Vote: I like it
  • +47
  • Vote: I do not like it

Comments Comments (42)
| Write comment?
»
18 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Hope to become 1Dan in this round.

UPD: FINALLY, I DO IT!

→ Reply
»
18 months ago, hide # |
← Rev. 2  
Vote: I like it +13 Vote: I do not like it

Hope this contest will not be as shit as the last ABC.

===========================

update: very hard but is a good contest.

→ Reply
»
18 months ago, hide # |
 
Vote: I like it +15 Vote: I do not like it

ABC400 marks a historic point in AtCoder’s journey — 400 beginner contests, week after week! Massive respect to the AtCoder team and all the problem setters who made this possible. Looking forward to celebrating this one properly!

→ Reply
»
18 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

Wow! chokudai （高橋君） becomes the writer!

Congratulations!

→ Reply
»
18 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

ABC 4e2!

→ Reply
»
18 months ago, hide # |
← Rev. 2  
Vote: I like it +6 Vote: I do not like it

Congratulation to 400th ABC! Many problem is about number 400, too. lol.

→ Reply
»
18 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

jiangly wins!!!

→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

My problem E passed in 163 ms while running the test case 1 in my local device/ide took around 1600 ms. I used Spf based factorization

→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why does my Dijkstra solution TLE on 1 testcase ?

→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I need c answer ，it is a difficult to make it

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Binary search solution: 64571484

    The first intuition should be that you either iterate over $$$2^a$$$ or iterate over $$$b^2$$$. Iterating over $$$b^2$$$ takes too long since $$$b \le 10^9$$$, but iterating over $$$2^a$$$ is fast (only around 59 candidates). For each value of $$$2^a$$$, we need to find out how many values of $$$2^b$$$ are small enough to satisfy $$$2^a \cdot b^2 \le N$$$. We can just binary search over $$$b$$$, since for any $$$2^a \cdot b^2 \le N$$$, we also know that $$$2^a \cdot (b-1)^2 \le N$$$ (you can also just use sqrt instead of binary search). Also be careful not to overflow when doing calculations, you can replace potential overflowing statements like if (x*y > N) with if (x > N/y).

    After this, the only remaining issue is the fact that some numbers are over-counted (for example, 72 is counted as both $$$2^1 * 6^2$$$ and $$$2^3 * 3^2$$$). This is because in some cases, our $$$b^2$$$ value contains factors of 2, which could equivalently be moved to $$$2^a$$$ instead. We can just ignore all values of $$$b^2$$$ which contain factors of two, which are just the even values of $$$b$$$. If we have $$$x$$$ values of $$$b$$$ for which $$$2^a \cdot b^2 \le N$$$, then we have exactly $$$\lceil \frac{x}{2} \rceil$$$ odd values of $$$b$$$.

    → Reply
    • »
      »
      »
      18 months ago, hide # ^ |
       
      Vote: I like it +5 Vote: I do not like it

      Just want to add a little bit, it is not necessary to check $$$a = 1, 2, 3 ... 60$$$. Simply checking $$$a = 1$$$ and $$$a = 2$$$ is enough. This is because for odd value of $$$a$$$, $$$2^{a}b^{2}$$$ can be written as

      $$$2^{2n+1}b^{2} = 2^{1} * 2^{2n} b^{2} = 2^1 * (2^{n}b)^2$$$

      For even, it can be written as:

      $$$2^{2n}b^{2} = 2^2*2^{2n-2}b^{2} = 2^2*(2^{n-1}b)^2$$$
      → Reply
      • »
        »
        »
        »
        18 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        Oh wow that's smart, I guess I was thinking of moving the factors of $$$2^2$$$ to the left side, rather than the right.

        → Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice problems. Although for me personally C was harder than E. Similar statements, but in E all numbers can be straight up generated, while C requires a little bit of thinking. Enjoyed C, E and F.

→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

approach for E

got tle and could not optimise it

→ Reply
»
18 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Can someone explain to me what is wrong with my solution to problem C:

Solution

func main() {
	defer out.Flush()

	var n int64
	fmt.Fscan(in, &n)

	ans := int64(0)
	for i := int64(2); i <= n; i *= 2 {
		val := int64(math.Sqrt(float64(n / i)))
		ans += (val + 1) / 2
	}
	fmt.Fprintln(out, ans)
}

Passed almost all the test except for 4 test cases

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Even I got 4 cases wrong. same code almost https://atcoder.jp/contests/abc400/submissions/64549973

    → Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    sqrt is not reliable. At least for me, binary search gets AC while sqrt gets WA.

    → Reply
  • »
    »
    18 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it 0 Vote: I do not like it

    So here is some technical stuffs if you want to know why:

    • There is such a thing that is called "the maximum integer that can be precisely represented" by a floating-point number. For double (8-bit floating-point number), it is 2^53 — 1 (Smaller than 10^18). Some languages (Like JS) call this the "Max safe integer".

    • So you would need to switch to using long double (10-bit floating point number on GNU C++), which can represent integers precisely up to 2^64 — 1.

    → Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone please help me with my C submission https://atcoder.jp/contests/abc400/submissions/64549973

I counted all the perfect squares before N and the biggest power of 2 before N.

And then counted their number of combinations.

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    try using sqrtl

    → Reply
  • »
    »
    18 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +1 Vote: I do not like it

    So here is some technical stuffs if you want to know why:

    • There is such a thing that is called "the maximum integer that can be precisely represented" by a floating-point number. For double (8-bit floating-point number), it is 2^53 — 1 (Smaller than 10^18). Some languages (Like JS) call this the "Max safe integer".

    • So you would need to switch to using long double (10-bit floating point number on GNU C++), which can represent integers precisely up to 2^64 — 1. Which is also why using sqrtl works.

    But I would still suggest that you use binary search instead for this lol.

    → Reply
»
18 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

O(1) complexity solution for C：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long

void solve() {
    ll n;
    cin >> n;
    cout<<(ll)sqrt((long double)n/4) + (ll)sqrt((long double)n/2)<<endl;
}


int main() {
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
}
→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I solved D with dijkstra. Is it overkill or was that an intended solution?

→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

how to solve F?

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    First consider a regular array rather than a cyclic one. Each time we introduce a new number $$$C[i]$$$, we can give it a segment width of 1 and we pay $$$1+X[C[i]]$$$. We could also instead extend this segment to a previous occurrence of $$$C[i]$$$: if this previous occurrence is at index $$$j$$$ then we simply pay $$$i-j$$$ (with no X cost). However, if we do this, then any segments from $$$j+1$$$ to $$$i-1$$$ cannot extend outside of this range, and same for any segments from $$$0$$$ to $$$j-1$$$. We can maintain $$$dp[l][r]$$$ as the min cost of the subarray $$$C[l:r]$$$. If we're introducing a new number at index $$$r$$$ (currently with a segment width of 1), and we want to extend this segment to a previous occurrence of $$$C[r]$$$ at index $$$m$$$, then for all $$$l$$$ we can have $$$dp[l][r] = \min(dp[l][r], dp[l][m] + (r-m) + dp[m+1][r-1])$$$: the cost up until the previous occurrence, the cost of extending the segment, and the cost of the subarray inside of the extended segment. As an alternative, by not extending, we simply have $$$dp[l][r] = dp[l][r-1] + 1 + X[C[r]]$$$.

    To deal with the cyclic array, just set C = C+C, solve with the above method, and then select the best size-N window with $$$dp[i][i+N-1]$$$ in order to check all cyclic shifts.

    Solution: 64571967

    → Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Solve C in O(1): ~~~~~

include <bits/stdc++.h>

using namespace std;

define int long long

signed main() { int n;cin>>n; cout<<(long long)(sqrtl(n/2))+(long long)(sqrtl(n/4))<<endl; }

~~~~~

→ Reply
»
18 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

editorial for D?

→ Reply
»
17 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

In the editorial for problem F, when analyzing the recurrence for dp[l][r], the following case is discussed:

"Next, suppose that the last operation was performed against pieces l, l+1, ..., r−1. The sought cost is the minimum cost required to make each of the pieces l, l+1, ..., r−1 either color 0 or color C[l], plus r − l + X[C[l]]. (Note that piece l remains color C[l].)"

This corresponds to the case where the last operation is applied to the segment [l, r). My question is: Why do we only consider converting the segment [l, r) to either color 0 or the color C[l]? Wouldn't it make more sense to consider converting the segment to any color, not just C[l]? Imagine there's a large portion of the segment [l, r) that is already of some other color d, and the cost X[d] is very low. In that case, wouldn't it be better to convert the segment to color d, instead of being restricted to just 0 or C[l]? the editorial says: "Note that piece l remains color C[l]."

Why is it always optimal to leave piece l as color C[l]? Isn’t it possible that changing l to match the rest of the segment might lead to a lower cost overall?

I came across [user:cowmane]’s solution, and I found that approach more intuitive. But I want to understand why the editorial's version is still valid or even better.

→ Reply