KEYENCE Programming Contest 2023 Summer（AtCoder Beginner Contest 315） Announcement

11 месяцев назад, # |

Wish I can solve 7!

→ Ответить

11 месяцев назад, # ^ |

Worship the strong.

→ Ответить

RoutineX

11 месяцев назад, # |

Did you guys notice that the recent ABC is becoming harder...

→ Ответить

H-y-h-CSP-J

11 месяцев назад, # ^ |

Yes,I noticed.

→ Ответить

11 месяцев назад, # ^ |

That's true. For someone who's really good, that's nothing. But for me, not being able to quickly make the first three questions really affects the mood of doing the question.

→ Ответить

11 месяцев назад, # ^ |

Yeah.

→ Ответить

hzx12345678

11 месяцев назад, # |

Wish I can solve 6!

→ Ответить

bluefamily_cf

11 месяцев назад, # |

I hope I can solve 3 problem.

→ Ответить

11 месяцев назад, # ^ |

-10

Me too...

→ Ответить

XuYuhao

11 месяцев назад, # ^ |

And I

→ Ответить

XuYuhao

11 месяцев назад, # ^ |

That's great. I passed my third question

→ Ответить

bluefamily_cf

11 месяцев назад, # ^ |

Me too.But I just can solve 3 problems.DEFG and Ex is too hard for me.

→ Ответить

11 месяцев назад, # |

Look at the Standings! Is the problem F realy easier than the problem D?

→ Ответить

pb_messi

11 месяцев назад, # ^ |

E is definitely easier than D.D and F are almost equal but i took more time to solve D.

→ Ответить

11 месяцев назад, # ^ |

+10

How can u solve D? I think F<E<<<G<D qwq

→ Ответить

SNX03

11 месяцев назад, # ^ |

so so true

→ Ответить

Albert_Wei

11 месяцев назад, # ^ |

I used something like BFS to solve it in O((n+m)^2),and I think it should be E<F<D

→ Ответить

tanonymouse

11 месяцев назад, # ^ |

can you provide solution for D? I mean the clarification confused me even more... would be helpful if you could explain your approach

→ Ответить

lsz_

11 месяцев назад, # ^ |

Agree,at least this is true in my friends standings.

→ Ответить

233L

11 месяцев назад, # ^ |

I cant agree more

→ Ответить

duya2007

11 месяцев назад, # |

D is quite hard...I think E is quite easier than D. I solved ABCE,but spent more than 30 minutes to try D,and WA 2 cases.

→ Ответить

11 месяцев назад, # ^ |

← Rev. 2 →

Ah, me too. I have solved ABCE, and the problem E is quite easier than D. I got an Accept in one go. But the problem D and F is so hard to me.

→ Ответить

233L

11 месяцев назад, # ^ |

ME TOO

→ Ответить

EarthMessenger

11 месяцев назад, # |

Problem D is too hard. I spend nearly 1 hour to understand the problem.

→ Ответить

IskhakKutBilim

11 месяцев назад, # |

is D simple simulation or what? I think that D is harder than F. But I spent more time to D and didn't have enough time to F

→ Ответить

metelkov

11 месяцев назад, # ^ |

← Rev. 2 →

I tried doing a simulation, but couldn't fit it into TL (aside from a couple of small implementation mistakes during the contest), my submission

Maybe there are a couple of possible constant-time optimizations to this approach, not sure

→ Ответить

metelkov

11 месяцев назад, # ^ |

← Rev. 3 →

After some time away I've figured it out: the main observation is that after we delete a row (or a column) of characters, this row/column won't appear in other columns (rows), so we can just store 2 sets of remaining rows and columns, and for each new deletion operation decrease occurrences of the current character c only in those columns/rows, if at any point there is only one kind of character left (we can check it with a map or an array of size 26) and there is more than one character — add it for deletion in the future, submission

→ Ответить

chromate00

11 месяцев назад, # ^ |

