atcoder_official's blog

AtCoder Beginner Contest 417 Announcement
By atcoder_official, history, 9 months ago, In English

We will hold AtCoder Beginner Contest 417.

We are looking forward to your participation!

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

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

The difference in difficulty between question F and question G is a bit big today, but it doesn't affect my ability to do the question (after all, I am lucky to be able to do question F)

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

A-F too easy, but G too hard. This is completely a speed contest.

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

I kinda felt like question D was too hard. Am i stupid? I only managed to solve A-C Normally I am able to solve 4 questions.

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

    I usually solve A-C, but this time I solved also D. Just with prefix sum of B. if x > sum(b) + max(p), the answer is x — sum(b). Otherwise, I got the index idx where to begin iterating through presents, beginning with mood value

    x — prefixsum[idx — 1] (idx is the max possible so that this expression still > 0)

    and also caching known answers. I thought this solution would get TLE, but it passed.

    → Reply
    • »
      »
      »
      9 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it 
      // this is code
void solving() {
    ll n;
    cin >> n;
    vector<tuple<ll, ll, ll>> v;
    for (ll i = 0; i < n; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        v.emplace_back(a, b, c);
    }

    ll q;
    cin >> q;
    while (q--) {
        ll x;
        cin >> x;
        for (ll i = 0; i < n; i++) {
            ll a = get<0>(v[i]);
            ll b = get<1>(v[i]);
            ll c = get<2>(v[i]);
            if (a >= x) {
                x += b;
            } else {
                if (x < c) {
                    x = 0;
                } else {
                    x = x - c;
                }
            }

        }
        cout << x <<endl;

    }
}

      can you guys suggest what shouldve i done to not get TLE error from my code ??

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

      Do you use python or c++? I use c++, so if you use python and it barely passes, It might just be pretty quick in c++. or maybe java or pascal or rudy of idk I dont really know that much programming languages.

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

    I do think that D is harder than E and F.

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

    I also, thought D was too hard. Able to solve using binary search but I was 8 minutes late.

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

Can we finally ban a new "talent" from India binaryphoenix?

He is blatantly cheating in different platforms. And he has links posted in linkedin profile(with 2.5k followers btw). He got top1 in recent codechef round but wasn't be able solve C1 in last div1 round. I guess it's very convenient to know what problem is chat gpt proved but at this point it's getting ridiculous. atcoder_official Dominater069

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

    Does banning him increase your odds of solving more problems?

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

      No. It's slightly decreased. Without him I wouldn't be able to know what problems chatcpt can solve lol. I guess he's doing great work representing llm capabilities. Actually, we need more guys like him.

      Buy chatgpt pro. Cheat in every round. And even then, you're going to find a fellow defender from your country.

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

        Then why not just focus on solving problems and getting better? Instead of tagging a new guy everytime and getting him banned is a waste of efforts from your side, people are already doing their work whomsoever you tag everytime.

        Focus your energy on the right thing!! Best of luck.

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

          I think that if we turn a blind eye to cheaters it's totally unfair to other participants...

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

      .

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

Easy F, hard G. There's a GAAAAAAAAAP between F and G :(

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

why was F no brainer? or is it just me, it took me more time to solve D than to solve F.

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

Problem G can solve with balance tree. Wow

edit: the balance tree call WBLT, https://en.oi-wiki.org/ds/wblt/

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

