atcoder_official's blog

By atcoder_official, history, 5 months ago, In English

We will hold UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359).

We are looking forward to your participation!

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

»
5 months ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

atcoder is top 8 contributer now!

»
5 months ago, # |
  Vote: I like it +6 Vote: I do not like it

After many many exams in the school, many many students begin their AtCoder tours again :)

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

Idk how I passed C after 4 WAs, just did some +/- math. Idea was to move diagonally as much as possible and align the x coordinate or y coordinate with the target node.

Code
»
5 months ago, # |
  Vote: I like it +25 Vote: I do not like it

what the fck was C

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

    Idk man, I just figured some +/- math after moving diagonally as much as possible and aligning resultant x or y with target node. After that it was tricky to move in the same direction where I did some guessing.

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

    I felt like leaving the contest .

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there a simpler solution to G than Small to Large merging? Or did people just manage to implement that approach in like 5 mins @_@

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    small to large merging is simple ??

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    It's a classic euler tour + monostack problem.

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

    There are indeed simpler solutions, but small to large merging is also simple enough. It's only about 30 lines and 5 mins or so is enough to implement it (my solution in contest was small to large merging).

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

      Could you roughly explain your approach using small-to-large merging?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone please explain the idea behind the 3rd question import math a,b=map(int,input().split()) c,d=map(int,input().split()) t=math.ceil(1.5*abs(b-d))

