We will hold AtCoder Beginner Contest 356.

- Contest URL: https://atcoder.jp/contests/abc356
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240601T2100&p1=248
- Duration: 100 minutes
- Writer: physics0523, kyopro_friends, nok0, Aus21
- Tester: MMNMM, nok0
- Rated range: ~ 1999
- The point values: 100-150-300-400-475-525-575

We are looking forward to your participation!

vERY gOOd AtcodeR,making mY cOdE SpIn.

有中国人吗？

Yes, but please communicate in English(请使用英语对话).

Yes, but please communicate in English(请使用英语对话).

当然有 but,please speak Enlish and I don't know why we should speak Enlish

Because it is easy to understand and learn :)

有

Please communicate in English.I'm sorry to vote down it.

How to change my name?

You can only change your name once in the end of a year.

UPD:I forget that you can change your name infinitely in at most 7 days after you registered a new account.

is this hard?

Yes.

i can only answer the first problem, lol. i'm stuck at the 2nd and the 3rd one. is the 2nd problem use dynamic programming?

Please discuss after contest

I can answer the first and the second problems.But I have no time to answer the third problem.

I know the first, second, third, fourth, and fifth questions. The competition has ended, and I definitely have time to answer them for you, but I'm going to sleep. You can check my submission records. My name is Littlesnake, and I wish you good luck, buddy.

second：

thank you!

You are right. But G is only 575 pts?

Hope everyone to have fun! And I hope a positive delta.I've already got negative deltas for a long time(only 4 probs)...

Hope for a funny and relaxing contest on International Children's Day.

International Children's Day is on November 20th to commemorate the Declaration of the Rights of the Child by the United National General Assembly on November 20th, 1959.

June 1st is celebrated as Children's Day primarily in communist and post-communist countries. The date was arbitrarily selected by the Women's International Democratic Federation in Moscow on November 4th, 1949.

The United Nations has more authority in setting up international holidays.

You may right, but lovely_cyc is Chinese.

That doesn't magically transform "Chinese Children's Day" into the "International Children's Day".

Happy Children's Day!Good luck.

Happy Children's day!

My post contest discussion stream for A-F problems

Interesting problems, this was a bit tougher than 355. My second ABC and it feels so much more diverse and balanced than recent CF rounds, great job.

Sadly rounding down in E ruins such a beautiful solution:

Couldn't find fix for it.

Why O(max(a) * log(max(a))) gives TLE in E?

My O(max(a) * log(max(a))) submission passes for E, maybe you didn't remove duplicates from the array?

Damn, that's right. My god, I completely forgot about it

Can you tell me how to solve problem E?

Sorry, I totally forgot about it(( If you're still interested in solution, here's the link to the editorial: https://atcoder.jp/contests/abc356/editorial/10141

Whats the mistake in my code for problem-C ? Code

I think the problem is the logic you use to check if a key configuration is valid or not. For example, if popcount(i) < k you never increase ans. But consider for example the test case

1 1 1

1 1 x

i = 0 is a valid configuration here but popcount(i) < k.

ya i just removed the condition popcount(i) >= k.

Thank you

Why is today's G only worth 575 points? I think it is as hard as last round's G, which is 650 points. (and the statistics agrees with me too!)

AtCoder Beginner Contests always have one too few testers for an accurate difficulty perception.

What's the matter with my segment tree algorithm on problem E?

It can't even AC any of the examples.

Put it in spoiler dude

Can someone explain why my logics for C & D fail?

For C, I iterate over each possible subset and check if it does not contradict with the tests.

SpoilerFor D, I iterate over 1's in M, and count the number of 1's on i's position through k: 0->N. The counting can be done in O(1) since on i's position 0's and 1's are alternating like this: 01010101 (for bit 0) 00110011 (for bit 1) 00001111 (for bit 2) ...

SpoilerFor C, your code does not consider the possibility that there are no real keys (I made the same mistake). Consider this test case:

The answer is 1 but your code gives 0.

For D, I think there is an off by one error somewhere when you are calculating

`add`

. Consider this test case:The answer is 1 but your code gives 0.

Oh yes you’re right. Thank you, both problems passed now.

for E : How to find the remainder of the values which are greater than a[i] for every a[i] efficiently.

I don't think you can

So ideas along the lines of $$$\lfloor\frac{a}{b}\rfloor = \frac{a-a\%b}{b}$$$ don't work because it's hard to calculate the sum of $$$a\%b$$$ quickly

Here is an idea with the complexity of $$$O(\sum \limits_{i = 1}^n (a_i \sqrt{a_i}))$$$:

You should remember these two theorems:

For a fixed integer $$$n$$$, there is at most $$$O(\sqrt{n})$$$ different values of $$$\lfloor \frac{n}{i} \rfloor$$$.

For a fixed integer $$$n$$$, assume $$$l$$$ is the minimum value of $$$i$$$ such that $$$\lfloor \frac{n}{i} \rfloor = x$$$, then the maximum value of $$$i$$$ satisfies the condition is $$$\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$$$.

Then pre-calculate the times of occurences of each value, then use these theorems to create a simple method:

For each time, get an interval $$$[l, r]$$$ such that $$$\frac{n}{l} = \frac{n}{l + 1} = \cdots = \frac{n}{r}$$$, calculate the answer in $$$[l, r]$$$(it is easy), until $$$l > n$$$ where $$$n$$$ is the current value.

Problem F can be solved by dividing into sqrt(Q) blocks of queries :D, I love sqrt decomposition.

Or by love with multiple sets

Assume current set is $$$[1, 5, 10, 14, 19]$$$ and $$$K = 4$$$. Let's look at segments between each two consecutive elements: $$$[[1, 5], [5, 10], [10, 14], [14, 19]]$$$. Now lets leave only those, whose length is greater than $$$K$$$ and take only left points out of two: $$$[5, 14]$$$.

Assume, the query is $$$1$$$. We apply

`lower_bound`

to this set and get $$$14$$$. This is the right point in connected component, that we are looking for. Now use indexed_set to find its number in original set.To find left point in connected component use another set (Why C++ doesn't have

`xxx_bound`

to left direction...).I don't actually use indexed_set anymore as it won't help me a lot in offline contests (I can't use the extension library) but thanks for another way to solve the problem! I've also thought about getting the index first but I forgot about indexed sets hehe :D

Actually, I think it is a good idea to learn just this magic line, as it helps me quite often. I guess, the only another way to do it is by implementing cartesian tree by hands, which is far worse idea for offline contest.

the problem is that our offline judge (known as Themis) doesn't support extended libraries so maybe (just maybe) I can instead use a trie to store

I did something similar, but with 4 sets (set of current points, ordered_set of current points, set of points whose closest point on the left is at a distance > K, set of points whose closest point on the right is at a distance > K). Here's the submission. Tbh I was surprised by the low solve count.

Sadly, I entered contest 1 hour after the start and missed out on +100 delta :(.

Mo's algo and DSU, the one in the EDU section?

Modified Mo's algorithm to be exact.

why range based segment tree won't work for Problem F ?

Problem setter, I don't know who you are, but I love you, you are amazing! =)

I laughed so hard when I solved problem C and read the problem statement of D =))))

Problem A is very ez, but was so satisfying to solve with clean c++ std. Pure joy =))

Problem AHow to solve problem E. The editorial is too complex for me.

At first assume, that there are no repeating numbers.

First let's sort the array. Assume, we have following: $$$[1, 2, 4, 5]$$$. We are calculating following: $$$(2 / 1 + 4 / 1 + 5 / 1) + (4 / 2 + 5 / 2) + (5 / 4)$$$. Let's calculate it parenthesis by parenthesis.

Assume, current number is $$$x$$$. By dividing which numbers by $$$x$$$ we get $$$1$$$? Numbers $$$x, x+1, \dots, 2x - 1$$$. By dividing which numbers by $$$x$$$ we get $$$y$$$? Numbers $$$xy, xy + 1, \dots, (x+1)y - 1$$$. Let's instead of original array use array of occurences: $$$[1, 1, 0, 1, 1, 0, 0, 0, \dots]$$$, which means, there is one occurence of $$$1$$$, one occurence of $$$2$$$, zero occurences of $$$3$$$, etc. Let's build prefix sums $$$ps$$$ on this array. Now the required number is $$$ps[(x + 1)y] - ps[xy]$$$.

