atcoder_official's blog

Denso Create Programming Contest 2024（AtCoder Beginner Contest 361） Announcement
By atcoder_official, history, 21 month(s) 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
  • +136
  • Vote: I do not like it

Comments Comments (56)
| Write comment?
»
21 month(s) ago, hide # |
 
Vote: I like it -105 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
»
21 month(s) ago, hide # |
 
Vote: I like it -33 Vote: I do not like it

Are there any Chinese?

→ Reply
»
21 month(s) ago, hide # |
 
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
  • »
    »
    21 month(s) ago, hide # ^ |
    ← 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
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
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
  • »
    »
    21 month(s) ago, hide # ^ |
    ← 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
    • »
      »
      »
      21 month(s) ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        21 month(s) ago, hide # ^ |
         
        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
    • »
      »
      »
      21 month(s) ago, hide # ^ |
       
      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
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This contest was easier than usual, hmmm?

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Oh my god

There is an original problem

→ Reply
»
21 month(s) ago, hide # |
← 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
  • »
    »
    21 month(s) ago, hide # ^ |
    ← 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
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

D cooked me ,time to focus on implementation

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

how to solve d?

→ Reply
  • »
    »
    21 month(s) ago, hide # ^ |
    ← 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
    • »
      »
      »
      21 month(s) ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      could you please explain ?? with your code ?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, hide # ^ |
        ← 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
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

how to do f?

→ Reply
  • »
    »
    21 month(s) ago, hide # ^ |
     
    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
»
21 month(s) ago, hide # |
 
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
  • »
    »
    21 month(s) ago, hide # ^ |
     
    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
»
21 month(s) ago, hide # |
 
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
  • »
    »
    21 month(s) ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Yes it is.

    → Reply
  • »
    »
    21 month(s) ago, hide # ^ |
     
    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
  • »
    »
    21 month(s) ago, hide # ^ |
     
    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 \lt =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
  • »
    »
    21 month(s) ago, hide # ^ |
     
    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
»
21 month(s) ago, hide # |
← 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
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Solved ABCD，problem B is funny

→ Reply
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
← 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
  • »
    »
    21 month(s) ago, hide # ^ |
    ← 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
    • »
      »
      »
      21 month(s) ago, hide # ^ |
      ← 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
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
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
  • »
    »
    21 month(s) ago, hide # ^ |
     
    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
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

hey guys. how to solve F?

→ Reply
  • »
    »
    21 month(s) ago, hide # ^ |
     
    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
    • »
      »
      »
      21 month(s) ago, hide # ^ |
       
      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
      • »
        »
        »
        »
        21 month(s) ago, hide # ^ |
         
        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
      • »
        »
        »
        »
        21 month(s) ago, hide # ^ |
         
        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
»
21 month(s) ago, hide # |
 
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
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply