atcoder_official's blog

Denso Create Programming Contest 2024（AtCoder Beginner Contest 361） Announcement
By atcoder_official, history, 3 days ago, In English

We will hold Denso Create Programming Contest 2024（AtCoder Beginner Contest 361）.

We are looking forward to your participation!

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

»
3 days ago, # |
  Vote: I like it -95 Vote: I do not like it

Contest Topic Predictions for ABC:

A will be brute force.

B,C and D will be a Graph/Segment Tree/Advanced DP Problem/BS on answers/Sweepline.

E,F and G will be advanced data structures, MST, ternary search, NP Hard and 3 SAT problem.

→ Reply
  • »
    »
    46 hours ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Aged like milk

    → Reply
»
2 days ago, # |
  Vote: I like it -38 Vote: I do not like it

Plz dont organise contest by Denso hereafter. Bring Back Suntory contests.

→ Reply
»
2 days ago, # |
← Rev. 3   Vote: I like it -15 Vote: I do not like it

If I still can't solve till I open problem D, I may really cry.

→ Reply
»
2 days ago, # |
  Vote: I like it -10 Vote: I do not like it

GL & HF

Hope E.

→ Reply
  • »
    »
    2 days ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    Hello, I'm a primary school student, too. I live in Dalian Development Zone!

    → Reply
»
2 days ago, # |
  Vote: I like it -33 Vote: I do not like it

Are there any Chinese?

→ Reply
»
2 days ago, # |
  Vote: I like it -23 Vote: I do not like it

qpqp

→ Reply
»
47 hours ago, # |
  Vote: I like it -16 Vote: I do not like it

I couldn't solve problem B any more! Because my maths is terrible, I couldn't imagine those cubiods' location!

→ Reply
  • »
    »
    46 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Disclaimer: contest is over now so we are allowed to discuss solutions.

    Define a boolean function $$$f(x_1, y_1, x_2, y_2)$$$ to be true if the ranges $$$(x1, y1)$$$ and $$$(x2, y2)$$$ intersect. (Take note of the open intervals).

    Then, the two cuboids intersect if and only if $$$f(a, d, g, j)$$$, $$$f(b, e, h, k)$$$ and $$$f(c, f, i, l)$$$ are all true.

    My (messy) solution. I find it funny how I solved the problems in the order A CDEF B.

    → Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Is F a known problem? I was sure I'd find code for it somewhere online but could only find a paper on it.

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

This solution for F gives WA for 2 test cases,can anyone help?

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a great contest, enjoyed all problems and this is my first time solving A-F. B was a bit annoying tho.