We need to iterate over all possible $$$y$$$. But aren't there too many of them? We don't need to have $$$xy > 10^6 = C$$$, because there will be only zeros in array of occurences. So $$$y \le \frac{C}{x}$$$. Number of iterations will be $$$\frac{C}{1} + \frac{C}{2} + \frac{C}{3} + \dots + \frac{C}{C} = C(\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{C})$$$. The expression in parenthesis is well-known. It is called

harmonic seriesand is approximately equal to $$$\ln(C)$$$. So if we simply iterate over all $$$x$$$ and $$$y$$$ up to $$$\frac{C}{x}$$$ it will be $$$C \cdot \ln(C)$$$ time.About repeating number. In straightforward implementation all pairs of repeated numbers will be calculated, but we need to calculate them left to right direction. To do it, we can simply subtract all extra pairs by $$$res -= \frac{cnt(cnt + 1)}{2}$$$.

I was thinking on sorting numbers in descending order and then for each number calculate how many numbers are in range >= x & < 2x, >= 2x & <3 x, .....

I was thinking to do this by binary search. Can it be done better?

We can leave the original sorted array. For each number $$$x$$$ in the array iterate on all $$$y$$$ and find corresponding segment $$$[xy, (x+y)y - 1]$$$ by binary search.

But we also need to not iterate on same value $$$x$$$ several times, if it has several occurences. We need to do it once and then multiply by the number of occurences and also add the binomial coefficient of number of ordered pairs of these repeated elements.

It is $$$C \cdot \ln(C) \cdot \log(n)$$$ and looks harder to implement.

Understood. Thanks!

If $$$ 1 \leq a_{i} \leq 10^9$$$, then how can we solve problem E?

Yes, create an array that holds the count of each number, and you can easily calculate the count of numbers between a and b using prefix sums.

Could you help me understand how sorting does not change the answer say our array is [2 10 10 10 1] then 2/1 pair will never come but in sorted array it does appear

Did you understand why the order of the array doesn't matter?

re read the quesn i read it wrong

yaa just got to know, silly me.

but in sorted array 1,2 will come which will have the same max and min.

MySolution Can anyone please tell me what is wrong in my solution for C — Keys? ;)

A lot of people (including me) are making the same mistake for C, consider this test case:

The answer is 1 but your code gives 0.

What is error in my C code : https://atcoder.jp/contests/abc356/submissions/54135408?

consider test:

Thanks!!

In F, I used DCP offline on unordered_maps

CodeExplanationAfter we found time intervals for every x when it belongs to S, we maintain DSU with rollbacks and current S. When we want to add x, we find first elements in S which are bigger and smaller than x. If the difference between them and x is lower or equal to K, we merge them in our DSU.

Atcoder should have a NO AI TEST

If you take a look at the fastest submissions of A,C,D,you'll find that they are apparently written by AI.By the way,this and this didn't delete the comment "Generated by OpenAI gpt-4o".(Laugh)

F using binary search and segment tree. For a x, we need to know the leftmost element having absolute different with element to it's left > k. In the same way we will find the rightmost element having absolute different with element to it's right > k. Now we have 2 indexes a and b. The answer will be no of element in the range [a, b] which are still part of S. Sorry for my bad English.

for e may someone tell me what is matter of my code?

In problem C, the following solution of mine got AC. I thought it would be a TLE. What I did is calculate for every combination using bitmask. In worse case it is O((2^N)*M*N)=O((2^15)*100*15)=49,152,000. Can someone please explain why is it not TLE?

my solution

$$$O(m2^n)+O(mn)$$$ solutions run in 1..5ms, yours is 45 so it seems quite consistent

Sorry I don't quite get it. Could you please elaborate little more?

a complete beginner here, where would one rate the difficulty of this challenge? This was my first CC at I could only crack the first two.

https://atcoder.jp/contests/abc356/submissions/54163403

Any idea why a simple functional implementation would give wrong answer rather than tle?

Where can one find the complete set of test cases for problem E for this contest?