atcoder_official's blog

AtCoder Beginner Contest 343 Announcement
By atcoder_official, history, 9 months ago, In English

We will hold AtCoder Beginner Contest 343.

We are looking forward to your participation!

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

»
9 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I hope good luck to everyone!

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Did I say something bad? Just downwoting for no reason

    → Reply
»
9 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Hope to solve A,B,C,D

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope everyone enjoyed testing this round a lot!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to solve A,B,C,D!

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

ABC 343 ......

Looks like questions will involve palindromes?

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Lucky

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Why this code is getting TLE for task F

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

What are those 2 test cases in problem E ??

there were many WA's in Problem E.

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

    No idea. I too want to know.

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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 cases
    → Reply
»
9 months ago, # |
  Vote: I like it +53 Vote: I do not like it

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

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

    is it simulation ? how to solve it ?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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 ;-;

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

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

        → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Sounds like a skill issue

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

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

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

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

    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

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

G is the same as this task.

But the data range of that task is smaller.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem G is a direct application of a standard technique and CF1200E: Compress Words.

I've added hints and thought process for this problem on CF Step

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

    my solution

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

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

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

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

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 cases
    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

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

        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.

        → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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).

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

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

Code
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

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 :(

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Problem E

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

    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 cases
    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

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

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

        → Reply
»
9 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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 Tree

If k <= n, simple 3D Mo does the task: Code

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

    Can 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.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

        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.

        → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        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 ?

        → Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like 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

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

    This is the only test point that I failed.

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

    Just avoid using float/double unless you absolutely have to.

    Your code is AC without the cbrt(n): submission

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

    same as you problem

    atcoder compile use below args

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

    testcase17 will output 10662526601

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

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

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

    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++):

    #include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<unordered_map>
using namespace std;
unordered_map<long long,long long>Hash;
bitset<200010>bz;
long long scores[200010],sum[200010],Hash_cnt;
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	bz[0]=1;
	sum[0]=n;
	for(int i=1;i<=q;i++)
	{
		long long x,y;
		scanf("%lld%lld",&x,&y);
		sum[Hash[scores[x]]]--;
		if(sum[Hash[scores[x]]]==0) bz[Hash[scores[x]]]=0;
		scores[x]+=y;
		if(Hash[scores[x]]==0)
			Hash[scores[x]]=++Hash_cnt;
		sum[Hash[scores[x]]]++;
		bz[Hash[scores[x]]]=1;
		printf("%lld\n",bz.count());
	}
}

    520ms

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
unsigned long long n,cub,tmp;
bool check(unsigned long long qaq)
{
	int a[30];
	int cnt = 0;
	while (qaq)
	{
		a[++cnt] = qaq % 10;
		qaq /= 10;
	}
	for (int i = 1,j = cnt;i <= j;i++,j--)
		if (a[i] != a[j]) return false;
	return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	cub = floor(cbrt(n));
	for (unsigned long long i = cub;i >= 1;i--)
	{
		tmp = i * i * i;
		if (check(tmp))
		{
			cout << tmp << '\n';
			return 0;
		}
	}
}

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

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
long long n,l,r,mid,ans,cnt1;
long long a[N];
long long tmp;
bool check(__int128_t qaq)
{
	long long a[30];
	int cnt = 0;
	while (qaq)
	{
		a[++cnt] = qaq % 10;
		qaq /= 10;
	}
	if (a[cnt] == 0) return false;
	for (int i = 1,j = cnt;i <= j;i++,j--)
		if (a[i] != a[j]) return false;
	return true;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	for (long long i = 1;i <= 1e6;i++)
		if (check(i * i * i)) a[++cnt1] = i * i * i;
	cin >> n;
	l = 1;
	r = cnt1;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		if (a[mid] <= n)
		{
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	cout << a[ans] << '\n';
}

What happened? I think two solutions are the same.

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

    The first solution uses double (cbrt). Try removing it.

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please tell expected rating of E and F que according to codeforces rating system??

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

йеша

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply