AtCoder Beginner Contest 358 Announcement

My post contest discussion stream for all problems

11 дней назад, # ^ |

that's not even the main thing , thing is output format could have been better , they just could have asked to output pair of cells which have wall between them

→ Ответить

nichke

11 дней назад, # ^ |

Yeah that's why I said implementing seemed messy. Format is weird. I didn't want to generate sequences of characters.

→ Ответить

GDCm1ro

11 дней назад, # |

← Rev. 10 →

What the fuck is the output format of problem F ???

What's the meaning of and the connected component containing the vertices (1,M) and (N,M) consists only of this path. ???

just for harder implementation ???

→ Ответить

harvey_wzy

11 дней назад, # ^ |

For human-readable

→ Ответить

aryanc403

11 дней назад, # |

← Rev. 2 →

→ Ответить

not_insync

11 дней назад, # |

26 correct 2 WA on C any idea submission

→ Ответить

SNX03

11 дней назад, # ^ |

Just go through every possibility $$$O(2^N)$$$

→ Ответить

MonoLith

11 дней назад, # ^ |

← Rev. 2 →

your way of computing minima is not correct

ex- 001 ,010,110

you only need shop 1 and 3 to fill the mask but your approach is greedy picking which is wrong and you will end up taking 1,2,3

hint-use bitmask

→ Ответить

_trie_again

11 дней назад, # |

any idea for g?

→ Ответить

ibrahimwq

11 дней назад, # ^ |

you only stay in only one cell

→ Ответить

TrendBattles

11 дней назад, # ^ |

You try to go to a certain point on a board then just spam staying in that point.

Because of that, you can try to dp here, like dp[u][T] is the maximum value you will receive when you use T turns to go from start to u (all points here are converted into 1-D coordination).

→ Ответить

11 дней назад, # ^ |

is $$$T$$$ fixed for certain $$$U$$$?

→ Ответить

_trie_again

11 дней назад, # ^ |

I considered for max value cell only, will fix it

→ Ответить

Astaaaaaa

11 дней назад, # ^ |

← Rev. 2 →

But how do you calculate T ? I was lucky to get AC doing similar thing using BFS but just kept increasing turns till I got AC.

→ Ответить

TrendBattles

11 дней назад, # ^ |

T <= H * W I suppose so

→ Ответить

Astaaaaaa

11 дней назад, # ^ |

Yep but is there any proof on why T <= H * W. Is it because the number of unique paths from a cell to any other cell bounded by H * W ?

→ Ответить

aryanc403

11 дней назад, # ^ |

Try 1968D - Permutation Game first. You can use almost same arguments for this problem.

→ Ответить

Astaaaaaa

11 дней назад, # ^ |

Alright , Thank you !

→ Ответить

lvisbl_

9 дней назад, # ^ |

Same argument.. what do you mean, I still can not understand why the maximum number of steps to check is H*W and I can not find any formal proof, this drive me crazy.

→ Ответить

11 дней назад, # ^ |

f i x,y means when Takahashi goes i steps and stops at (x,y), how many fun value can he get.

Takahashi may walk for some steps and stopped at a position forever.

It's easy to solve f i x,y when i<=n*m. And it's can be proved that Takahashi may walk at most n*m times, so the answer is MAX (f i x,y + a x,y * (K-i))

→ Ответить

what's wrong in my solution of G?

11 дней назад, # |

→ Ответить

jeal0uspengu1n

11 дней назад, # ^ |

It's the same mistake that I did, and wasn't patient enough to even debug it after the contest so went through the editorial and just noticed that the dp table is going to have 3 states and I got what I was doing wrong, hope it provides you a hint :9

→ Ответить

11 дней назад, # ^ |

yo same case , I also wasn't patient enough to debug and watched the editorial and yeah missed the crucial no of turns state

→ Ответить

aryanc403

11 дней назад, # ^ |

← Rev. 2 →

Shortest path to reach final cell is not enough.
Consider this testcase -

Spoiler

5 5 1000
5 1
100 99 99 99 99
0 0 0 0 99
0 0 0 0 99
0 0 0 0 99
99 99 99 99 99

Answer is — 99989

→ Ответить

AnishchukT

4 дня назад, # ^ |

← Rev. 3 →

but A[i][j] > 0 (never mind)

→ Ответить

AnishchukT

4 дня назад, # ^ |

Thanks a lot!

This is somewhat that is in testcase9

→ Ответить

RE_Prince

11 дней назад, # |

how E?

→ Ответить

11 дней назад, # |

+23

Problem F is frustrating. I accept the other six problems quickly with no penalty, but I had wrong F for 5 times.

→ Ответить