→ Reply
  • »
    »
    46 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Me too. I regretted skipping B because it added a lot of time to my penalty :(

    (I did the problems in the order A CDEF B)

    → Reply
    • »
      »
      »
      42 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      is this your alt acc,i mean reaching upto F and still a newbie doesnt make sense to me

      → Reply
      • »
        »
        »
        »
        29 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No, my accounts on both Codeforces and AtCoder are jatrophalouvre, but my accounts are very new (I created them around two weeks ago) so my ratings are not accurate yet.

        → Reply
    • »
      »
      »
      6 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      AtCoder penalty time is the maximum submission time, not their (weighted) sum. The order doesn't matter if you solve the same set of problems.

      → Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

This contest was easier than usual, hmmm?

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh my god

There is an original problem

→ Reply
»
46 hours ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

My logic for E was as follows: The optimal path will start from a leaf and end at another leaf. Let's say the two optimal leaves are a and b, and their LCA (lowest common ancestor is) c, then all the edges in the tree will be traversed twice except the ones between a and c, and b and c. Hence we want to maximise the sum of those edges.

For this I iterated over all the vertices assuming them as LCA and found out the maximum value of highest depth. See my code for more details: https://atcoder.jp/contests/abc361/submissions/55306890

But I'm getting Wrong Answer on 5 test cases. Can anyone help me find out the issue here?

Update: Found the error. I needed to use multiset instead of set

→ Reply
  • »
    »
    46 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    The answer can be calculated as each edge weight * 2 minus the weighted diameter of the tree

    → Reply
  • »
    »
    45 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My ideas was for each node i to find the maximum distance to some other node denoted by ans[i] . Now if I start from u, the answer will be 2 * ( sum of all edge weight ) — ans[u] . We need to return the minimum . JAVA : TLE C++ : AC

    → Reply
»
46 hours ago, # |
  Vote: I like it -10 Vote: I do not like it

B and C were bad, and I am surprised to see those many submissions on them. I really feel the dumbest.

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

D cooked me ,time to focus on implementation

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve d?

→ Reply
  • »
    »
    46 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    D is a brute force search problem. I did double-ended BFS. It is a bit overkill but I used this because I didn't want to TLE, although I've seen normal BFS work too.

    Edit: downvoters please explain?

    → Reply
    • »
      »
      »
      46 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you please explain ?? with your code ?

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

        I wrote a normal BFS solution as well. I will be using this code because it is easier to understand. However, the prerequisites are that you understand and know how to apply BFS algorithms. If not, a simple search will suffice.

        Starting with main(), we first cin>>n>>st>>te. To make our lives easier, we add ".." to the end of st and te. Now that we have initialized our start and goal states, we carry out bfs().

        Moving onto bfs(), the first line should be fairly obvious: if st==te then we clearly return 0. Otherwise, we start with some more initializing.

        unordered_map<string, int> d tracks the distance from st, i.e. d[s] is the minimal number of operations required to get from st to s. Then, we want to find d[te].

        unordered_map<string, bool> vis tracks whether we have already processed a string, i.e. if vis[s]=1, then we have already processed s, and we shall not process s again.

        queue<string> q is the standard BFS queue. Actually, all of these initializing things should make sense if you know BFS.

        The main idea of the BFS is that we start from a string u and brute force every string v that can be reached from u in 1 operation. To do this, we first add st to q, set d[st]=0 and vis[st]=1. These should be self-explanatory.

        Then, to find all strings v that can be reached from u in 1 operation, we first initialize an integer pos, which is the position of the gaps, i.e. $$$u[pos]=u[pos+1]='.'$$$. Now that we know the gaps, we brute force swapping every adjacent characters with $$$[pos, pos+1]$$$. We do this by looping from i=0 to i=u.size()-2. Note that we don't loop to i=u.size()-1, because then i+1 will be out of range of u. We need some additional if conditionals to ensure that the intervals $$$[i, i+1]$$$ and $$$[pos, pos+1]$$$ don't overlap.

        Then, to swap $$$[i, i+1]$$$ and $$$[pos, pos+1]$$$, simply taking swap(v[i], v[pos]) and swap(v[i+1], v[pos+1]) suffices. The rest are all standard BFS procedures.

        → Reply
        • »
          »
          »
          »
          »
          40 hours ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          hello can u help me in debugging my it's not working for 3rd test case int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; string s; cin>>s; string t; cin>>t; map<string ,int>mp; if(s==t){ cout<<0; } else{ s.push_back('.'); s.push_back('.'); t.push_back('.'); t.push_back('.');

          map<string ,int>vis;
multiset<pair<int ,pair<string ,int>>>mm;
mm.insert({0,{s,n}});
mp[s]=0;
vis[s]=1;
while(mm.size()!=0){
    auto vv=*mm.begin();
    int xx=vv.first;
    string sn=vv.second.first;
    int nn=vv.second.second;
    mm.erase(mm.begin());
    //mm.pop();
    vis[sn]=1;
    for(int i=0;i<=n;i++){
        if(i==nn){
            continue;
        }
        if(i==nn+1){
            continue;
        }
        if(i==nn-1){
            continue;
        }
        string s2=sn;
        swap(s2[i],s2[nn]);
        swap(s2[i+1],s2[nn+1]);
        if(vis[s2]==0){

            mm.insert({xx+1,{s2,i}});
            mp[s2]=xx+1;
            vis[s2]=1;

        }

    }
}
if(mp[t]==0){
    cout<<-1;
}
else{
    cout<<mp[t];
}

          }

          return 0; } edit: i got my mistake

          → Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

