We will hold AtCoder Beginner Contest 440.
- Contest URL: https://atcoder.jp/contests/abc440
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20260110T2100&p1=248
- Duration: 100 minutes
- Writer: kyopro_friends, sheyasutaka
- Tester: sounansya, cn449
- Rated range: ~ 1999
- The point values: 100-200-300-400-450-550-600
We are looking forward to your participation!
Hi,have a good time
Hope for short problem statement like the post!
Good luck!!!
Enough "Good luck" — newbie here, ABC all ACed!
Well,A,B,C question of ABC!
Why can't I get into Atcoder Website? Locating in China
Please into atcoder.jp。 Please check your network.
Problem C was too hard for me. I felt D was easier than C.
can i get some hints for D ?
i used some binary searches
i also thought about that but wt to do if we encounter a mid which is already in array
start from the first number greater than or equal to a and count how many numbers are between a and mid in the array. i think by this way, you don’t need to check whether mid itself exists
Think this way.
First count how many no of elements are missing from the array which are less than X. Now add that to current y let say this as target and do binary search on the elements and see the missing no of numbers till the mid is equal to target.
If you have a habit of solving any problem by breaking the problem into lot of cases, you may just see the case breakdown of this submission, and try to fill the body of each case yourself.
My submission for D
F,G too hard for me...
https://cdn.luogu.com.cn/upload/image_hosting/0ij5agr1.png
Too hard for me.
CDEF is all not easy.
Maybe I can't make my rating higher.
I took almost whole contest just to solve C and D 😭..., D too hard to me at implementation and C I don't know why but it just doesn't click at all initially, at first I thought that it might because of my brain fatigue or just that the thing are really more educational to me than usual this time and did sucker punch me 👊 👊 👊 in my thinking blind spot, but it seems like a handful of people also really did struggle at C too with the same mysterious reason
I have solved D after almost 55 mins.
But still I'm struggling to understand problem C.
How did you reach Specialist and close to Expert? D was a very easy binary search. Maybe you should practice DS problems.
OK,I know.I will practice DS problems.
I am not good
POV:me after fumble hard with C and D
meeeee toooooooooo
How to solve $$$E$$$?
Crying my eyes out , I solved A and B in a flash, but then C totally stumped me—by the time I finished it, I only had 10 minutes left for D and didn’t even get to finish it.
While giving contest In C problem I was trying to find optimal X and tried brute-force first to check if I can find any pattern and found that the values to be some bi-tonic function is there any way to find the optimal X ??
Just me over here AC-ing the problem with a prefix sum while everyone else was stuck on ternary search.Haha
I promise I won't laugh at anyone.
It's just filling W positions and leaving W positions empty, repeating over and over!
But......POV: Me who was just crying my eyes out )goto( Me dying of laughter after seeing my rating jump from 47 to 135.
I thought this E was easy but for some reason I didn't find any easy solution.
At first I thought about this technique Fracturing Search, which seems to be the actual way to solve, but the standard way: do a DFS where each node is a vector with 50 integers and there is 50 possible next states was giving TLE + MLE
So I saw that from (x, 0, 0, ..., 0) we can reach any state in a unique way if we allow the only move to be from the first element to some element in the right or equal the last element, reducing the vector from 50 integers to only 3: the value of the sum, the current rightmost element and the value of the first element (because we can't move more than x elements to the right) Submission
Using the same Idea we can solve this problem K Subset Sums II, you just need to find a way to make a new set from the current set in a unique way and break early if the "priority queue" is big enough
In fact,a vector with 50 integers can also work,and you should create a map to record the visited nodes.
https://atcoder.jp/contests/abc440/submissions/72365358
this solution is easier to think of.
thank you so much , your solution is very much intuitive
A great ABC round! G's implement is bit too complicated for a 100-minute-contest, but also a good problem.
gogogo!
I don't know what's wrong with my solution of problem F.
my submission
Can anyone give me a hack?Thank you very much!
Problem C was tough, but I still ACed it though. Kinda felt D was easier tbh.
I should have checked Problem D first!
Why I think F is easier than E? I spent about an hour on E, but I didn't solve it. When I saw Problem F, it took me only a short time to solve it.
My solution for C:
[i2, i1]when incremented by x will always have remainders < W after mod 2W[i2, i1]when incremented by x will always have remainders < W after mod 2WTherefore, the solution is - Find the sum of all combination of subarrays i_a for 0 <= a < 2W - Return the min ans
Edge cases - n < W: Then we have an index range:
[W, 2*W - 1]of size W whose sum = 0 => min = 0 => ans = 0well done
well done
well done