zenoalt

11 дней назад, # |

← Rev. 2 →

[deleted]

→ Ответить

xiaofu15191

11 дней назад, # |

Why does the C++ solution in the problem E's editorial unavailable?

→ Ответить

xiaofu15191

11 дней назад, # ^ |

Oh,sorry,maybe my internet has some problems.It is now available.

→ Ответить

Igor_Parfenov

11 дней назад, # |

I think, I solved problem like today's F not long time ago, but don't remember, where. Anyone remember?

Also, what happened with problem G? I've never seen anything such simple on this position.

→ Ответить

nichke

11 дней назад, # ^ |

G could have easily been a D/E imo.

→ Ответить

BouncyHunter

11 дней назад, # |

Anyone could hack my F please? I have been testing on it for about 1 hour but I don't know why it gets WA*3.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=100+10;
int n,m,k,a[maxn]; 
void solve(){
	cin>>n>>m>>k;
	if(k<n||(k&1)!=(n&1)) return cout<<"No"<<endl,void();
	int now=n;
	for(int i=1;i*2<=n;i++){
		if((k-now)/2<=m-1){
			a[i]=(k-now)/2;
			now=k;
			break;
		}
		a[i]=m-1,now+=m*2-2;
	}
//	for(int i=1;i*2<=n;i++) cout<<a[i]<<endl;
	if(now!=k) return cout<<"No"<<endl,void();
	int N=n*2+1,M=m*2+1;
	cout<<"Yes"<<endl;
	for(int i=1;i<=N;i++){
		if(i==1){
			for(int j=1;j<=M;j++) cout<<(j==M-1?'S':'+');
		}
		else if(i==N){
			for(int j=1;j<=M;j++) cout<<(j==M-1?'G':'+');
		}
		else if(i%2==0){
			for(int j=1;j<=M;j++){
				if(j==M||j==1) cout<<"+";
				else if(j%2==0) cout<<"o";
				else cout<<(m-j/2>a[(i-2)/4+1]?'|':'.');
			}
		}
		else{
			if((i/2)&1){
				for(int j=1;j<=M;j++){
					if(j&1) cout<<"+";
					else cout<<(m-j/2+1<=a[(i-2)/4+1]?'-':'.');
				}
			}
			else{
				for(int j=1;j<=M;j++){
					if(j&1) cout<<"+";
					else cout<<(j/2==m?'.':'-');
				}
			}
		}
		cout<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--) solve();
	return 0;
}

→ Ответить

wtc_fan

11 дней назад, # ^ |

+28

Your code fails when $$$n=3,m=5,k=13$$$. I am extremely sorry that you were disgusted by the authors!

→ Ответить

11 дней назад, # ^ |

← Rev. 3 →

+27

output:

Yes
+++++++++S+
+o.o.o.o.o+
+.+-+-+-+-+
+o|o.o|o|o+
+.+.+.+-+-+
+o.o|o.o.o+
+++++++++G+

→ Ответить

BouncyHunter

11 дней назад, # ^ |

+29

Thank you. I didn't notice that I can turn to the other side. And to be honest, I'm not disgusted XD anyway thanks a lot.

→ Ответить

https://atcoder.jp/contests/abc358/submissions/54597481

11 дней назад, # ^ |

+30

3 5 13 Yes +++++++++S+ +o.o.o.o.o+ +.+-+-+-+-+ +o|o.o.o.o+ +.+.+-+-+.+ +o.o|o|o|o+ +++++++++G+

It seems that you filled the path in maze one row by one row, however, when n is odd, you can also fill the last row but your code did not.

I also WA 3 for 5 times because of it, and it made me angry. However, after coming up with this situation, I accepted at once.

I have a friend who is rank 45, he didn't passed the following testcase but also accepted F in 67 minutes.

It is unfair, isn't it?

3 3 9 Yes +++++S+ +o.o.o+ +.+-+-+ +o|o.o+ +.+.+.+ +o.o|o+ +++++G+

→ Ответить

Jellyprx

11 дней назад, # ^ |

+23

You know that, I could pass the hack easily but I always got 1 RE.

Luck is always unpredictable

→ Ответить

crashsaladd

11 дней назад, # |

+11

Could someone please tell why my D fails ???

→ Ответить

MonoLith

11 дней назад, # ^ |

don't use it only stores unique element

let say a= 2,2,2,4,4,4

and b= 2,2

your approach will result in 2+4=6

but optimal one is 2+2=4

→ Ответить

MrCodder

11 дней назад, # ^ |

Use Multiset because element may repeat

→ Ответить

subhashgunda

11 дней назад, # |

+15

Can someone say why my Problem D is TLE Submission

→ Ответить

11 дней назад, # ^ |

+18

You should use ms.lower_bound(b[i])

→ Ответить

subhashgunda

11 дней назад, # ^ |

+10

can you please explain why does it make so much difference?

→ Ответить

11 дней назад, # ^ |

+10

set:: lowerbound is a binary search for red and black trees, with a complexity of O (log n).

std:: lower_bound for non randomly accessed containers, it is an iterator sequential search with a complexity of O (n).

→ Ответить

subhashgunda

11 дней назад, # |

Can someone please debug my Problem G(18xAC,18xRE)Submission

→ Ответить

11 дней назад, # ^ |

+10

1≤K≤10^9

You cannot open a vector whose size is related to K.

→ Ответить

tolbi

11 дней назад, # |

In problem F, O(n^2) is enough guys; all you have to do is do very little HOLY CASEWORK!!!

→ Ответить

cotx

11 дней назад, # ^ |

OTZ

→ Ответить

ZnPdCo

11 дней назад, # |

+15

Do they make AI more difficult to understand the statement by modifying important information in Problem F many times?

→ Ответить

11 дней назад, # ^ |

+10

That's right!

→ Ответить

11 дней назад, # ^ |

+14

I don't think so. I had never seen the input format or the output format when I was trying to solve Problem F because it's too long, but I still understand what the problem want me to do. I think AI is smart, and it may easily understand what did the problem mean. If AI can solve Problem F with correct information, it can also accept Problem F with wrong format.

ABC is for more than ten thousand people. If the question surface is wrong, it will make many people feel confusion. So I think it's no need to modifying importand information in order to make AI more difficult to understand Problem F.

→ Ответить

then00bprogrammer

11 дней назад, # |

E was such a good problem.

→ Ответить

AvaraKedavra

11 дней назад, # ^ |

How to do it ?

→ Ответить

then00bprogrammer

11 дней назад, # ^ |

← Rev. 3 →

It's DP+Combinatorics.

If you have n items, among which m are unique with quantities(q1, q2, q3... qm), the number of distinct ways to arrange these items is:

n!/(q1!*q2!...qm!) - (1)

Now for DP, there are two states [i,len] (i denotes the alphabet we're currently at and len denotes the length of our sequence so far).

Now, at each step, we attempt to take as many elements of that alphabet as possible. Therefore, the recurrence relation is:

dp[i][len]=sum(dp[i+1][len-j]*mod_inverse(j)) for j= 0 to min(c[i],len)

and base case is

dp[26][0]=1

For each state, by using mod_inverse at each step of calculation we've got denominator of eqn (1), to get the whole expression multiply it by len!.

Summation of dp[0][len] is your answer for len=1 to k.

Here's a link to my submission.

→ Ответить

AvaraKedavra

11 дней назад, # ^ |

← Rev. 2 →

Thanks mate.Amazing Solution.I appreciate your effort into writing this.

→ Ответить

XGptw

11 дней назад, # ^ |

yep it's good

→ Ответить

Pirate_King

11 дней назад, # |

Why does this TLE ??

→ Ответить

jose_5056

11 дней назад, # ^ |

Precompute the mod inverse for each $$${factorial_i}$$$.

→ Ответить

Pirate_King

11 дней назад, # ^ |

thx

→ Ответить

adaptatron

11 дней назад, # |

G is a nice follow up to the recent Atcoder problem : ABC344F : Earn to Advance. I also have a blog, hints and practice contest for the concepts used in the first problem.

→ Ответить

XGptw

11 дней назад, # ^ |

your articles are good.

→ Ответить

lvisbl_

9 дней назад, # ^ |

I dont see any relation between G and Time travel technique, can you help me to elaborate more?

→ Ответить

adaptatron

9 дней назад, # ^ |

It makes the observation trivial that there will only be one cell where you stay multiple cells. And this cell would be retrospectively fixed as the maximum valued cell that you encountered in your journey. Just like we did in ABC344F: Earn to Advance.

→ Ответить

_oO_Oo_

11 дней назад, # |

Can anyone tell me why am I having a TLE XD My code

→ Ответить

_oO_Oo_

11 дней назад, # ^ |

OK. I'm turning to C++.Same code in python and C++ led to 2209ms and 64ms.Almost got me crazy trying to optimize further in python :(

→ Ответить

Citypop

11 дней назад, # |

← Rev. 2 →

F is surprisingly neat if figure out the pattern, very fun to upsolve.

→ Ответить

cleanser

11 дней назад, # |

I don't like how I can go from TLE to a relatively fast AC in E simply by precomputing nck values.

→ Ответить