atcoder_official's blog

Toyota Programming Contest 2024#11（AtCoder Beginner Contest 379） Announcement
By atcoder_official, history, 2 weeks ago, In English

We will hold Toyota Programming Contest 2024#11（AtCoder Beginner Contest 379）.

We are looking forward to your participation!

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to ask how can come up with the solution in a short time. Sorry for my weak English.

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

GL && HF!

→ Reply
»
13 days ago, # |
  Vote: I like it +13 Vote: I do not like it

Today is my birthday!

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Seems a lot easier than previous contests. G is only 575.

$$$\Huge{\text{Good Luck & Have Fun!}}$$$
→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

GL&&HF!

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C is too difficult!

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C is way much harder than a 300-score problem, I think it worth at least 400.

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

    EDIT: only ~3.1k solves o_O

    interesting; why do you think that? it seems like it only required sorting and speeding up the simulation with triangular numbers... (and it doesn't seem like basically bruteforcing the thing is hard to come up with but i'm probably biased here)

    though i did get stuck on C for some reason

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

F was beautiful!

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For E, my only observation is:

For some number, says, 349685

Ans = 333333 + 2 * 44444 + 3 * 9999 + 4 * 666 + 5 * 88 + 6 * 5

But this will definitely get TLE, so how the hell did u guys manage to solve it?

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I unaccepted C at about 20:30,and I dont accept so far,but I dont know why I unaccepted.

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I assumed the input for boxes containing stones was sorted. Was wondering why getting WA the entire time ;)

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why bruteforce works for D? Solution

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

    I didnt try hoping it wud get TLE

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

    During he contest, I thought that was the intended solution. It works because a plant only be harvest(count/delete) for once.

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

      I think it should TLE. Eg a case where the first 1e5 queries are type 1, and the next 1e5 queries are type 2. Even if you compress Type 2 queries, should still TLE if you alternate between type 1 and type 2 queries...

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

        sorry, I missunderstood the OP's solution.

        But if the second operation was changed to something similar to lazy tag(then you insert -tag, and delete >= H-tag), then it works.

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

How to solve E? My approach is to consider the contribution of each digit, but used High Precision which caused TLE. :(

→ Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • I used the idea to "simulate how we simply add two or more numbers."
    • We will find the answer from last position to first position. First, store the contributions of all the digits.
    • For example:- In string 379 , 3 will come to the last position 1 time (Only 3), 7 will come to the last position 2 times(37 and 7), and 9 will come to the last position in some substring 3 times(379,79 and 9). Or we can say s[i] contribution to last position will be i+1 (0-based indexing).
    • Now, We will build the answer from last position from last position to first position. For this, we need to store "carry" term. After we process position i, we will delete the contribution of s[i] digit. At last, we will add if any carry left.
    • Submission Link — https://atcoder.jp/contests/abc379/submissions/59605521
    → Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

My bad for not checking conditions, but still not to sort input in C was totally unnecessary :(

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anybody can explain me the F problem ;-;

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

C was hard

Could not optimize to final state

→ Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

felt F was a next greatest ele problem but got confused from the testcases?

Example:

2 1 4 3 5

query: 1 and 2

expected ans: 2 (buildings with heights 3 and 5)

how is 1 able to see 3 and 5 ? isn't it blocked by 4 (building 3)

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

    You misread the example. It is building index 3 and 5 (not height) that can be seen. Building index 3's height is 4 and building index 5's height is 5.

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

      ohh it was a previous greater + next greater combo

      damn could've solved it

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

E made me laugh because I thought it was a easy simulation problem haha. Surprisingly, I got a 2210 runtime running at $$$O(n^2)$$$. I read the editorial last night and it had such a beautiful solution. 10/10 contest.

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

Can someone help with finding what's wrong with my submission for problem C https://atcoder.jp/contests/abc379/submissions/59600147

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

    Try this test case;

    Spoiler
    → Reply
    • »
      »
      »
      12 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, need to practice reading statements more carefully :)

      → Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

when the Testcases will be updated in dropbox and then i can download the wrong test?

→ Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone tell me where am wrong in C ? I've tried many times, but didn't accepted yet.... Below is my code. ~~~~~

define _CRT_SECURE_NO_WARNINGS

include <bits/stdc++.h>

using ll = long long int; using namespace std;

struct ch { ll x, y; } a[200005];

bool cmp(ch q, ch p) { return q.x < p.x; }

int main() { ll n, m; cin >> n >> m;

for (int i = 1; i <= m; i++)
    cin >> a[i].x;
for (int i = 1; i <= m; i++)
    cin >> a[i].y;

sort(a + 1, a + m + 1, cmp);
ll ans = 0;
for (int i = 1; i < m; i++)
{
    ll gap = a[i + 1].x - a[i].x - 1;
    ll d = gap * (gap + 1) / 2;
    if (gap == 0)
    {
        a[i + 1].y += a[i].y - 1;
        ans += a[i].y - 1;
    }
    if (gap <= a[i].y - 1&&gap!=0)
    {
        a[i + 1].y += a[i].y - 1 - gap; 
        ans += d;
    }
    if(gap>a[i].y-1)
    {
        cout << -1 << endl;
        return 0;
    }
}
ll last_gap = n - a[m].x;
ll last_cost = last_gap * (last_gap + 1) / 2;

if (last_gap < a[m].y - 1)
{
    cout << -1 << endl;
    return 0;
}
else
{
    ans += last_cost;
}

cout << ans << endl;
return 0;

} ~~~~~

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why no blog of ABC380 yet?

→ Reply