Problem F : In the following submission why am I getting WA. Don't worry about TLE.

My submission

speed really matters on atcoder

E << C << D. Difficulty level according to me (T_T)

Do you mean easy ?

It too does not work because of worst case time complexity of n * m.

I tried from high to low => failed on test case 3. Tried from low to high => passed.

was it mentioned that D is pretest = full test ?

in the last 10 minutes. (T_T)

I guess your implementation will be correct just you are using more than 2 * n queries.

Same mistake as me. You should traverse from rightmost bit to leftmost bit. This reduces the possible values of pn to atleast 1/2 each time.

I just made multiple wrong submissions in D and spent a lot of time. I was checking from highest to lowest bit set each time which would fail sometimes. Change it to from lowest to highest bit and the solution passes.

WTF i thought i did lock it so it would not matter. Unnecessary -ve rating

what ?

for problem c1 i submitted correct solution at 48 mins but to verify my solution for c2 i tried submitting other solutions so they are considering the last submitted solution or the first submitted solution ? ( I am fucked)(T_T)

Check this : https://atcoder.jp/contests/abc424/submissions/69491621

Any Hints / Suggestions for Problem E ?

I was looking for something like binary search.

Consider chords as linear segments. So you just have to check if new chord inserted will intersect with already available segments. So if current chord is l,r. Then find minimum (L)left endpoint of any segment that has right endpoint in range(l to r). Similarly check for maximum R.

U can use segtree for it.

D was easier just Brute Force and seeing the constraints. Btw I took too much time for that problem (T_T).

Again. I think Problem E >> Problem F.

brute force. I also missed the constraints that n and m <= 7 and tried Greedy. After noticing that bitmask and DP worked.

D was really good problem. Any hints ?

I was wondering if it’s okay to have E2 with a slight difference from E1 just to make it optimal and get AC?

I mean what was the logic ? for E1 i did calculate no. of nodes at each level and then used dp to find maximum number of nodes that can be painted with 1's.

Finally if all nodes till certain depth(mx) can be painted then answer is mx else mx — 1.

How was bitset used to solve the problem ?

Can you share what logic did you use ?

Any idea how to solve this problem ?

I found this CSES:Maximum Building II which can be used to solve the problem. But is there any other alternate way that is easier ?

Okay got it i didn't see this part :

**The former is the next earlier index on the same row with a strictly lower downi,j value. The latter is the next later index on the same row with a lower or equal down(i,j) value**.

Can you explain how would you calculate number of rectangles for [1, 1, 1]. I think using your method we will contribution of each position = [3, 4, 3] so total = 3+4+3 != 6.

Okay, so I know how to calculate the maximal area of rectangle containing all 1's in a matrix. How can i use it to calculate number of rectangles that only contain 1's ?

what do you mean by adding the areas?

Suppose the original matrix is [1, 1, 1] then area will be [3, 3, 3] so sum = 9 but number of rectangles with all 1's are 6.

Could someone please help with problem E? It’s a really nice problem.

Lets make it most downvoted ABC contest

F easy cause setter ran out of evil.

Too much time + multiple wrong attempts = fucked up!!!

F was very easier compared to D. You just have to use linked list in F and no complex logic or anything.

I think D was difficult(wording atleast) compared to F. In F you just have to use a linked List nothing else. (T_T)

Spent too much time in problem D and multiple wrong attempts due to silly mistake.(T_T T_T)

for ||gm sum of coordinates opposite vertices are equal.

x1 + x3 = x2 + x4

y1 + y3 = y2 + y4

How to solve problem F — We're teapots ?

What i understood till now :

• number of ways to fill coffee and tea in n length array without constraints is

    ways[0] = 1;
    ways[1] = 2; 
    for(int i = 2; i <= n; i++){
        ways[i] = (ways[i-1] + ways[i-2]) % mod2;
    }

• number of ways to fill exactly r coffee in n length such that any two cups has atleast one tea is (n-r+1) C r

Thanks. It’s working now. So the problem was that I didn’t count the socks that wasn't in the drawer initially.

not able to figure out what is wrong with this submission :

my solution

That was accepted. But now I got it why. Because we are only checking points between corners the time complexity will be O(n).

In problem F2 why the following code isn't giving TLE? What is time complexity of the loop for given problem ?

