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

- Contest URL: https://atcoder.jp/contests/abc361
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240706T2100&p1=248
- Duration: 100 minutes
- Writer: physics0523, kyopro_friends, sotanishy
- Tester: yuto1115, cn449
- Rated range: ~ 1999
- The point values: 100-250-250-425-500-500-600

We are looking forward to your participation!

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.

Aged like milk

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

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

GL & HF

Hope E.

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

Are there any Chinese?

Here.

Here

Edit: Guys why the downvotes??

Here

Here

Hnist

here

qpqp

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

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.

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

this

I think problem F is almost the same (or an eaiser version) as this one https://mirror.codeforces.com/contest/955/problem/C , and you can check the editorial of that contest, https://mirror.codeforces.com/blog/entry/58547

I was lucky because I just solved this problem at codeforces several weeks ago, when I took a virtual participation of that contest.

Solving as many problems as possible is really important, and you will benefit from it sooner or later!

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

me too, can you help me with this submission (2 testcases only): https://atcoder.jp/contests/abc361/submissions/55314240

The function pow() in cmath header is not overflow safe (it can cause overflows), so better use a manual powering function.

This modified code of yours now works in 1ms ! :)

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

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)

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

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.

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.

This contest was easier than usual, hmmm?

Oh my god

There is an original problem

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

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

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

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

D cooked me ,time to focus on implementation

how to solve d?

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?

could you please explain ?? with your code ?

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 intervalsUnable to parse markup [type=CF_MATHJAX]

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.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('.');

}

return 0; } edit: i got my mistake

how to do f?

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

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.

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

What is wrong with this solution in C?

For this testcase

Spoiler`k=3`

and arr=`1 3 8 100 101 102`

your code gives`93`

, but answer is`2`

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

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

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

Solved ABCF, D and E were harder than F

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

Yes it is.

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

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

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.

can u explain how to count squares, cubes, a^4,.. a^k with kth root ??

The amount of k-th powers from 1 to N is floor(N^(1/k)).

Count of a^k from 1 to n is a^(1/k). You can calculate kth root using binary search, it's a pretty standard problem you can google it. Take care of the edge case when a^k exceeds long long range. Here's a link to my submission.

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

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?

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.

Solved ABCD，problem B is funny

how to solve D ?

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

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

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"

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

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.

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 ?

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.

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

F Brute Force

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

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.

E is this problem

Isn't it F?

Oops, I meant F

hey guys. how to solve F?

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 codethanks! I still don't understand why your solution works. (the inclusion-exclusion part). Can you prove that you're not overcounting (or undercounting) anything?

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)

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

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

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

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

A-800 B-1000 C-1000 D-1700 E-1700 F-1900 G-2400

Where did you get them?

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

Probelm: E I dont know why is this failing for 7 test cases. Can anyone please help...