atcoder_official's blog

AtCoder Beginner Contest 347 Announcement
By atcoder_official, history, 2 years ago, In English

We will hold AtCoder Beginner Contest 347.

We are looking forward to your participation!

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

Comments Comments (46)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I hope I can stop dropping rated this round!

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

GL&HF.Hope my rating do not drop

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

My submission for problem C gives WA for only 1 testcase — LINK.

I can't figure out what's wrong in this,any help is appreciated.

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it -27 Vote: I do not like it

    same issue can anyone help

    include

    include

    include

    using namespace std;

    int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

    int N;
long long A, B;
cin >> N >> A >> B;

vector<long long> D(N);
for (int i = 0; i < N; ++i) {
    cin >> D[i];
}

long long week_length = A + B;

// Calculate the minimum and maximum days later
vector<long long> temp;
for (int i = 0; i < N; ++i) {
    long long days_later = D[i] % week_length;
    if (days_later == 0) {
        days_later = week_length;
    }
    temp.push_back(days_later);
}
sort(temp.begin(), temp.end());
long long mini = temp[0];
long long maxi = temp[N - 1];

// Check if the difference between mini and maxi is less than or equal to A
bool flag = (maxi - mini < A);

if (flag) {
    cout << "Yes" << endl;
} else {
    cout << "No" << endl;
}

return 0;

    } this is my code

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    same issue dude, I missed both C and D today by just 1 test case each, which is the same test case as what you got wrong. I have no idea what could go wrong, spent 1 hr into debugging but of no use :(

    Someone please help.

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

    I think that the problem with your solution is that you didn't take into account that, even after first taking the remainder modulo $$$(A + B)$$$, the array can still be shifted for better adjustment.

    To illustrate this with an example, try the hack:

    2 5 5

    1 7

    The correct answer should be "Yes", but your solution outputs "No". The reason is, after taking the remainder, the array is still $$$[1, 7]$$$, but this gap of length $$$6 \gt A = 5$$$ between $$$1$$$ and $$$7$$$ means we can still shift the dates so that the first plan is on Day 5 and the second plan is on Day 11, which still works.

    I reckon that anyone else failing to pass one or two test cases might be having this problem, too.

    → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    Spoiler

    Answer should be yes.

    → Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

was able to solve till E, what's wrong with 1 testcase in C? can anybody tell that testcase?

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

Problem F is almost same with https://www.luogu.com.cn/problem/P3625

→ Reply
»
2 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

problem C ????????????

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

what was the last test case in problem D, I spent more than half hour but was unable to figure out that test case

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

https://atcoder.jp/contests/abc347/submissions/51845269

any help for C test case?

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

You can actually pass F without considering those two cases:

if (M <= i && i + M < N - M + 1) // three squares arranged vertically; fix the center square
    chmax(ans, upper_left[i - M].back() + sum[i][j] + lower_right[i + M].front());
if (M <= j && j + M < N - M + 1) // three squares arranged horizontally; fix the center square
    chmax(ans, upper_left.back()[j - M] + sum[i][j] + lower_right.front()[j + M]);

If you comment those in the std you can still get an AC. Weak tests.

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

Does greedy not work for D?

https://atcoder.jp/contests/abc347/submissions/51871701

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    You need to apply one more check, that the numbers you have constrcuted have popcounts equal to a and b respectively, As for both num1 and num2 too you have constraint of being <2^60

    Think of a case when a = 60 b = 60 and you have popcount of c = 60

    In this case you will greedilly keep 30 1's in num1 and other 30 1's in num2, This will satisfy xor condition, but you don't have 60 popcounts in num1 and num2

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

    it works https://atcoder.jp/contests/abc347/submissions/52433050

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

I must say problem C is very perfect

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

apologize for my impulse.

This comment was deleted.

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

Good contest. Got 1 of WAs in C because got used to printing "YES" in cfs and atcoder requires 'Yes' :p

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

My pC also got 1 subtask WA at 01_test_28.txt ; Wondering what's the problem of my idea ; Actually I don't even think we need O(NlogN) to solve this ; Can't we just simply calculate the max and min value of D_i%(A+B) for all elements in D ; And consider the "max-min < A" one as "Yes" case?

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

What was C? I kept getting WA on 1 testcase, also I feel D>E.

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

My Solution for E !!

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int n , q;
    cin >> n >> q;
    vector<ll> queries(q+10,0) , vis(n+10,0) , ans(n+10,0) , marked(n+10,0) , sum(q+10,0);

    ll unique = 0;
    for(int i = 1; i <= q;i++){
        cin >> queries[i];
        ll x = queries[i];
        if(vis[x]) vis[x] = 0 , unique--;
        else vis[x] = 1 , unique++;
        sum[i] =  unique;
    }

    for(int i = 1; i <= q; i++) sum[i] += sum[i-1];

    for(int i = 1 ; i <= q; i++){
        ll x = queries[i];
        if(marked[x]){
            ans[x] += sum[i-1];
            marked[x] = 0;
        }
        else{
            ans[x] -= sum[i-1];
            marked[x] = 1;
        }
    }

    for(int i = 1 ; i <= n ; i++) if(marked[i]) ans[i] += sum[q];
    for(int i = 1 ; i <= n ; i++) cout << ans[i] << " ";

    return 0;
}
→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can someone help me understand why my solution for C is wrong. Below is what I did.

for (int D : plans) {
    int rem = D % (A + B);
    if (!(1 <= rem && rem <= A)) {
            return "No";
    }
}
return "Yes";
→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone Give Counter Test for C https://atcoder.jp/contests/abc347/submissions/51861296 it is just falling on 2 test case

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

a possible hack for problem F:

5 2
57 67 65 27 55 
46 20 63 8 71 
44 56 44 11 14 
47 23 46 90 56 
36 30 21 76 12

the answer is 619.

(i1, i2, i3, i4, i5, i6) = (1, 2, 3, 1, 4, 4).

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

I think the testdata of F is kind of weak.
The solution mentioned 6 situations, but I didn't check the 1st and 4th (three submatrices on [left, mid, right], [top, mid, bottom]), still got AC.

My submission
(the array dp2[][] is useless)

A hack data which my code can't pass:

Input:
3 1
2 2 2
0 0 0
0 0 0

Answer: 6
Output: 4

Update: Here's what happened in my code.

ll dp1[4][maxn][maxn]; // LU LD RU RD

ll ans = -0x3f3f3f3f3f3f3f3fll;
for (int i = 1; i < n; ++i) {
  for (int j = 1; j < n; ++j) {
    // LU RU D
    ans = std::max(ans, dp1[0][i][j] + dp1[2][i][j + 1] + dp1[1][i + 1][n]);
    // LD RD U
    ans = std::max(ans, dp1[1][i + 1][j] + dp1[3][i + 1][j + 1] + dp1[0][i][n]);
    // LU LD R
    ans = std::max(ans, dp1[0][i][j] + dp1[1][i + 1][j] + dp1[2][n][j + 1]);
    // RU RD L
    ans = std::max(ans, dp1[2][i][j + 1] + dp1[3][i + 1][j + 1] + dp1[0][n][j]);
    // I didn't check L M R and U M D
  }
}
std::cout << ans << '\n';
→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Mr. Takahashi, could you please add my ranking when I click on the Show favs only to filter the ranking list . So that we can compare with our good friends. Just like the Codeforces.

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

why checking only if(d[i - 1] + a + b - d[i] + 1 <= a){ flag = 1; } is sufficent ?

what about the days at left of i-1 and to the right of i ?

how we will make sure that are also satisfied

→ Reply