atcoder_official's blog

AtCoder Beginner Contest 358 Announcement
By atcoder_official, history, 6 months ago, In English

We will hold AtCoder Beginner Contest 358.

We are looking forward to your participation!

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

»
6 months ago, # |
  Vote: I like it +4 Vote: I do not like it

exited

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

Only 550 pts G!

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

Hi, i am new to competitive programming and new to AtCoder. I am curious about the rating score of ABC questions, what are their equivalent codeforces rating scores? Is their a formula that can do the conversion? Thx

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

I refuse to write solution for F even if i'm getting paid.

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

    Exactly. I had solution after 1 minute of thinking but just implementing it seemed messy so I gave up on it.

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

      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

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

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

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

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

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

My post contest discussion stream for all problems

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

26 correct 2 WA on C any idea submission

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

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

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

    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

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

any idea for g?

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

    you only stay in only one cell

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

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

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

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

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

      I considered for max value cell only, will fix it

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

      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.

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

        T <= H * W I suppose so

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

          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 ?

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

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

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

              Alright , Thank you !

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

              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.

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

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

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

what's wrong in my solution of G?

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

    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

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

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

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

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

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

how E?

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

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

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

[deleted]

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

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

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

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

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

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.

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

    G could have easily been a D/E imo.

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

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

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

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

      output:

      Yes
+++++++++S+
+o.o.o.o.o+
+.+-+-+-+-+
+o|o.o|o|o+
+.+.+.+-+-+
+o.o|o.o.o+
+++++++++G+
      → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +29 Vote: I do not like it

      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.

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

    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+

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

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

      Luck is always unpredictable

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

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

Could someone please tell why my D fails ???

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

    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

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

    Use Multiset because element may repeat

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

Can someone say why my Problem D is TLE Submission

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

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

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

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

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

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

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

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

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

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

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

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

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

    That's right!

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

    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.

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

E was such a good problem.

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

    How to do it ?

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

      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.

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

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

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

    yep it's good

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

Why does this TLE ??

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

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.

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

    your articles are good.

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

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

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

      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.

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

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

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

    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 :(

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

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

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

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

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

    you don't need NCK values , you just have to calculate factorials and mod inverse of it

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

OMG i don't know why i did not try to solve G, got stuck in F, when i read G i thought some matrix exponentiation stuff so i left it. i should have tried G

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

Can problem G be solved using Dijkstra's Algorithm?

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

The G is pretty simple than usual rounds:D

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

you should swap between c and d

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

When would the official editorial of the round be released on the website?

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

I think G is easier than E.

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

ok

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

Who has stronger data to help me hack my code for F question please?I have tried all the known strong data.submission

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

Found a test that fails the fastest solution for task G.

1 9 34

1 4

80 28 4 98 84 2 67 57 100

The optimal solution is to take 98 * 34 = 3332, but merhorn's solution outputs 3330

→ Reply