Nice Editorial by the looks of it... I mean the explanation seems thorough

Well, B was harder than usual Div2 B.

Really the explanation is superb.

Well, the working of D was googleable. You just need to connect and implement.

Link to the site: https://www.codechef.com/wiki/tutorial-expectation (Q3).

Thanks for your fast & detailed solution <3

Thank you for the great solutions. (I love the problemset)

Pls help. I did the problem C with almost exactly the same algorithm (which is O(n^2)), but got TL many times. Submission.

Is this a std::vector slow or what?

P.s. I even did an initialisation to vector before operating with digits

The observation for problem B was very critical relating to problem statement. But I think problem C was easier as it was greedy implementation problem.

I really liked problem D. Thanks for the contest :)

I would admit B is an interesting problem, but it's way harder than a typical Div.2 B problem. Well, at least it's a good lesson about my mentality adjustment. I still can't overcome the frustration about can't solve easy(at least in my mind) problems during the contest (:」∠)_

This contest was tough!!

Nice ProblemSet, Editorial !

Everyone solved problem C assuming that it is always optimal for us to choose the right triangle. But how do we prove it? The statement said at least one side of the triangle should be parallel with one of the sides of the board. So we can have other types of triangles as well. djm03178

In problem E, I failed this problem in test 2, 14th testcase. System said I responded 3, but it expected 2. However, I debug the same code in code::blocks, it printed 2. I think the Testing system has error.

E번 문제 두 번째 테스트 14번째 케이스에서 정답이 2이고, 코드블럭에서 똑같은 코드에 똑같은 테케를 넣어본 결과 2를 대답했는데, 3을 대답해서 틀렸다고 나옵니다. 시스템 오류가 있는 것 같습니다.

Problem B was not easy for us!

I did a very stupid mistake in B.
For n = 2 answer will be 0 but I don't know what came to my mind, I printed their difference.
Sadly that case wasn't in the pretests.

Here is an easier solution for E:

Just binary search the answer $$$K$$$ and let $$$DFS(Node)$$$ return the minimum difference in height between this node and the last node you ate a snack from.

If all the children return difference in height $$$\lt K - 1$$$ just return the minimum meaning the last child you will visit is the one with minimum difference in height.

If one of them has difference in height equal to $$$\ge K - 1$$$ return it.

If more than one of them has difference in height equal to $$$\ge K - 1$$$ then there is no answer.

In the end just check that $$$DFS(1) \le K$$$.

Can someone explain D with a bit more mathematical proof? For the sequence 1 0 1 what are the expected number of tries for each stage?

I tried E but I dont know where its wrong.

can someone point out my error https://codeforces.net/contest/1453/submission/100387883

My O(n^2) C gives TLE -_-:

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const ll maxn=100005;
const ll mod=1e9+7;

int main(){
	fast;
	ll t,n,i,j,k,d;
	cin >> t;
	while(t--){
		cin >> n;
		int gr[n][n];
		for(i=0;i<n;i++){
			string s;
			cin >> s;
			for(j=0;j<n;j++){
				gr[i][j]=(s[j]-'0');
			}
		}
		vector<ll> av;
		for(d=0;d<10;++d){
			vector<pi> v;
			ll ans=0;
			for(i=0;i<n;i++){
				for(j=0;j<n;j++){
					if(gr[i][j]==d){
						v.pb({i,j});
					}
				}
			}
			for(i=0;i<v.size();++i){
				for(j=0;j<v.size();++j){
					ll a = v[i].ff;
					ll b = v[i].ss;
					ll c = v[j].ff;
					ll d = v[j].ss;
					
					ans=max({ans,a*abs(b-d),c*abs(b-d),abs(n-1-d)*abs(a-c),abs(n-1-b)*abs(a-c),abs(n-1-c)*abs(b-d),abs(n-1-a)*abs(b-d),b*abs(a-c),d*abs(a-c)});
				}
			}
			av.pb(ans);
		}
		for(ll x : av)
			cout<<x<<" ";
		cout<<"\n";
	}
}

B was harder than usual...!

During the contest I had the same idea for E as the editorial, but I couldn't see why it is always optimal to choose the child that has the shortest 'moving back' distance. I'd like to know if there is an easy proof/intuition for this.

It should be forbidden to write an editorial for that C without drawing a picture.

Wow... all codes are short!

Thank you for B, I learnt something new.

Irrespective of how much I f***ed up in the contest , I want to say that the problems are beautiful. I learnt a lot. I will practice harder. Thank you for such a nice contest.

my this WA solution and this AC solution is almost same, just diff is i am using log2 operator instead of another loop, why its wrong then???????

Okay this is probably silly, but help me out a bit.

