atcoder_official's blog

KEYENCE Programming Contest 2023 Summer（AtCoder Beginner Contest 315） Announcement
By atcoder_official, history, 10 months ago, In English

We will hold KEYENCE Programming Contest 2023 Summer（AtCoder Beginner Contest 315）.

The point values will be 100-200-300-400-425-500-575-625.

We are looking forward to your participation!

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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool

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

E is worth 425 only!

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

excited

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

Wish I can solve 7!

→ Reply
»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes,I noticed.

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

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

    Yeah.

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

Wish I can solve 6!

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

I hope I can solve 3 problem.

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

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

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

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

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

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

        so so true

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

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

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

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

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

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

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

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.

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

    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.

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

    ME TOO

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

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

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

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

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

    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

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

      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

      → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    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)$$$.

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

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.

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

    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

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

      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.

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

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

        → Reply
        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

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

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.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it
What's wrong with my solution for E
→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)?

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

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?

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

    Looks correct,My AC code is similar with you.

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

      thanks

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

      me too

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

      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";
}
      → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

    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.

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

    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";
}
    → Reply
»
10 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

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

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

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

Can Task G be solved without using __int128?

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

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

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

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

→ Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

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

Help In Problem F For Recursive DP.

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

    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.

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

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!

→ Reply
»
9 months ago, # |
← Rev. 3   Vote: I like it +29 Vote: I do not like it

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

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

    that's nice!

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

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

      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.

      → Reply
      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

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

      My submission

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

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

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

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

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

      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.

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

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

        → Reply
»
9 months ago, # |
← Rev. 5   Vote: I like it +13 Vote: I do not like it

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

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

    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.......

    → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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.

      → Reply
  • »
    »
    9 months ago, # ^ |
    ← Rev. 6   Vote: I like it +1 Vote: I do not like it

    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.

    RTE with default stack size

    AC with (1<<26) stack size

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

Can anybody please say how to solve F?

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

anyone to explain D solution more?

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

    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.

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

Is codechef dead?

→ Reply
»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Where's ABC316?

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

Can someone please explain why my solution for problem F is not working? I have used dp[current index][no. of skipped checkpoints] = minimum distance of path; just as the editorial has mentioned. My Submission.

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

is G solvable with dp, i think it's quite similar to this problem https://cses.fi/problemset/task/1159

upd: i guess it's not possible

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

for E it is giving tle on 2 testcases anyone help pls me?

my code link

Your code here...
#include <bits/stdc++.h>
#define int long long
#define double long double
#define superSLOW ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define TxtIO  freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
const int mod=1e9+7;
const int inf=1e18;
using namespace std;

void dijkstra(vector<vector<pair<int,int>>> &g , vector<int> &dis , int node){
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,node});
	dis[node]=0;
	while(!pq.empty()){
		auto u=pq.top();pq.pop();
		int node=u.ss;
		int d=u.ff;
		if(dis[node]<d)continue;
		dis[node]=d;
		for(auto ch:g[node]){
			if(dis[ch.ff]>(dis[node]+ch.ss)){
				dis[ch.ff]=dis[node]+ch.ss;
				pq.push({dis[ch.ff],ch.ff});
			}
		}
	}
}

int32_t main() {
	// your code goes hereTxtIO;
	superSLOW;
	int n;cin>>n;
	vector<vector<pii>>g(n+1);
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		while(x--){
			int y;cin>>y;
			g[i].pb({y,-1});
		}
	}
	
	vector<int>dis(n+1,inf);
	dijkstra(g,dis,1);
	vector<pii>ans;
	for(int i=1;i<=n;i++){
		ans.pb({dis[i],i});
	}
	sort(ans.begin(),ans.end());
	for(int i=0;i<n;i++){
		if(ans[i].ff==inf or ans[i].ss==1)break;
		cout<<ans[i].ss<<" ";
	}
	cout<<endl;
	return 0;
}
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I used DFS for E, but I get TLE for some tests. Can someone tell me what I'm doing wrong? https://atcoder.jp/contests/abc315/submissions/44953559

→ Reply