We will hold AtCoder Beginner Contest 343.

- Contest URL: https://atcoder.jp/contests/abc343
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240302T2100&p1=248
- Duration: 100 minutes
- Writer: yuto1115, cn449, evima, leaf1415
- Tester: Nyaan, math957963
- Rated range: ~ 1999
- The point values: 100-150-250-400-475-525-600

We are looking forward to your participation!

I hope good luck to everyone!

Did I say something bad? Just downwoting for no reason

Hope to solve A,B,C,D

I hope everyone enjoyed testing this round a lot!

Hope to solve A,B,C,D!

Hope to solve A,B,C,D,E!

I hope as you

GL,HF! ys,qd!

I hope us all solve the A,B,C,D at least,and hope me solve the E even the F .

ABC 343 ......

Looks like questions will involve palindromes?

true.

and $$$7\ast 7\ast 7$$$

Good Lucky

Are there any Chinese? (I'm not good at English)

Why this code is getting TLE for task F

What are those 2 test cases in problem E ??

there were many WA's in Problem E.

No idea. I too want to know.

You cannot fixate the first cube to be in (0,0,0) and require that both of the other 2 have positive coordinates. The symmetry is wrong. Imagine a cube1 in the middle, cube 2 with positive y and positive z and cube 3 with negative y and positive z. Here are the cases for which your solutions should fail:

Test casesE is the most garbage problem I've ever had the misfortune of attempting

is it simulation ? how to solve it ?

Notice that we can fix the first point to be (0,0,0) without loss of generality. Now, for the second and third points, we can brute upto (7,7,7) and (14,14,14) respectively. For some triplet of points, we can check the answer in O(1) by taking the intersecting cuboids and inclusion exclusion. Atleast that's what I did. I get wa on two testcases and cannot fix it no matter what I do ;-;

try fixing the first point at (7,7,7) , doing this got me AC.

Sounds like a skill issue

Ape has no skill, only issues

Can anyone tell me why this $$$O(n\log^2 n)$$$ solution cannot pass F?

https://atcoder.jp/contests/abc343/submissions/50837622

I guess the time limit is tight. I first wrote a nlog^2n solution that didn't pass then I switched to nlogn by merging two sorted lists each time I merge two nodes. My submission

G is the same as this task.

But the data range of that task is smaller.

Problem

Gis a direct application of a standard technique and CF1200E: Compress Words.I've added hints and thought process for this problem on CF Step

Can someone please tell me what is wrong with my solution to Problem F? I get the TLE part, but not the WA.

JasonQin is a cheater. He asked me solutions during the contest.

For problem E,is there any special conditions that I should take into consideration? I got 24/26 AC and it drove me crazy。

my solution

Search the 3rd cube within [-7, 14]

I'll try, thanks a lot.

i searched from 0 23 for both cubes still WA

maybe it's the algorithm?

yes it got AC

same i was also stuck there my solution https://atcoder.jp/contests/abc343/submissions/50843371

You cannot fixate the first cube to be in (0,0,0) and require that both of the other 2 have positive coordinates. The symmetry is wrong. Here are the cases for which your solutions should fail:

Test casesWhy though? Isn't every symmetry which is possible using negative co-ordinates possible wrt the second cube which we assign?

No. That is an interesting fact. It is not intuitive for me either. If it was 2 cubes in total instead of 3, it would be fine.

I wonder if for 3 squares, you would need negative number, but Im not sure either.

If the cubes given by $$$C(a_i,b_i,c_i)$$$ satisfy $$$a_1<a_2<a_3$$$, $$$b_2<b_3<b_1$$$ and $$$c_3<c_1<c_2$$$, then we cannot get them in the same octant (with some vertex as the origin).

This is my solution for F.Luckily i didn't got tle.

Codehttps://atcoder.jp/contests/abc343/submissions/50838129

Can anyone Please give me the Solution of Problem-F — Second Largest Query ...

I use segment tree. You can maintain [max, sec_max, cnt_max, cnt_sec_max] in each node. Then it's just if-else case working in your propagation function.

I try to find point B and C in [0,14], but I got wrong answer on 04_killer2_00.txt and 04_killer2_00.txt. Who can tell me why :(

Problem E

You cannot fixate the first cube to be in (0,0,0) and require that both of the other 2 have positive coordinates. The symmetry is wrong. Here are the cases for which your solutions should fail:

Test casesCould you please tell me the answer for one of these testcase?

Its Yes for all of them. Just take the solution from someone in contest if you want to see. Lazy people...

Thinks.

F can be solve even if we need to find the number of occurrences of the k-th maximum.

If

`k <= 20`

, we can still used Segment TreeIf

`k <= n`

, simple 3D Mo does the task: CodeCan you explain

`get_ans()`

function in your code? I used`map<value, occurrence_num>`

to track the occurrence of all elements inside [L:R] then get the second largest value by`std::next(map.begin())`

but got TLE.It is a well-known trick. We use additional sqrt-decomposition to find the number of occurrences of x (

`CNT`

array).You have a problem: you are changing

`cnt`

array during 3D Mo (you use`cnt`

to maintain a set of current elements). And you need to know the k-th minimum of the current set of numbers. We want to modify`cnt`

in O(1) and get k-th minimum in O(sqrt(n)). The number of`modify`

queries is O(n^5/3) and the number of`get`

queries is O(q) — we call`get`

exactly once for each query.We can perform these queries in required time. Divide array into blocks size of

`sqrt(n)`

. For each block we maintain the number of different elements in it. Modify is trivial. To get k-th minimum, we need to find a prefix of blocks with >= k different elements, and then find the k-th minimum in the last of these blocks.I got it. Thank you.

$$$O(n\sqrt{n})$$$ passes in 500 ms in F.

How do you remove log factor in sqrt decomp? I tried but could not do it without map.

Why do you need a map? I just stored the maximum, second maximum, and the frequencies of these two for each window.

Lmao I am so dumb. I stored frequencies of all elements in map to mage updates O(logN), instead of making the update O(segment size). Thanks.

My submission I am storing maximum and second maximum using sqrt decomposition . But I am getting wrong answer. Can you pls check what is wrong with it ?

can anyone help me point out why my solution for problem C fails on testcase17.txt https://atcoder.jp/contests/abc343/submissions/50848352

and my solution for problem D only fails on the last testcase: https://atcoder.jp/contests/abc343/submissions/50851607

edit: found the cause for WA in problem D, integer overflow. Idk cause for problem C still

This is the only test point that I failed.

Just avoid using float/double unless you

absolutelyhave to.Your code is AC without the

`cbrt(n)`

: submissionsame as you problem

atcoder compile use below args

g++ --std=c++20 -O3

testcase17 will output 10662526601

I have one question to ask: Do Atcoder encourages participants to use Surfing and Searching Internet for solution? In today's problem E editorial's video, it encouraged to use ChatGPT to convert a python written code to a C++ version. Doesn't it break the fairplay and similar to cheating? (As in almost every official contest, it's punishable to surf and search internet during contest)

Can somebody help me with problem D? I know understand/know why i am getting TLE

It seems like your code is $$$O(n^2)$$$.

This is my solution:

Because of the large value range of the scores, we first discretize each person's score using

`unordered_map`

. Then we use buckets to count each person's score, and`bitset`

to maintain whether the score occurs or not, and just output the number of 1's in`bitset`

.Just like this(code in C++):

520ms

I have a way to solve problem use $$$O(n \sqrt n \log n)$$$ .(My English is quite bad , don't mind)

First,divide the array into $$$\sqrt n$$$ blocks.For each block ,we give it a

`map<int,int>`

it means that number x appear map[x] times in the block.A change for`A[x]`

only need $$$\log n$$$ time.So,We can find the Largest number by

`auto it = map.end();it--;`

`it`

is a`pair<int,int>`

that the first value is the largest number and it's appear count is the second value.For the second large number,we can use the same way and the only difference is to`it--`

2 times.(Note: there maybe only 1 value that`map.size()=1`

,so we should have a special decision.For each query,We can record the max and the 2nd.For block which is all in the query range,We should get the max and 2nd (only this two can change our recording) by following the above method.It take $$$O(\sqrt n \log n)$$$ time.For other pos,We can record in brute force because the number of it will not be larger than $$$2\sqrt n$$$.

My code is here:Code

My first code gives ACx31, WAx1 on Problem C.

I thought of enumerating from $$$\sqrt[3]{n}$$$ to $$$1$$$ and checking if its cube is a palindrome.

While my second solution gots AC: (pre-calculating palindromic cube number and do binary search)

What happened? I think two solutions are the same.

The first solution uses double (

`cbrt`

). Try removing it.can someone please tell expected rating of E and F que according to codeforces rating system??

can anyone prove why for problem E

the solution that first cube placed at (0,0,0)

second cube from 0->7 and third cube from 0->14 fails.

i am trying to visualize the placement of 3 cubes not possible from this kind of arrangement, but i am not able to find any such placement.

Check This submission. Second cube from 0->14 and first from 0->7. and the test cases doesn't fail.

йеша

for 1st problem: WRONG ANSWER

i submitted this code

package main

import "fmt"

func main(){ var a, b int fmt.Scan(&a, &b) if a+b == 0 { fmt.Println((a+b) + 1) } else if a+b <= 9 { fmt.Println((a+b) — (b + 1)) } }

logically its correct but don't what are 2 test cases my test case fails

please can someone see and review it.