how to do f?

→ Reply
  • »
    »
    43 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Use principle of inclusion exclusion with prime exponents up to 60 (since 2^60>10^18).

    This is my solution: https://atcoder.jp/contests/abc361/submissions/55309609

    → Reply
  • »
    »
    42 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In C++ it is actually possible to just store every a^b with b>=3 in a set and check that stored value is not a square of some other number by finding an integer square root. Only caveat is to use binary search for finding an integer square root to avoid precision issues. Answer is int_sqrt(n) + set size.

    → Reply
»
46 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

luck for me,is can be ac! (problem D)

#include <bits/stdc++.h>
#define pii pair<int, int>
#define int long long
#define rep(i, j, n) for (int i = (int)(j); i <= (int)(n); i++)
#define endl '\n'
using namespace std;
const int Mod = 1e9 + 7;
inline int add(int a, const int &b){ a += b &mdash; Mod; a += (a>>31) & Mod; return a; }
inline void usub(int &a, const int &b){ a -= b; a += (a>>31) & Mod; }
inline int sub(int a, const int &b){ a -= b, a += (a>>31) & Mod; return a; }
inline void umul(int &a, const int &b){ a = (int)(1ll * a * b % Mod); }
inline int mul(const int &a, const int &b){ return (int)(1ll * a * b % Mod); }
int qpow(int b, int p){ int ret = 1; while(p){ if(p & 1) umul(ret, b); umul(b, b), p >>= 1; } return ret; }
// priority_queue<pii, vector<pii>, less<pii>> q;
char c[20],c1[20];
int n;
int aws=100000000000000000;
int vis[20];
bool j(){
	rep(i,1,n){
		if(c[i]!=c1[i]){
			return false;
		}
	}
	return true;
}
void dfs(int p,int lay){
	if(j()){
		aws=min(aws,lay);
	}
	if(lay>8){
		return;
	}
	rep(i,lay-1,n-1){
		if(c[i]!='.'&&c[i+1]!='.'&&vis[i]==0){
			swap(c[i],c[p]);
			swap(c[i+1],c[p+1]);
			vis[i]=1;
			dfs(i,lay+1);
			vis[i]=0;
			swap(c[i],c[p]);
			swap(c[i+1],c[p+1]);
		}
	}
}
void solve() {
	cin>>n;
	int ct1=0,ct2=0,ct3=0,ct4=0;
	rep(i,1,n){
		cin>>c[i];
		ct1+=(c[i]=='B');
		ct2+=(c[i]=='W');
	}
	rep(i,1,n){
		cin>>c1[i];
		ct3+=(c1[i]=='B');
		ct4+=(c1[i]=='W');
	}
	if(ct1==ct3&&ct2==ct4){
		n++;
		c[n]='.';
		c1[n]='.';
		n++;
		c[n]='.';
		c1[n]='.';
		dfs(n-1,0);
		cout<<(aws == 100000000000000000 ? -1:aws);
	}
	else{
		cout<<-1;
	}
}
int32_t main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// int t;
// cin >> t;
// while (t--){
	solve();
//}
	return 0;
}
//
→ Reply
»
46 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

What is wrong with this solution in C?

#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <iostream>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define all(x) x.begin(),x.end()
using namespace std;
void paveway(){
    long long n , k; cin >> n >> k; vector<long long> a(n); 
    long long mn = 10000000000 , mx = -10000000000;
    for(long long i = 0; i < n; i++) cin >> a[i];
    sort(all(a));
    if(!( k %  2)){
        for(ll i = (k / 2)-1; i < (n - (i + 1)); i++){
            mn = min(mn , a[i]);
            mx = max(mx , a[i]);
        }
        cout << mx - mn << endl ;
    }else{
        for(long long i = (k/2)+1;i < (n - ((k/2))); i++){
            mn = min(mn , a[i]);
            mx = max(mx , a[i]);
        }
        cout << mx - mn << endl;
    }
}
int main (){ 
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	long long t = 1;
	//long long t; cin >> t;
	for(;t--;)
	paveway();
return 0;
}
→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this time abc361 have a same problem with luogu(an oj in China)?

The same problem in luogu: https://www.luogu.com.cn/problem/P9118

There is a discuss in luogu recently: https://www.luogu.com.cn/discuss/845537

→ Reply
  • »
    »
    46 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Disappointing, I was pretty sure the problem wasn't original but couldn't find the solution for it using an english search engine.

    → Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem F is an original problem.A lot of people do it.

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved ABCF, D and E were harder than F

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Is F based on Mobius Function? I believe F is Inclusion-Exclusion, but could not figure out which values to include/exclude in time.

→ Reply
  • »
    »
    46 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes it is.

    → Reply
  • »
    »
    46 hours ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    You don't need any advanced knowledge for F. Just try to optimize the brute force. There is ~$$$10^6$$$ values of x where $$$b \geq 3$$$ so you can track those values in a set to avoid overcounting. For $$$b = 2$$$ binary search on the biggest square that is less or equal to $$$N$$$. My submission: https://atcoder.jp/contests/abc361/submissions/55297768

    → Reply
  • »
    »
    46 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It is kind of smart brute force. Firstly we will count the number of values such that $$$i^2<=N$$$ . After this, we have to count the cubes and higher power. For doing this we can just start a loop from $$$2$$$ till $$$\sqrt[3]{n}$$$ .

    We must take care to not overcount elements, for example $$$64$$$ which is both the square of 8 and the cube of 2

    → Reply
  • »
    »
    46 hours ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    You can do it using Inclusion-Exclusion too. You've to basically count all squares, cubes, a^4,.. a^k less than N. Iterate from highest power to lowest power and find those values (using kth root). Then for each power k you've to exclude calculated value of its multiples.

    → Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please help me with this: https://atcoder.jp/contests/abc361/submissions/55314240? I'm getting WA on two tests, even though my code passed for 1 and 1e18

→ Reply
»
46 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

There's an exactly same problem from the National Olympics in Informatics (Spring Contest, 2023) in China, even the samples are same (original sample #3->sample #1, original sample #4->sample #3). Is it a concidence?

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.luogu.com.cn/problem/P9118 You know that F is an known problem,but you don't know that this problem is a pro version of F.

→ Reply
»
46 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved ABCD，problem B is funny

→ Reply
»
46 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is the code for question B, only one test point did not pass. Can anyone provide me with a set of hack data?

#include <iostream>
#include <algorithm>
#include <cstring>
#include <sstream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <stack>

#define endl "\n"
typedef long long LL;

using std::cin;
using std::cout;
using std::getline;

using std::max;
using std::min;
using std::sort;

using std::vector;
using std::string;
using std::stringstream;
using std::queue;
using std::priority_queue;
using std::map;
using std::stack;

struct Node {
    int x, y, z;
};

vector<Node> pii;