To my understanding, I derived the following,

Assertion : In a sequence of length $$$k+1$$$, where the 1st and last characters are 1 and rest are zero. The expected number of tries to reach (not beat) $$$(k+1)^{th}$$$ stage from $$$1^{st}$$$ stage is $$$2^{k}$$$

With this assertion, I did the following, for an input x, subtract 2 (Since we need this to exit the last stage) and now for $$$k^{th}$$$ set bit, append sequence $$$1(0)^{k-1}$$$. And finally append $$$1$$$.

However for $$$8$$$, my algorithm prints $$$1011$$$, $$$2^2$$$ (beating 1,2) to reach $$$3^{rd}$$$, then $$$2$$$ beating $$$3$$$ to reach $$$4$$$, and finally beating $$$4^{th}$$$ with $$$2$$$ itself to win. A total of $$$4+2+2=8$$$.

It would be very helpful if someone could point out where I am wrong.

.

Thanks for the great problems.

For E, I keep getting runtime error for a pure dfs solution.

Looking at the submissions, it looks like only two solutions in PyPy3 were accepted, and each of these does dfs 'non-recursively' (by a bfs first), e.g. https://codeforces.net/contest/1453/submission/100385834

Could someone explain why a pure dfs solution gives a runtime error? Many thanks.

can someone please tell why this gives tle but this is Ac .

only difference between them is that the Ac code does not have the line #define int long long

Personally, I think that this is one of the most interesting contests in a long time. I enjoyed solving these problems a lot, especially problems B and E.

For E: it's too **boring** to find the sub-maximum in linear time, so just sort the candidates and it will be O(nlogn) for each test case.

More like: it's too **tedious** ...

Can anyone hack my O(n^3) solution for F? 100403925

Can anyone provide me the explanation of third case in editorial of B. abs(ai-ai+1)+abs(ai-ai-1)+abs(ai+1-ai-1).I am not able to understand why we are doing this.

The problems were great. Thank you, djm03178. But I totally messed up this round. :(

if i am not hungry, i could solve F and become master

B was hard enough

Deteailed hindi video tutorial from A to E and thought process here

B problem was fun to solve! Thanks for such questions :)

For the triangles problem, I had the same approach and as n=2000 it should have worked for n^2. But it gave me TLE on the 5th pretest. Someone please tell me where I went wrong. Thanks in advance

100388093

Can someone explain how the max area*2 is 42 for digit-9 in this testcase 42987101 98289412 38949562 87599023 92834718 83917348 19823743 38947912 Any help is kindly required :(

As a matter of fact, the problem C is a little boring.
But overall, the contest is pretty good.
Thanks for the contest

Nice tutorial and problem set. Thank you.

This was by far the best editorial on codeforces according to me.

B was more tuff than usual but thanks for the explanation really helpful :)

can someone help me, i keep getting wrong ans on test case23 on test no 5. i have done something similiar to the first strategy in the editorial .

I find the sum of the gp of 2,4,8... which is just smaller than n and take those many zeroes and then subtract that sum from n and then the dif becomes the new n and i do this recursively till the dif is zero.

I even took the test case and found that the expected value was same as the number given .

Any help is much appreciated 100441237

Solution for prob B I found this video really helpful.

for the first time, I will say the tutorial is awesome. I am learning a lot.

F is cool, thanks

For problem B, if you know before the contest that the basic solution (in case of no replacement) is : $$$\sum_{i=2}^n abs(a_i - a_{i-1})$$$. Then it's probably easier to solve it as you can reason about this equation.

Is it part of a common knowledge that experienced competitive programmer have ?

Video Tutorial for E

Can anyone help me with this problem

For Problem F, 1453F — Even Harder, my O(n**3) DP solution passed. I didn't try to optimize the code, just wrote the simplest version for my DP expectig it will TLE and I will have to optimize my code to O(n**2). http://codeforces.net/contest/1453/submission/100570074 Although the solution is O(n**3), I am having difficulty in coming up with a test case which will trigger TLE on my solution.

Can anybody please explain the general equation derived in question D.I cannot get it please

can anybody please explain the main idea of solution used in problem E DOG'S SNACK

The problem D is very useful. I hope to conduct more value contests.

It took us one month to prepare a video solution for problem B :) If it is still interesting to anyone, please consider:

Alternate $$$O(N^2.\log{N})$$$ dp solution for problem F using a segment tree: link

The basic idea is to maintain n segment trees, and ith segment tree stores that if point i is the second point chosen, then all j > i, store the total answer if point i is chosen as the second point and j is chosen as the third point. This works because we only need to maintain information for the first two points, and rest of the chosen points will inductively be valid.

Note to self: Write explanation later.