-8

During the simulation, maintain the frequency map of each row/column and a queue for recording what you must remove in the next turn. Only check rows/columns that have not been touched yet. As a result, every cell is accessed at most twice (once for its row, once for its column), and each cell change will take $$$O(1)$$$ or $$$O(\log(h+w))$$$. The time complexity turns out to be $$$O(hw)$$$ or $$$O(hw\log(h+w)$$$.

→ Ответить

Prayge

11 месяцев назад, # |

Anyone faced issues with strict TL in F? Quick mafs gave me upper bound on skips as 29 but this was TLEing for me. Submitted with skips limit 20 and got AC.

→ Ответить

suraj10

11 месяцев назад, # ^ |

I got AC with only 43ms runtime for F even after setting the upper bound as 30. Which language do you use? Or maybe recursive solution is too slow? I'll attach my solution for reference.

Link to my submission

→ Ответить

Prayge

11 месяцев назад, # ^ |

Yeah, I have seen c++ ones with similar runtime. probably doing something stupid somewhere. Will need to log times and compare ig. My TLEd solution here. AC one too gets 900ms idk here.

→ Ответить

suraj10

11 месяцев назад, # ^ |

Strangely after removing all the pow functions in your code, it passes in 8ms! Modified solution

→ Ответить

Prayge

11 месяцев назад, # ^ |

Thanks for taking a look. Well, that was unexpected. I assumed pow would be O(log n) at worst. Even it was linear, I was only calculating till exponent of max_skips. Idk but prob something to remember.

→ Ответить

coderchamp7

11 месяцев назад, # |

Not able to figure our why my submission gave TLE for 2 test cases https://atcoder.jp/contests/abc315/submissions/44754723 Even the editorial mentions that we had to optimize checking the number of unique characters in a row/column for which I am simply selecting the first character that is encountered and if any other character is encountered the row/column is skipped.

→ Ответить

tautology

11 месяцев назад, # |

What's wrong with my solution for E

int n;
  cin >> n;
  vector<int> adj[n + 1], indeg(n + 1, 0);
  for(int i = 1; i <= n; i++){
     int c;
     cin >> c;
     for(int j = 0; j < c; j++){
         int b;
         cin >> b;
         adj[i].push_back(b);
         indeg[b]++;
     }
  }
  queue<int> q;
  q.push(1);
  vector<int> order;
 
  while(!q.empty()){
     int u = q.front();
     q.pop();
     order.push_back(u);
     for(int v: adj[u]){
         indeg[v]--;
         if(indeg[v] == 0)
           q.push(v);
     }
  }
  reverse(order.begin(), order.end());
  order.pop_back();
  for(int val: order) cout << val << ' ';

→ Ответить

tautology

11 месяцев назад, # ^ |

Can someone provide counter case

→ Ответить

Srbmaury

11 месяцев назад, # ^ |

This may help

→ Ответить

tautology

11 месяцев назад, # ^ |

Thanks a lot! got the issue.

→ Ответить

IskhakKutBilim

11 месяцев назад, # |

task F: if the max total distance to reach n is N×100000 (it is from editorial) than if we take 32 being the max size of second index( the number of skipped checkpoints ) in our dp.32 is enough for it? why 100 (in editorial)?

→ Ответить

EduardoBrito

11 месяцев назад, # ^ |

I think $$$20$$$ is enough for this problem :)

→ Ответить

Albert_Wei

11 месяцев назад, # |

I wrote an easier solution to problem E

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

int n;
bool vis[200005];
vector<int> e[200005];
inline void dfs(int x) {
 vis[x] = true;
 for (auto i : e[x])
  if (!vis[i]) dfs(i);
 if (x != 1) cout << x << " ";
}

signed main() {
 cin >> n;
 for (int i = 1, c; i <= n; i++) {
  cin >> c;
  for (int j = 1, p; j <= c; j++) {
   cin >> p;
   e[i].push_back(p);
  }
 }
 dfs(1);
 return 0; 
}

