atcoder_official's blog

AtCoder Beginner Contest 440 Announcement
By atcoder_official, history, 4 months ago, In English

We will hold AtCoder Beginner Contest 440.

We are looking forward to your participation!

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

»
4 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Hi,have a good time

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

Hope for short problem statement like the post!

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

Good luck!!!

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

Why can't I get into Atcoder Website? Locating in China

→ Reply
»
4 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Problem C was too hard for me. I felt D was easier than C.

→ Reply
»
4 months ago, hide # |
 
Vote: I like it -6 Vote: I do not like it

F,G too hard for me...

→ Reply
»
4 months ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

https://cdn.luogu.com.cn/upload/image_hosting/0ij5agr1.png

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

    Too hard for me.

    CDEF is all not easy.

    Maybe I can't make my rating higher.

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

      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

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

I am not good

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

How to solve $$$E$$$?

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

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.

→ Reply
»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like 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 ??

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

But......POV: Me who was just crying my eyes out )goto( Me dying of laughter after seeing my rating jump from 47 to 135.

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

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

→ Reply
»
4 months ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

A great ABC round! G's implement is bit too complicated for a 100-minute-contest, but also a good problem.

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

gogogo!

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

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!

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

Problem C was tough, but I still ACed it though. Kinda felt D was easier tbh.

I should have checked Problem D first!

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

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.

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

My solution for C:

  • Only consider 0 < x <= 2W (cause for x > 2W in equation of mod 2W it'll be decreased)
  • Finding 1: there's always an index i such that when incremented by x (x > 0), its remainder after being divided by 2W is < W
  • Finding 2:
    • consider a random i1, there's always a positive int x such that (i1 + x) = W — 1 mod 2W
    • For i2 = i1 — (W — 1) => (i2 + x) = 0 mod 2W
    • => [i2, i1] when incremented by x will always have remainders < W after mod 2W
  • Conclusion:
    • => All i of the same remainder as [i2, i1] when incremented by x will always have remainders < W after mod 2W
  • Now we'll name all the ranges of size W with the 1st element = a mod 2W Combination of subarrays i_a

Therefore, 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 = 0

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

well done

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

well done

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

well done

→ Reply