int main() {
    int x, y, z, a, b, c;
    int xx, yy, zz, aa, bb, cc;
    cin >> x >> y >> z >> a >> b >> c;
    xx = x;
    yy = y;
    zz = z;
    aa = a;
    bb = b;
    cc = c;
    pii.push_back({x, y, z});
    pii.push_back({a, y, z});
    pii.push_back({x, y, c});
    pii.push_back({a, y, c});
    pii.push_back({a, b, c});
    pii.push_back({x, b, c});
    pii.push_back({x, b, z});
    pii.push_back({a, b, z});
    cin >> x >> y >> z >> a >> b >> c;
    pii.push_back({x, y, z});
    pii.push_back({a, y, z});
    pii.push_back({x, y, c});
    pii.push_back({a, y, c});
    pii.push_back({a, b, c});
    pii.push_back({x, b, c});
    pii.push_back({x, b, z});
    pii.push_back({a, b, z});
    bool ok = false;
    if (a == aa && b == bb && c == cc && x == xx && y == yy && z == zz) ok = true;
    int cccc = 0;
    for (int i = 0; i < 8; i ++) {
        Node now = pii[i];
        if (now.x > min(x, a) && now.x < max(x, a) && now.y > min(y, b) && now.y < max(y, b) && now.z > min(z, c) && now.z < max(z, c)) {
            ok = true; 
        }
    }
    if ((xx < a && yy < b && zz < c && aa >= a && bb >= b && cc >= c) || (x < aa && y < bb && z < cc && a >= aa && b >= bb && c >= cc)) ok = true;
    x = xx;
    y = yy;
    z = zz;
    a = aa;
    b = bb;
    c = cc;
    for (int i = 8; i < 16; i ++) {
        Node now = pii[i];
        if (now.x > min(x, a) && now.x < max(x, a) && now.y > min(y, b) && now.y < max(y, b) && now.z > min(z, c) && now.z < max(z, c)) {
            ok = true; 
        }
    }
    if (ok) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

/*

*/
→ Reply
»
46 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there an explanation as to why G isn't commonly included in official editorials?

→ Reply
»
46 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I noticed a strange behaviour in c++ today while writing code for problem D. When I use & sign before "it" in the code, the output is some gibberish like "��q{xU"

    ll n = 16;
    string s = "BBBWBWWWBBWWBW..";
    queue<pair<ll,string>>q;
    q.push({n,s});
    while(!q.empty()){
        ll sz = q.size();
        while(sz--){
            auto &it = q.front();
            q.pop();
            ll pos = it.first;
            string str = it.second;
            cout<<"str = "<<str<<endl;
        }
    }

But when I remove the & sign, I get the expected output "BBBWBWWWBBWWBW..". Can someone explain what is this and why is this happening ?

→ Reply
  • »
    »
    46 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You use & when you want a reference to the value. i.e. for (auto & i : v) i++; will increase all elements in a vector, while for(auto i : v) i++; will not affect the original vector. You are getting a reference to the front of your queue, then removing the front, so you may get some garbage because you're referencing something that doesn't exist.

    → Reply
    • »
      »
      »
      46 hours ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      What you are saying is true and I agree with you. However, this issue only happens when string length is >15. I tried for various lengths <=15 and it works in those cases. Do you have any explanation for that ?

      → Reply
»
45 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone could tell me the idea for G that would be great. I tried the following:

First, we clearly just want to find all enclosed areas. Let pair<int, int> f[i] denote the coordinates of the i-th stone. Then, we connect a (bidirectional) edge from $$$u$$$ to $$$v$$$ if |f[u].first-f[v].first|<=1 and |f[u].second-f[v].second|<=1. Then, an enclosed area is analogous to a cycle in this graph. If we have a cycle $$$a_1, a_2, \dots, a_n$$$ in this graph, we can calculate the number of lattice points enclosed by the polygon formed by f[a[1]], f[a[2]], ..., f[a[n]] by using Pick's Theorem. We can calculate the area using shoelace and "reverse engineer" the number of lattice points enclosed by the polygon using Pick's Theorem. Summation of this should give us the answer.

This, however, is giving WA. If anyone could correct me, that would be greatly appreciated.

→ Reply
»
45 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Lol, I didn't expect this to work, but F is brute force!

F Brute Force

→ Reply
»
44 hours ago, # |
  Vote: I like it +9 Vote: I do not like it

Many thanks to yuto1115 for sharing an amazing solution of G — Go Territory (*ˊᗜˋ*)/ᵗᑋᵃᐢᵏ ᵞᵒᵘ*

→ Reply
  • »
    »
    40 hours ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    I totally agree. During the contest I came up with the original idea (from another editorial) and failed to consider all cases properly. Actually, it took me nearly a dozen of submissions after the contest for all tests to be passed. I was wondering how so many people during the contest did it so fast and clean. After reading about yuto1115's approach I feel really stupid, but now I fully understand how this problem should have been solved during the contest. For sure, one of the most educational problems I've seen so far on AtCoder.

    → Reply
»
36 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

E is this problem

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

hey guys. how to solve F?

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    there is said to be a brute force solution, but i cannot really understand that. my solution is to use dp and inclusion-exclusion principle. first, we can ignore 1 as it is too special. then let f[x] be the number of integars between 1 and N that can be written as pow(p, x). we can calculate it with floor(pow(n, 1/x)) - 1 (you may need to implement bisection method to avoid precision problem with these cmath functions). but there is obviously some duplicated integars calculated. for example, 2^6 is in f[6] while also in f[3] as 4^3. to avoid this, you can substract all f[x*j] from f[x] where j are integars greater than 2. the reason is simple: we calculate an integar only in f[x] where x is the greatest possible. by doing this all f[x] we calculated includes no duplicated integars. we can get the sum of all f[x] as the answer. lastly dont forget the 1 we excluded previously. my code

    → Reply
    • »
      »
      »
      28 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thanks! I still don't understand why your solution works. (the inclusion-exclusion part). Can you prove that you're not overcounting (or undercounting) anything?

      → Reply
      • »
        »
        »
        »
        28 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if an integar x is going to be counted, it can be written as p^q, let assune a case where q is the greatest. in another word, if we decompose the prime factors of x, the gcd of all the index of the factors is q. now we can learn that for every integar x there exist an only q which is greatest possible. as 2^60 > 1e18, all the q of the integars we are counting is no greater than 60, so we can enumerate q from 60 to 2. for each m as a factor of q. m < q, x = p^q = (p^(q/m))^m. when we are calculating f[m], such x is also calculated in f[q], so we substract it. and m*j (j>=2) can enumerate all the integars that have a factor m and is greater than m. when m = q, in this case we will not substract f[q] from f[m] because m*j>m. therefore the f[m] remaining includes only x=p^m where m is the greatest and it will make the following recursion holds true. (please forgive my terrible wording as i am not a native english speaker)

        → Reply
        • »
          »
          »
          »
          »
          27 hours ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Thanks. It's a beautiful solution! though It took me a while to understand it

          → Reply
      • »
        »
        »
        »
        28 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        btw, a similar technique is also performed in this problem (although i think that is much harder)

        → Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I got 2 WA on F, i am not sure whether it is not the correct solution or it is just the precision problem.

#include<bits/stdc++.h>

long long n;
int mem[10000002];

long long qp(long long p, long long q) {
	long long r = 1, b = p;
	while (q) {
		if (q & 1) r = r * b;
		b = b * b;
		q >>= 1;
	}
	return r;
}

long long f(long long x) {
	if (x == 0) return 0;
	if (x <= 1e7) {
		if (mem[x]) return mem[x];
	}
	long long res = 0;
	for (int i = 2; i <= 61; i ++) {
		
		long long l = floor(pow((long double)x, (long double)1.0 / i) + 1e-9);
		res += l - f(l);
	}res ++;
	if (x <= 1e7) mem[x] = res;
	return res;
}

signed main(){
	std::ios::sync_with_stdio(0);
	std::cin.tie(0); std::cout.tie(0);
	mem[1] = 1;
	std::cin >> n;
	std::cout << f(n);
	return 0;
}
→ Reply
»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any way to know what would their CF rating be?

→ Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know why Atcoder promotes its contests within Codeforce

→ Reply