is that correct?

→ Ответить

lsz_

11 месяцев назад, # ^ |

Looks correct,My AC code is similar with you.

→ Ответить

Albert_Wei

11 месяцев назад, # ^ |

thanks

→ Ответить

233L

11 месяцев назад, # ^ |

me too

→ Ответить

abhi.kr.2100

11 месяцев назад, # ^ |

Why does my solution which is very similar to yours cause TLE?

#include <bits/stdc++.h>

using namespace std;

vector<size_t> dfs(const vector<set<size_t>> &nodes, const size_t n,
                   vector<size_t> &toRead, vector<bool> &alreadyRead) {
  if (alreadyRead[n - 1]) {
    return toRead;
  }
  alreadyRead[n - 1] = true;

  for (const auto &p : nodes[n - 1]) {
    dfs(nodes, p, toRead, alreadyRead);
  }
  toRead.push_back(n);

  return toRead;
}

vector<size_t> dfs(const vector<set<size_t>> &nodes) {
  vector<size_t> toRead;
  vector<bool> alreadyRead(nodes.size());

  return dfs(nodes, 1, toRead, alreadyRead);
}

int main() {
  size_t n;
  cin >> n;

  vector<set<size_t>> books(n);
  for (auto &b : books) {
    size_t c;
    cin >> c;

    while (c--) {
      size_t p;
      cin >> p;
      b.insert(p);
    }
  }

  auto s = dfs(books);
  s.pop_back();

  for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
  }

  cout << "\n";
}

→ Ответить

11 месяцев назад, # ^ |

My AC code. Also use DFS, but I wrote a lot of functions to optimize.

→ Ответить

Mabangjie6789

11 месяцев назад, # ^ |

I think it's true. But the method of the editorial is much more complex, and the code is longer. I think they should change the order of D and E.

→ Ответить

abhi.kr.2100

11 месяцев назад, # ^ |

Why does my solution which is very similar to yours cause TLE?

#include <bits/stdc++.h>

using namespace std;

vector<size_t> dfs(const vector<set<size_t>> &nodes, const size_t n,
                   vector<size_t> &toRead, vector<bool> &alreadyRead) {
  if (alreadyRead[n - 1]) {
    return toRead;
  }
  alreadyRead[n - 1] = true;

  for (const auto &p : nodes[n - 1]) {
    dfs(nodes, p, toRead, alreadyRead);
  }
  toRead.push_back(n);

  return toRead;
}

vector<size_t> dfs(const vector<set<size_t>> &nodes) {
  vector<size_t> toRead;
  vector<bool> alreadyRead(nodes.size());

  return dfs(nodes, 1, toRead, alreadyRead);
}

int main() {
  size_t n;
  cin >> n;

  vector<set<size_t>> books(n);
  for (auto &b : books) {
    size_t c;
    cin >> c;

    while (c--) {
      size_t p;
      cin >> p;
      b.insert(p);
    }
  }

  auto s = dfs(books);
  s.pop_back();

  for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
  }

  cout << "\n";
}

→ Ответить

hxu10

11 месяцев назад, # |

+13

I thought in problem F, the order of visiting can be shuffled, and are wondering why so many contestants pass problem F.

When realizing the real meaning of ordered visiting in the last 1 minute before the contest end, I just want to kill myself.

→ Ответить

vd__coder

11 месяцев назад, # |

In D, I thought it is as graph problem, connecting (i,j) to 1. First cell which is left to it and have same character 2. First cell which is right of it and have same character 3. First cell above it and have same character 4. First cell below it and have same character

After making these connections, I just traversed the formed graph and count size of components. If size >1 , cells in that component should be removed. This causes TLE on some cases and WA on some.I don't know what's wrong in this

→ Ответить

WAtoAC2001

11 месяцев назад, # |

Can Task G be solved without using __int128?

→ Ответить