if t<=abs(a-c) and t!=0: print(int(abs(a-c) -1.5*abs(b-d))//2 + abs(b-d)+1) else: a=abs(b-d) print(a) please explain me why my code is incorrect please

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

    you can try to move the initial and the end points to adjacent ones (where (x + y) mod 2 = 0) such that each one is still in its tile and then draft some examples

»
5 months ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

My solution for problem-D is to store last K characters as state. AC

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Great contest. D was a really good problem, wish I would've solved E a bit quicker though. Also, How to do C?

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

    Idea is to move diagonally as much as possible and then align target with the resultant x or y coordinate. Tricky part was to move in the same direction in x. In y its just that difference of y coordinates as height of tiles are 1.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how can we get atcoder contest testcase at which our solution got failed...

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody who found C,D tougher than E,F or just me?

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone can give hints on how to solve D?.

My approach to count all the possibilities such there is atleast 1 subarray of K length that is a palindrome and then the subtract that from 2^q and get the answer, but I couldn't calculate it properly(due to overcounting).

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

    bitmask dp

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

    Let $$$dp[i][m]$$$ (for $$$k - 1 \leq i \lt n$$$) represent the number of ways of constructing a good prefix of the first $$$i$$$ characters ending with mask $$$m$$$.

    For $$$i = k - 1$$$, this is fairly direct, check all $$$2^k$$$ possible masks and see if they work (are possible and don't contain any palindromes). If they do, set $$$dp[k - 1][m] = 1$$$, otherwise set it to $$$0$$$.

    Now notice that the masks for position $$$i$$$ and $$$i - 1$$$ share $$$k - 1$$$ characters. So for any $$$i \geq k$$$, we can check each of the $$$2^k$$$ masks again. If a mask $$$m$$$ is valid, we simply calculate $$$dp[i][m] = dp[i - 1][m'] + dp[i - 1][m' + 1]$$$ where $$$m'$$$ is $$$m$$$ with its highest ($$$(k - 1)$$$-th) bit disabled.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think problem B's statement could have been made a lot easier to understand.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My code failed for last three testcases in C.Can someone point out where the mistake lies?

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

"Can anyone explain C, please? I should have at least tried d, as I've spent so much time with C, actually, not so much time but significant time. I'm feeling bad about it now."

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D is good.

»
5 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

I used small to large in G. But I can't understand what's wrong in my solution. mp[v][c] contains two numbers: the number of vertices of color c in v's subtree and the total length of paths to them.

Code

UPD: submission

UPD2: I found issue, AC

»
5 months ago, # |
  Vote: I like it +63 Vote: I do not like it

If C has a million haters I'm one of them. If C has a hundred haters I'm one of them. If C has one hater it's me. If C has zero haters I have died. If the world is against C I am with the world, if the world is for C I am against the world.

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

    D E easier than C

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Tbh C was cute problem. I didn't like it either, but it's really simple and solution is pretty concise. I feel like CP turned into mindlessly rewriting same algos over and over, especially on AtCoder ABC. Problems like this humiliate you in a good way.

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

      I was helllbent on solving C, finally did and missed on other problems D,E,...

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

      I don't particularly enjoy writing math casework

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    I also don't like problems like this one. But since ABC is supposed to be educational, I try to make use of such problems. For example, I've learned the following lessons (in this particular order):

    1. Skip nasty non-standard grid problems whenever it's possible. Especially if there are problems with more points to get.

    2. Try to find out "simple observation" (as they will call it in editorial for sure) before considering shit tons of edge cases.

    3. Test your solution like crazy. After the first WA, write stress test immediately, don't wait for luck.

    4. Solving more and more similar problems make your more resistant and prepared to them.

    5. Competitive programming is 100% pain.

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

    If C has n haters ($$$ 3 \le n $$$) I'm one of them. If C has two haters that's you and me. If C has one hater I have AFOed. If the world is for C, I'm with you.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

E was stack and $$$\text{O(N)}$$$ ? (Asking cuz constraints had 2e5)

Code
»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So typical problem G. Maybe it will be better to swap some orders of the problem.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you guys just STOP making "greedy in grid" problems such as C plz? :(

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

how can we get atcoder contest testcase at which our solution got failed...

»
5 months ago, # |
  Vote: I like it +113 Vote: I do not like it

https://www.luogu.com.cn/problem/P7840

this is the original problem of F?

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

    Why ABC usually has an original problem?

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

    My code which get AC in AT also get AC in LG!

    But I suppose it wasn't on purpose, as there weren't many easy ideas:(

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

    But I think ABC is a good way to let us find the same problem so that get AC.

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

      so that get AC is wrong in grammar,you should modify it to be "so that you can get AC on the original problem."

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is same as F!

»
5 months ago, # |
Rev. 3   Vote: I like it +21 Vote: I do not like it

C was exactly same as https://codeforces.me/contest/1421/problem/D. Just consider the right point of tiles (moving between left and right didn't encounter any cost), and those right points forms the hexagon.

It can be solved via linear algebra, no need to go into greedy

»
5 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Problem F has appeared here previously : https://www.luogu.com.cn/problem/P7840

However, Luogu is a website that currently mainly used in China. So I think it is a coincidence. I only point out for notice.

Here is the translation by Copilot:

  • There are $$$n$$$ servers.
  • Each server has a busyness level denoted by $$$v_i$$$.
  • The servers are connected using $$$n−1$$$ network links.
  • Each server has a connection count $$$d_i$$$.

The total running time of the server network is given by the expression:

$$$ \sum_{i = 1}^n d_i^2 v_i $$$

The goal is to minimize this value.

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

    I think so.

    I wonder who finds this original problem?

»
5 months ago, # |
  Vote: I like it -29 Vote: I do not like it

Didn't Atcoder check for if there have been the same problem???

This problem from Luogu same as today's G.

And this problem is from the year 2021.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    It is a Chinese website and it only support Chinese... It is extremely difficult to check EVERY CP website and search whether there is a same problem. So It can be only coincidence. BTW it didn't cause any significant effect, because it is just an ABC contest.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      They do nothing wrong. Try not to be too aggressive.

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

        Is it hard to check weight? Inexplicably! Only a fool thinks so. The questions are exactly the same, and luogu is a great site for brushing up on questions, and the bottom line as a question writer is to not come up with exactly the same questions. Even though the questions are in Chinese, can't you learn Chinese? You can't read Chinese, can you? And ziyistudy is stating facts and you're defending a shit group of question writers. I think you are very wrong.

        Translated with www.DeepL.com/Translator (free version)

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

    I don't think the testers can find this problem. It's from China.

    However, the impact is not significant, as even Chinese people find it difficult to detect.

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

      find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect. find it easy to detect.

»
5 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Why inclusive-exclusive algorithm doesn't work in problem D?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    I'm stupid... How dare me apply inclusive-exclusive algorithm for n-k elements!!!! I thought n-k<=10....

»
5 months ago, # |
  Vote: I like it -13 Vote: I do not like it

Top 10 contribution!

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder how to prove that greedy algorithm is correct for problem F. Would anyone like to share your ideas? Thanks a lot.

»
5 months ago, # |
  Vote: I like it +11 Vote: I do not like it

I see some solutions using Small to Large technique, so I'd like to share 5 problems (in increasing order of difficulty) for someone who is not familiar with this topic and want to learn it.

Plain Small to Large

  1. Distinct Colors
  2. Confuzzle
  3. It is a Tree : Subtask 2

Small to Large + Advanced DP

  1. Count Paths
  2. Leaf Color

For problems from BOJ, either use Google Translate or add the problem to Vjudge and use the inbuilt translator option.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain Problem G ?