E is worth 425 only!

excited

Wish I can solve 7!

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

Wish I can solve 6!

I hope I can solve 3 problem.

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

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.

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

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

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.

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

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?

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.

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

Can Task G be solved without using __int128?

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

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!

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

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

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

anyone to explain D solution more?

Is codechef dead?

Where's ABC316?

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

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;
}