11 месяцев назад, # ^ |

Is __int128_t allowed in AtCoder?

→ Ответить

11 месяцев назад, # ^ |

← Rev. 2 →

Yes, it is allowed. Long double leads to WA*8.

→ Ответить

clocosacide

11 месяцев назад, # |

D is so hard... Tortured me for over half an hour!!! And E is a lot easier!!!

→ Ответить

sanatp977

11 месяцев назад, # |

← Rev. 2 →

Hello, for the problem B my solution works on my C++ 17 compiler but does not run on AtCoder providing a compilation error , and a wrong answer :

Main.cpp: In function ‘int main()’:

Main.cpp:11:6: warning: ‘m’ may be used uninitialized [-Wmaybe-uninitialized]

11 | m+=arr[i];

|     ~^~~~~~~~

Main.cpp:6:5: note: ‘m’ was declared here

6 | int m,t,middle;

Can you explain why the following submission does not work :

(header files)

using namespace std;

int main(){

ios::sync_with_stdio(0);

cin.tie(0);

int m,t,middle;

cin>>t;

int arr[t];

for(int i=0;i<t;i++){

cin>>arr[i];

m+=arr[i];

}

middle=(m+1)/2;

for(int i=0;i<t;i++){

if(arr[i]<middle){

    middle-=arr[i];

}

else{

    cout<<i+1<<" "<<middle<<"\n";

    break;

}

}

Thank you for your response

→ Ответить

123asdf123

11 месяцев назад, # ^ |

← Rev. 2 →

int m,t,middle;

change it to:

int m=0,t,middle;

→ Ответить

__SSB__

11 месяцев назад, # |

← Rev. 3 →

Question E,i used topological sort using DFS.Atcoder please increase the java stack depth, as i had to explicitly increase it to get the AC.

→ Ответить

Communication

11 месяцев назад, # |

-8

Help In Problem F For Recursive DP.

Code

double dp[maxn][25];
double rec(int prev_idx,int cur_idx,int skipped) {
    if (skipped >= 22 || cur_idx >= n) {
        return 1E9;
    }
    if(dp[cur_idx][skipped] != -1)return dp[cur_idx][skipped];
    if(cur_idx == n - 1) {
        double dis = calc(prev_idx,cur_idx);
        double val = 0.0;
        if(skipped > 0) {
            int c = skipped - 1;
            val = (1 << c);
        }
        return dp[cur_idx][skipped] = (dis + val);
    }
    double left  = rec(prev_idx, cur_idx + 1,skipped + 1);
    double right = rec(cur_idx , cur_idx + 1,skipped) + calc(prev_idx,cur_idx);
    return dp[cur_idx][skipped] = min(left,right);

}

→ Ответить

11 месяцев назад, # ^ |

← Rev. 2 →

you actually don't need the prev_idx, this is my submission: https://atcoder.jp/contests/abc315/submissions/44770131

let dp[i][skipped] minimum value to get from i to n having skipped "skipped" stations.

j from 1 to 30 dp[i][skipped]=min of( cost(i,i+j)+ dp[i+j][skipped+j])

and in the base cases if skipped>=30 just return something BIG else if i==n-1 return 2^(skipped-1); and that's it.

→ Ответить

vantaablackk

11 месяцев назад, # ^ |

Can you please explain why my solution is not working? I have used the same states. My submission.

→ Ответить

suraj10

11 месяцев назад, # |

D was a bit hard. I ended up thinking the solution to D for the whole contest and now after reading F I regret not taking a look at it during contest. Overall good contest!

→ Ответить

ayhan23

11 месяцев назад, # |

← Rev. 3 →

+29

My solution doesn't use extended_gcd or diophantine_equations for problem G.

My solution : We can fix A*i since n<=1e6. Let's call Y = X-A*i. We need to solve this equation: B*j + C*k = Y We can observe that (B*j) % C must be equal to Y % C. I maintained a map of vectors to store all (B*j)%Cs The rest of the solution is doing binary search on the vector corresponding Y % C

→ Ответить

11 месяцев назад, # ^ |

that's nice!

→ Ответить

11 месяцев назад, # ^ |

Aha. But what if k <= 0? I think in this case you cannot only %C.

→ Ответить

ayhan23

11 месяцев назад, # ^ |

We do 2 binary_search on our sorted vector (map[Y%c] => vector of B*j). Notice that k = (Y-B*j)/c In the first binary_search, we find the last B*j smaller than Y (don't forget that Y=X-A*i). This way (Y-B*j)/ C can't be <=0. In the second binary search, we find the first B * j that (Y-B*j)/ C is smaller or equal to <=n.

→ Ответить

11 месяцев назад, # ^ |

Oh, like lower_bound&upper_bound? I think I understand it. thx!

→ Ответить

ayhan23

11 месяцев назад, # ^ |

My submission

→ Ответить

Ten44Fun

11 месяцев назад, # |

When do the test cases get released? I got runtime errors on 4 of the test cases and I'm not sure why.

→ Ответить

11 месяцев назад, # ^ |

I am getting the same runtime errors on these 4 test cases. Can't figure out why....

→ Ответить

Ten44Fun

11 месяцев назад, # ^ |

After looking at accepted solutions, turns out we need to manually adjust the recursion limit of the program to something higher than its default value. I added two lines to the top of my program and it passed

import sys
sys.setrecursionlimit(10**8)

Link to solution

Wonder if the contest organizers are going to adjust any points based off this.

→ Ответить

11 месяцев назад, # ^ |

Interesting. I switched dfs to bfs, and it got accepted. Must be the recursion depth issue.

→ Ответить

profchi

11 месяцев назад, # |

← Rev. 5 →

+13

Using dfs with depth in tens of thousands was giving runtime error for Java code. This doesn't happen in previous contest. I double checked on an accepted question with this function

private static void dfs(int node) {

if (node == 100_000) return;

dfs(node + 1);

}

and

dfs(1) in the main function and was getting runtime error

Dfs with such depth didn't give stackoverflow errors in previous contest. What happened

→ Ответить

11 месяцев назад, # ^ |

Yeah, it must be a recent atcoder platform judge change. I wonder if it is because atcoder only supports Java17 now, it used to support Java8 as well. I did not run into this recursion depth issue back then.......

→ Ответить

profchi

11 месяцев назад, # ^ |

I noticed that on older contest, I used Java 11 and it's not available on newer contest.It may be caused by the -Xss JVM arguments. May be worth fixing this issue or adding back java 11.

→ Ответить

RTE with default stack size

11 месяцев назад, # ^ |

+16

atcoder_official Can you guys look into this issue? Recursive call in Java on AtCoder sometimes result in runtime error now due to the recursion stack depth. It used to work before switched to only Java 17 on the platform.

→ Ответить

Java_Programmer

11 месяцев назад, # ^ |

← Rev. 6 →

This is because of small stack size for recursive calls. We can create a new thread and assign stack size. (1<<26) stack size is sufficent for most recursive tasks.

AC with (1<<26) stack size

→ Ответить

WORTH

11 месяцев назад, # ^ |

Do you know why this is happening?

→ Ответить

Java_Programmer

11 месяцев назад, # ^ |

← Rev. 4 →

Quite strange, with 1024mb its giving MLE and 256mb AC... i have no clue.

But if we reduce thread stack size to 1<<26 it get AC 219687128

→ Ответить

Kamranali

11 месяцев назад, # |

← Rev. 2 →

Can anybody please say how to solve F?

→ Ответить

11 месяцев назад, # |

anyone to explain D solution more?

→ Ответить

llc5pg

11 месяцев назад, # ^ |

Starting with a brute force solution. Then optimize it by replacing the original matrix with some small arrays which hold the frequency tables of rows and columns.

→ Ответить