atcoder_official's blog

OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397) Announcement
By atcoder_official, history, 14 months ago, In English

We will hold OMRON Corporation Programming Contest 2025 (AtCoder Beginner Contest 397).

We are looking forward to your participation!

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

Comments Comments (22)
| Write comment?
»
14 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I am sure we will have fun in this round ! GL&&HF!

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

hoping for a +ve delta

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

Anybody else getting 500 server error?

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

D is cancer.

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

    Unfortunately, I have to agree.

    Solving the quadratic equation in code is almost always boring.

    Although I dislike the particular problem, I still want to thank the authors for the contest.

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

      Not me getting accepted in $$$O(\sqrt{N})$$$ with this code:

      int64_t y{1}, x{2}, z{};
while (x != y && (z = x * x * x - y * y * y) != n) {
  if (z < n) {
    ++x;
  } else {
    ++y;
  }
}
if (x == y) {
  cout << -1 << '\n';
} else {
  cout << x << ' ' << y << '\n';
}
      → Reply
    • »
      »
      »
      14 months ago, hide # ^ |
      ← Rev. 4  
      Vote: I like it 0 Vote: I do not like it

      No need to solve the thing, just use $$$4*(x^2+xy+y^2)=3*(x+y)^2+(x-y)^2$$$

      Code (C++)
      → Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Problem C : CF DIV4 D but integers instead of char

Problem D : Similar to problem I authored

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

D >> E

I kept getting 5WA on D, would appreciate if someone point out what's wrong with my code. Basically, I rewirte x^3 — y^3 as (x — y) * (x ^ 2 + xy + y^2). Simply bruteforce every value of x — y from 1 to n ^ (1 / 3).

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

    It might be caused by an overflow when computing $$$delta$$$ or $$$y$$$. You also don't need to check for the solution y=(-3d-k)/6, since y has to be positive

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

      So I guess we don't need to compute delta to solve the problem.

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

the F problem be solved using decision monotonicity. Is there anyone who can prove this point, or is it wrong?

core code:

void solve(ll l, ll r, ll x, ll y) {
	if (l > r) return;
	int mid = (l + r) >> 1;
	ll mx = 0, w;
	for (ll i = max(x, mid + 1); i <= y && i < n; i++) {
		ll tmp = ask(1, mid) + ask(mid + 1, i) + ask(i + 1, n);
		if (tmp > mx) {
			mx = tmp;
			w = i;
		}
	}
	ans = max(ans, mx);
	solve(l, mid - 1, x, w);
	solve(mid + 1, r, w, y);
}

https://atcoder.jp/contests/abc397/submissions/63840457

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

    Let $$$ w(i,j) = diff(1,i) + diff(i+1,j) + diff(j+1,n) $$$. Then, to prove the quadrangle inequality: $$$ w(i,j) + w(i+1,j+1) \geq w(i,j+1) + w(i+1,j). $$$

    This transforms into: $$$ diff(1,i) + diff(i+1,j) + diff(j+1,n) + diff(1,i+1) + diff(i+2,j+1) + diff(j+1,n) \geq diff(1,i) + diff(i+1,j+1) + diff(j+2,n) + diff(1,i+1) + diff(i+2,j) + diff(j+1,n). $$$

    This simplifies to: $$$ diff(i+1,j) + diff(i+2,j+1) \geq diff(i+1,j+1) + diff(i+2,j). $$$

    This is easily provable.

    Proving the quadrangle inequality is equivalent to establishing decision monotonicity.

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

The problems are very nice and I solved till F for the first time.

→ Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it 
    #include <bits/stdc++.h>
using namespace std;
#define ll long long
ll cube(ll x) {
    return x * 1LL * x * 1LL * x;
}
bool isPerfectCube(ll y_cubed, ll &y_val) {
    if (y_cubed < 1) return false; 
    ll low = 0, high = 1000000; 
    while (low <= high) {
        ll mid = (low + high) / 2;
        ll mid_cubed = cube(mid);
        if (mid_cubed == y_cubed) {
            y_val = mid;
            return true;
        } else if (mid_cubed < y_cubed) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return false;
}

void solve() {
    ll n;
    cin >> n;
    ll x = -1, y = -1;
    for (ll i = 1; i <= 10000000; i++) {
        ll x_cubed = cube(i);
        ll y_cubed = x_cubed - n; 
        if (y_cubed > 0) { 
            ll y_val;
            if (isPerfectCube(y_cubed, y_val)) {
                x = i;
                y = y_val;
                break;
            }
        }
    }

    if (x != -1) {
        cout << x << " " << y << endl;
    } else {
        cout << "-1" << endl;
    }
}

""""""int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t;
    t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

    // can u pls help where i am doing wrong in problem d?

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

      You are computing x_cubed where x is going till 1e7, this might cause overflow. Also you are only iterating for x upto 1e7 but there is a chance that both x and y are of the order 1e8 and N is less than equal to 1e18.

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

G can be solved using PuLP in Python.

See link: https://atcoder.jp/contests/abc397/submissions/63854618

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

Anyone who used something like topology for E?

Code (C++)
→ Reply
»
14 months ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

I don't want to be impolite.but...isn't D more difficulty than E or F?

(I solved ABCEF in 65min then I spend 30min on D.)

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

    (English is NOT my native language; please excuse typing errors.)

    Well,I found another way to understand D without $$$x^3-y^3=(x-y)(x^2+xy+y^2)$$$ or solving the quadratic equation.

    Let $$$y=x-k(1\le k \lt x)$$$ because $$$N \gt 0$$$.

    Now $$$x^3-(x-k)^3=N$$$,which is equal to $$$3xk(x-k)=N-k^3$$$,so $$$x(x-k)=\frac{N-k^3}{3k}$$$.

    Notice that $$$x \gt k$$$ so $$$x-k \gt 0$$$,so we can use binary search to find $$$x$$$.

    $$$N-k^3 \gt 0$$$ because $$$x(x-k) \gt 0$$$,so we can enumerate all of $$$k\le ^3\sqrt{N}$$$ and find whether there is an $$$x$$$.

    Complexity $$$O(^3\sqrt{N}\log n)$$$.

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

Don't get the editorial of F. If last[arr[i]]==-1, you add 1 to all elements from 0 to i. Otherwise you add 1 to all elements from last[arr[i]] to i. Then dp[i] is max value in the range 0 to i. Finally you update the value at index i to be suml[i]. How is this computing the answer ? Can someone explain how is this working ?

→ Reply