Why did you use L[i], R[i] in G :((. I solved for concatenating the subarray of strings from L[i] to R[i]. X[i]/Y[i] would have been better imo.

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

Does anyone knew how to solve problem C? Mine is N^2 ans it is definitely TLE.

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

    I had the same issue with C and also D. Both solutions I made were TLE barely. Just didn't have time to rethink how to solve. They release the editorials after the contest so you can view the creator's solutions to the problems if that helps.

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

    rewrite the condition like j — Aj == i + Ai

    and save frequencies of past i + Ai in a map

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

G is well known persistent treap problem?

Or i am just dumb and just try to submit something that should not work?

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

    How do you do it with treaps?

    My solution: Moving to bigger of the L[i], R[i] and maintaining sort of binary lifting should work. Similar to Heavy-Light decomposition which would also solve for subarray L[i] to R[i] instead of just two points

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

      node stores value 0 or 1, create two nodes S0 and S1

      If size(root[l]) >= 10^18 just copy else just merge(root[l], root[r])

      print(root[i], pos)

      Merging in persistent treaps takes O(log(size)) in time and in number of nodes, so it can store string of length 10^18 with only ~120 nodes and each merge of two such nodes will create <= ~240 new nodes, so its fast enough

      However, there might be a problem where we unite one small(of size 10^18 — 1) node and one node of size 10^18, we create smth of size 2 * 10^18, and then we add another 10^18 — 1 and so on, so max size of str stores is at most 10^23, looks bad, yet, out persistent treaps will store it in log(10^23) nodes which should be good enough

      However, I was not able to figure out why I get 1/2 AC 1/2 RE during round

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

        I had the same problem and was not able to figure it out during the contest too.

        It's simple memory limit i guess. Even if we assume that we allocate about $$$120$$$ nodes per operation, we have $$$5 \cdot 10^5$$$ operations so we allocate about $$$60 \cdot 10^6$$$ nodes, which leaves us about $$$16$$$ bytes per node. And we at least need to store two pointers to left and write which alone would be $$$16$$$ bytes (in case we do not write treap on arrays where we can use int32_t as a "pointer").

        I made an experiment with exit(0) in my submission when i allocate more than $$$15 \cdot 10^6$$$ nodes and got rid of the RE, so it's just one of those cases when the judgement system confuses RE and ML.

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

        I've skimmed through some submissions sorted by memory limit by decreasing value, and it turns out it is possible to squeeze into the memory limit, but one has to be quite careful (e. g. https://atcoder.jp/contests/abc417/submissions/68172571).

        And it also seems that $$$30 \cdot 10^6$$$ nodes is enough (but i have no idea why, it's only 60 nodes per operation...).

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

          I just wrote a test that keep merging two treap with size 10^18, and turns out it use around $$$\frac{4 \times 10^7}{Q} \approx 2\ln(\text{10^18})$$$ per merge operation. Though I'm not sure how to analysis it properly.

          Btw, I didn't think that much and just create as many node as possible under ML when submitting it then pray it works lol

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

Screencast with commentary (once it is processed)
Didn't solve G though

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

For problem D, my solution is failing one test case. Can anyone point out the problem?

Submission Link for D

UPD: Found the problem. Never Mind!

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

SpeedCoder Beginner Contest. Wasn't able to solve G (TLE on testcases starting with "random2_") and solved A-F too slow, then got negative delta.

Also, long judge queue near the end of the contest.

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

How the Hell does this O(Q * N) code even passes????

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

    Is that so ?

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

    One of my friends' $$$O(nq)$$$ code also passed. I guess the test data is random. And here is the hack:

    #include <bits/stdc++.h>
#define rep(i, s, e) for(int i = s; i <= e; ++i)
using namespace std;
int main() {
	freopen("data.txt", "w", stdout);
	printf("10000\n");
	rep(i, 1, 10000) printf("1 1 1\n");
	printf("500000\n");
	rep(i, 1, 500000) printf("1\n");
	return 0;
}
    → Reply
»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone help me how to solve D and E ?

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

    For D, we maintain two sets of queries:

    • One containing values less than the current pi
    • Another containing values greater than or equal to pi.

    Since both Ai and Bi are ≤ 500, at most 500 elements can move from one set to the other during a single update operation. After each update, we must rebalance the two sets accordingly. We also maintain two variables:

    • l — the total value added to elements in the lower set
    • r — the total value added to elements in the upper set

    While balancing the sets, we need to handle these values( first find the current value then remove the effect of another set).N*Ai*log(Q)68158783

    Set will give TLE, so use priority_queue.

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

Task C of this contest has a similar idea with this problem here

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

Can anyone please help me identify difference in time complexity of this 2 submissions

TLE

AC

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

My submission for E keeps exceeding time limit for one testcase again and again. Could somebody please tell me if it's because my complexity is bad or if it's because my logic is flawed somewhere and so some loop doesn't break somewhere? My submission : https://atcoder.jp/contests/abc417/submissions/68172945

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

Is the data for question D too weak?

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

Finished my code of G, but considered as bot, cannot submit

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

For question D, why did I exceed the time limit by 6 test points，Mycode

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

It's too hard for the problem D, although I solved it with a weird DP w

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

E is so easy

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

My code got 30 WAs on G. Can somebody help me plz? submission

Upd: I considered $$$X_i$$$ as an int value. AC now :)

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

What am i missing in problem E: https://atcoder.jp/contests/abc417/tasks/abc417_e

Approach: visit min value node first and when cur dfs running node is y.. return.

Code: https://p.ip.fi/1WH2

→ Reply