atcoder_official's blog

UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334) Announcement
By atcoder_official, history, 11 months ago, In English

We will hold UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334).

We are looking forward to your participation!

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

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

Are Japanese editorials for Beginner contests still translated just by using GPT-4 to English?

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

hope to solve ABCD.

good luck!

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

excited

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

Hope everyone has good grades！

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

Why this submission gives wrong answer for E? Any HELP is appreciated.

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

today,i fuc**ed up

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

A < D < B < C

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

Nice contest as usual, managed to solve 6 problems.

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

is $$$F$$$ dp?

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

Does anyone accepted G with Dynamic Connectivity?

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

I added hints for E — Christmas Color Grid 1 on CF Step

I created video editorial for F: Christmas Present 2. I also created 1D version so that you can submit $$$O(N^3)$$$, $$$O(N^2)$$$ and $$$O(N Log(N))$$$ solution.

Is this the right direction to approach G?

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

    Yeah, and the standard approach for checking articulation points gives you their exact count lol. I just built the graph and ran the cp-algo implementation on it.

    In that implementation, the number of times IS_CUTPOINT($$$v$$$) is called is the number of resulting components (except for the root where its actually “children — 1”).

    If you’re familiar with DFS tree, the intuition is pretty obvious, each child $$$v$$$ which doesn’t have a backedge that crosses over $$$v$$$ will be disconnected when $$$v$$$ is removed.

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

Is it intended that offline dynamic connectivity solutions receive TLE on problem G?

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

Solved A,B,D

D<B<<C

A- If conditions

B- Tricky implementation + Maths

D-Sorting+Binary Search+ Prefix Sum

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

Hardest B ever, lol. I spent around 1 hour for B but failed. D, E are quite trivial though.

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

The time is over right after solving E. Fuck

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

Why does this code get WA in E?

https://atcoder.jp/contests/abc334/submissions/48798560

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

    DSU is quite overkilled though

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

    line 101:

    ans+=yay+res;

    line 106:

    ans*lt(dv, mod-2, mod)%mod

    • res (number of components) can be upto $$$5 \cdot 10^5$$$

    • so ans can be upto $$$(5 \cdot 10^5)^2$$$.

    • meaning ans*lt(dv, mod-2, mod) can overflow 64-bit ints

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

Horrible contest. Problem B very to hard for this division and no editorial. What else ?

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

I solved F just because I saw this before (The problem called Mowing the Lawn in USACO 2011 Open Gold Group)...

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

Speedcoder........

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

Why and where does this code give WA for problem E? any help ?

My submission

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

    Can you please elaborate on the idea behind your submission? I have solved the problem, but apparently with a different approach.

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

      Yes sure, I actually gave ids through string concatenation of row and column index, after that I performed merging of grid cells which are green, now so i will have components of green through dsu, then on every red cell I will check it's neighbor and identify what are the different component numbers in all 4 directions, then just adding the components we can achieve for every red cell to green. Then dividing by number of initial red cells which have equal probable to choose.

      → Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it 
    s += to_string(r) + to_string(c);

    seems to be wrong. Row 1 Column 11 has the same string as Row 11 Column 1.

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

How can i download the testcase.txt in Atcoder?

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

https://atcoder.jp/contests/abc334/submissions/48787539 Can anyone tell me what's wrong with my code or help me download the testcase??? Thanks a lot!

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

Weird round, I solved ADE.

Now I've just finished upsolving B. Being that there's no editorial for the problem yet, I'll give an explanation of what I've done:

What we are being asked is easy to understand: we want the amount of numbers y in the range [l , r], such that y % m == a % m. One way to go about this is to subtract a from l and r, now the problem reduces to finding all y such that y % m == 0 in the range [l , r]. Good, this is easier because we can subtract (l — 1) % m to r % m and that will give us the amount of multiples in between... right? Well, the intuition is correct but there is a slight flaw: when l is negative the above formula doesn't work because of rounding. So what we can do is add m * (abs(l)/ m) to l and r and then apply the formula. Ta-da! Problem solved

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

please give me a little hint for problem b

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

for problem B why this logic is wrong

ll a, m, l, r;
cin >> a >> m >> l >> r;
ll ans = 0;
if (abs(l - a) % m == 0)
	ans++;
if (abs(r - a) % m == 0)
	ans++;
ans += abs(r - l - 1) / m;
cout << ans;

I am checking at l and r and between l to r

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

    Logic is simple. typical arthimetic sequence

    ll a, m, l, r;
cin >> a >> m >> l >> r;

ll kl = (l - a) / m;
ll kr = (r - a) / m;

if (a + kl * m < l) {
    kl++;
}

if (a + kr * m > r) {
    kr--;
}

ll first = a + kl * m;
ll second = a + kr * m;

ll ans = 1 + (second - first) / m;

cout << ans << endl;
    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A<D<<B<<C,I hate problem B

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

I made video editorial for F: Christmas Present 2

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

B is hard,the hardest B I've ever done.(AC 15,WA 5) I think this is also the reason it gets 250 points but not 200 points.

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

Can anyone explain my question on B. For 0 2 1 10, why the answer is 5??

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

    f***! My brain must have been damaged.

    → Reply