atcoder_official's blog

AtCoder Beginner Contest 347 Announcement
By atcoder_official, history, 4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck to everyone!

→ Reply
»
4 weeks ago, # |
← Rev. 2   Vote: I like it -21 Vote: I do not like it

GLHF.

And let's have a guess!

Good Round :
Just so so Round :
Bad Round :

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can stop dropping rated this round!

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

GL&HF.Hope my rating do not drop

→ Reply
»
4 weeks ago, # |
  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
  • »
    »
    4 weeks ago, # ^ |
      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
  • »
    »
    4 weeks ago, # ^ |
      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
  • »
    »
    4 weeks ago, # ^ |
      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 > 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
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i also failed the same TC

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

      Thanks，I have never thouht of that and WA on 01_test_28.txt

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

    Answer should be yes.

    → Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

C was annoying

→ Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc347/submissions/51878189
where is this code going wrong ?? can anyone help . Thank you in advance

→ Reply
»
4 weeks ago, # |
← 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
»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

D can be solved using DP.

AC Code

→ Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My approach to problem C was I calculated all days[i]%(a + b) then find the maximum and minimum in this array if then length is greater than a then its no otherwise yes but it did fail 1 test case IDK can somebody explain why is this approach wrong ! much appreciated

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

    Do you know what the problem is with your solution because I have the same problem.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can somebody tell me why c is failing? I am checking if this below condition fails then it should be no: if(ar[i]%(a+b)>0 && ar[i]%(a+b)<=a) https://atcoder.jp/contests/abc347/submissions/51823167

→ Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
  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
  • »
    »
    4 weeks ago, # ^ |
      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
  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

I must say problem C is very perfect

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

apologize for my impulse.

This comment was deleted.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 3   Vote: I like it +12 Vote: I do not like it

    an accepted submission

    data:

    4 1
25 77 63 69 
31 57 46 14 
22 74 67 5 
58 80 22 62

    ans: 80+77+74=231

    my output is right while I did't pass the problem. The mentioned submission got wrong output.

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

    In addition, the problem F is also the same as a problem in APIO2009. We found that the solution of that problem cannot be accepted in this. The problem link in a Chinese site.

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

    I've just known that there's a problem of APIO which is almost the same as this one. I passed that problem.

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

    ...well, I hacked my submission just now. maybe the tests of F are weak but correct.

    → Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
  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
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    lets say after doing modulo operation our array becomes 0 1 8 and a = 5, b= 5. basically we cant just rely on the the length of holidays we also have to factor in the days on which we can plan our events. in above tc max-min will give no. but if we think of today as day 4 then ans is yes

    → Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
  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
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i also did same, People are sorting the array, i think we didnt get the question. Can somebody explained what is the expectation of the problem?

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

    For this test case

    2 5 2
6 7

    The answer is Yes but you output No

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

      Understood. So basically the start day need not be the 1st day itself. Thanks.

      → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I really Liked the Problem E,

My solution to E, using two sets

E Solution
→ Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
← 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
  • »
    »
    4 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    hey sorry to ask, can you please check my submission and let me know what i am doing wrong

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

      only checking the maximum and minimum values is not enough.

      your solution is far from the right one. suggest you do read the Editorial.

      → Reply
      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        thanks man also don't stay alone

        → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me what's wrong with my E solution? It's AC for some tests but logic looks correct https://atcoder.jp/contests/abc347/submissions/51888633

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain me the C's editorial. I didnt get why we are subtracting ei+1- ei?

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me find out where this code is failing for D? Submission Link

→ Reply
»
4 weeks ago, # |
← 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
»
4 weeks ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Need help in debugging my code for problem D. My code fails on the last test case. Please help me in debugging, I'm not able to find any mistake. My Submission for D

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem c was very annoying

→ Reply
»
4 weeks ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it
Spoiler

Can someone help me figure out why my code for problem C is failing , there's only 1 testcase that it didn't pass and I can't find a counter test case for my code.
According to my logic we reduce A[i] to A[i]%(a+b) at first , then we check for each Di how much we need to add in order for its mod with a+b to lie within [1,a] , based on this we'll get edges of an interval , if the interval is overlapping for all values of Di then I print yes , else no.

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

I also received 1 WA in C, but then I encountered an edge case where we can also create a cyclic schedule (which I hadn't considered during the contest).

1 WA Code
AC Code
→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what's a cyclic schedule?

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

      I mean you can imagine that as the subarray of plans which should have smallest length and fits in holiday schedule (You can make any day as starting point and see).

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

        how to visualize total — plan[i] + plan[i — 1]?

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

          Take an example a = 4, b = 3
          Total Days: 1 2 3 4 5 6 7
          so you can have holiday of length 4 (4 days)
          Plans = 1 2 6

          now as per my code
          - you can say 1 as your first day of holiday so 1 2 3 4 here 6 is not included so it will not work
          - now 2 as your first day of holiday so 2 3 4 5 this will also not work
          - now 6 as your first day so 6 7 1 2, it is covering all plans so it is possible to do plan on this holiday window.

          I hope you got the point.

          → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why I didn't take a look at PE... It turns out that PE was much easier than PC.

→ Reply
»
4 weeks ago, # |
  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
»
4 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
11 days ago, # |
  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