atcoder_official's blog

AtCoder Beginner Contest 399 Announcement
By atcoder_official, history, 13 months ago, In English

We will hold AtCoder Beginner Contest 399.

We are looking forward to your participation!

  • Vote: I like it
  • -64
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
13 months ago, hide # |
← Rev. 3  
Vote: I like it +81 Vote: I do not like it

Hello AtCoder,

I think AtCoder needs development, Please stop blocking kenkoooo thanks. Or please add pages like My Submissions or Friends' Submissions on AtCoder. Thank you!

Besides, hope this round will be good. Last ABC is totally a speed round.

============================================

Update :

Not good, too :(

Problem E is well well-known and this is the link :(

And the problems' gap is too large for ABC :(

Debug & speed round :(

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

Hi Atcoder,

Please stop unblock kenkoooo thanks.

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

hope I can slove $$$5$$$ problems!

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

E has so many edge cases,also E<<F.

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

    ikr, I got E in the last 30 seconds and 4 WAs.

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

      How did u solve E? I converted it to a graph problem but kept getting 48/87 test cases

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

        I also got that same count for a while. Convert this to a functional graph, then the idea is the answer is initially just the number of edges. However, consider some "pure cycle", wherein there is nothing coming off of the cycle. In this case, we require 1 additional operation to break the cycle by using some additional letter outside the cycle. Of course, to have this "intermediary" letter available, we also need to ensure beforehand that not all letters are on a cycle. Using these ideas and just carefully implementing is enough.

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

          Damn, I got it right but missed the edge cases probably

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

I hope the authors will learn from the dissatisfactory experience they provided today.

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

Shit E playing joke on edge cases huh?

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

    lmao same. I still dont understand what are those edge cases. Isnt it just finding number of cycles? or my logic is wrong for E

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

      Not exactly. First, it's impossible if every node is on a cycle. Second, if for some cycle, there are ingoing edges into the cycle, then it's possible to solve this cycle without any extra operations. For example, if you have d->a->b->c->a, then you can do the operations: c -> d, b -> c, a -> b, d -> a, so you only need 4 and not 5 operations here.

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

        mb thx for the explanation:)

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

        Nice, this is the edge case I couldn't come up with.

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

        I dont know, whats wrong with my approach i am getting 81/87.

        My approach is to count number of pure cycles, if there is any pure cycle and all 26 characters are present in string s(ie all characters have outdegree==1) then answer is -1.

        Other wise i report ans = (count of such character x that s[i] = x and t[i]!=x) + (number of pure cycles)

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

E

F

Just a cool observation. Also, F is too classical so I think AI can solve it. wtf

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

shit problem E. so many edge cases....

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

Hi, please help with problem E. Here is my Code

My logic:

1) Create a graph from s[i] to t[i] and if more than 1 outgoing edge then print -1

2) Count the number of cycles

3) Decrease the cycle count for each self loop

4) Answer = cycle_count + (number of non self loop edges)

5) If there is a cycle but no unused character in t, then print -1

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

F has an easier solution with prefix sums and Newtons binomial

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

I have a solution for F with O(NK). Here is my code

And its derivation is

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

    A genious solution! So, we should first find the prefix sum of array-A, and then find the prefix sum of "this prefix sum", and also the power of 0,1,2,..k. Really wonderful idea, and thank you so much for sharing your solution.

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

Interesting E.

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

for Problem D: why am i getting WA ??? ~~~~~ void solve() { int n; cin >> n; vector v(2*n);

f(i, 0, 2*n - 1)    cin >> v[i];

vector<vector<int>> pos(n + 1);

f(i, 0, 2*n - 1) {
    pos[v[i]].pb(i);
}

// pr(pos);

int cnt = 0;
f(i, 0, 2*n - 2) {
    int a = v[i], b = v[i + 1];
    int diffa = pos[a][1] - pos[a][0];
    int diffb = pos[b][1] - pos[b][0];

    if(diffa == 1 or diffb == 1)    continue;

    vector<int> temp;
    temp = {pos[a][0], pos[a][1], pos[b][0], pos[b][1]};
    sort(all(temp));

    if(temp[0] + 1 == temp[1] and temp[2] + 1 == temp[3])   cnt++;
}

cout << cnt / 2 << endl;

} ~~~~~

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

    Your code is failing for testcase: (array of 8) : 1 2 1 2 3 4 3 4 Ans should be 2, but, your code gives output as 3.

    Actually for case, 1 2 1 2, ans should be 2, but, you are reporting as 3.

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

typedef long long int ll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define f(i, a, b) for(int i = a; i <= b; i++)

bool compare(const vector<int>& a, const vector<int>& b) {
    return a[1] < b[1];
}

void solve() { 
    int n; 
    cin >> n; 
    vector<int> v(2*n);

    for(int i = 0; i < 2*n; i++) 
        cin >> v[i];
    
    vector<vector<int>> pos(n + 1);
    
    for(int i = 0; i < 2*n; i++) {
        pos[v[i]].pb(i);
    }
    
    int cnt = 0;
    for(int i = 0; i < 2*n - 1; i++) {  
        int a = v[i], b = v[i + 1];

        int diffa = pos[a][1] - pos[a][0];
        int diffb = pos[b][1] - pos[b][0];

        if(diffa == 1 || diffb == 1) continue;

        vector<int> temp = {pos[a][0], pos[a][1], pos[b][0], pos[b][1]};
        sort(all(temp));

        if(temp[0] + 1 == temp[1] && temp[2] + 1 == temp[3] && (!(temp[1] + 1 == temp[2] && i == temp[1])))     // corrected the line 
            cnt++;
    }
    
    cout << cnt / 2 << endl;
} 

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}
    → Reply
»
13 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
void solve()
{
  int n;
  cin >> n;

  vector<vector<int>> a(n + 1);
  vector<int> b(2 * n);

  for (int i = 0; i < 2 * n; i++)
  {
    int x;
    cin >> x;
    b[i] = x;
    a[x].push_back(i);
  }

  int ans = 0;

  for (int i = 1; i <= n; i++)
  {
    // first index of i
    int kk = a[i][0];
    int ll = b[kk + 1]; // find the element in the next index in original array
    if (a[i][1] - a[i][0] != 1 && a[ll][1] - a[ll][0] != 1) //no two adjecent 
    {
      if (abs(a[i][0] - a[ll][0]) == 1 && abs(a[i][1] - a[ll][1]) == 1) //but i can make it
      {
        ans++;
      }
    }
  }
  cout << ans << endl;
  return;
}

why this gives WA in D?

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

What's the issue in my code for problem E

My submission for E

→ Reply