for(int i = 1; i <= k; ++i){
        auto e = a[i - 1];
        if(ans[idx[e]] == 0)continue;
        int tot = total[i - 1];
        int cr = cur[i - 1];
        int lst = last[i - 1];
        for(int j = i + 1; j <= k; ++j){
            auto ee = a[j - 1];
            if(cr > ee.y){
                tot += (cr - 1) * (lst - ee.x);
                cr = ee.y;
                lst = ee.x;
            }
            if(ans[idx[ee]] == 1){
                ans[idx[e]] = tot - total[j];
                break;
            }
        }
    }

how did you find Weighted Maximum Independent Set for a given graph ?

I replaced long long with int everywhere and it didn't give TLE (T_T).

I found logic easily for D but couldn't implement the solution (T_T).

Thanks issue solved.

I used the same logic still i am getting 9 TLE and 2 WA. Can you point out the mistake?? My Submission

what is wrong in this submission? I mean i was looking for a counter test case.

Have look at this ;)

I was stuck at this case only.

if n = 3 and s = 4*X then what will be solution ??? example n = 3 and s = 16

Just do the Brute Force way. Time complexity will be around O(NWH).

how was QR code involved in F??

what was logic for C

They Have Really Fooled us T_T.

I think the test cases are weak because I was also getting only 1 test case wrong for wrong solution.

Can anyone pls give any counter example for this logic. This is the code.

Sorry I got the mistake ;).

sort(all(Q), [](vll& a, vll& b){return a[1] < b[1];});

Earlier I was passing a and b as value.

This is My Submission for problem D can you tell why this submission is showing TLE. I have used segment tree.

i was getting ((n-1)(n-2))/2. is it right ??

isn't it negative for n = 4 ?? but answer is 3

how do you apply 0-1 BFS on G ??

for (auto el : ans) {
el = (el + r)%n + 1;
}
// replace it with for (auto &el : ans)

you aren't changing el while traversing

what is logic for ** Problem G** .

repeat the same steps for req+1 and req — 1 also

or other lesson is to generally use long long.

Problem G is nice.

why to check only subarray when we can choose subsequence also ???

i guess implementation was easy but but grasping the underlying logic may be challenging.

Common in recent contests :

1. Fast editorial
2. Fast system testing
3. difficulty of D is less than C.

I was stuck for 1 hr and solved D in less time.

I think latest trend is difficulty of D is less than C in div2. And System testing just after contest. :)

Problem C was harder than D. Spent most of the time in C.(T_T)

Check This submission. Second cube from 0->14 and first from 0->7. and the test cases doesn't fail.

My submission I am storing maximum and second maximum using sqrt decomposition . But I am getting wrong answer. Can you pls check what is wrong with it ?

Fast system testing..

1. First find possible points from query(1,1) , query(1,n) , query(1,m). Atmost two points are possible from this.
2. now find distance from one of the possible points . if you get response as zero then this pair is answer or other pair will be answer.

InteractiveForces

also you are using endl multiple times.

May be to make question more easy. :)

++ fast system testing

make a function to calculate the responses for your queries and then comment the function while submitting.

tourist might come back to top 10 rated today :) :)

#include <iostream>
using namespace std;

int main() {
    cout << "1\n"; // End the line after printing "1"
    cout << "1000 1000\n"; // End the line after printing "1000 1000"
    for(int i = 0; i < 1000; i++) {
        for(int j = 0; j < 1000; j++) {
            cout << "0 "; // Print "0 " without a newline
        }
        cout << "\n"; // End the line after printing each row of zeros
    }
    return 0;
}

I am trying to hack Problem F using above generator. But got this Verdict "Validator 'validator.exe' returns exit code 3 [FAIL Expected integer, but "#include" found (stdin, line 1)]". Someone help me find the error.

i also did BFS. My Submission. But got TLE. How??

are u checking upward in all columns ??

you are passing vector by reference in binary search. use vector & pre

so move up only in last column will reduce your time complexity from O(n*n*m) to O(n^m)

I did same. i did not observe that robot will move up only in last column :(.

Problem F: BFS with one tricky observation. In this problem, the robot will move upward only when it's in the last column. Due to this constraint, the straightforward Depth-First Search (DFS) approach might lead to Time Limit Exceeded (TLE). This optimization should help improve the performance and prevent TLE.

speed matters mostly in those contests.

Nice Contest.

True wasted time on C.

I spent too much time on problem C and Did not attend problem D which was easy . Problem statement was not clear and ended up with negative rating change.Regret giving this contest(T_T).

When used for queue it clears the queue.