Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).

Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).

as a tester, qwexd ORZZZZ

As a tester, the problems were really good.

Participants, please enjoy the contest!

As a tester, I enjoyed the round and the statements were brief and clear. I hope to see you on the scoreboard!

As a tester, this was the best contest I have ever seen.

As an apparent tester (I don't remember testing this round recently), I'm sure the problems are good :P

Good luck to everyone!!!

Good Luck for every Candidate Master to promote to Master!

OMG South Korean setters, good mathematical problems coming on the way :)

Omg announcement shorter than tourist round

This contest may be a bit late, I guess I fell asleep at that time.

good luck everyone!

As a tester, I tested this round in the period about when I was orange for the first time.

Problems are nice tho!

очередной див 2. желаю всем удач решить его

My first contest was tourist round. I solved 1st 2 problem and earned 389 rating. This will be my 2nd contest .

I will skip an academic seminar in my university and participate in this round.

As a participant, I confirm that i will participate.

Sometimes I really want to skip school.

Please down me, thx.

As a tester, I enjoyed this round. Good luck!

Thanks for your excitation to invite us to participate in round !

Auto comment: topic has been updated by azberjibiou (previous revision, new revision, compare).

Good Luck and Have Fun!

I will skip an academic seminar in my university and participate in this round

Wishing you all a positive delta!!

Best wishes for everyone

Worst Contest I have Ever Seen. What are these strict time limits !?!?

Me after solving C

is that a pattern finding round?

Mo

Starting with problems A Motivation 100 to 50 B Motivation 50 to -100 C Motivation -100 to +50 Depression enters :)

How to solve E? Is this some dp? maybe we can precompute the maximum index, i can jump to from index j while keeping the sum of elements from i to j >= 0 . Am i thinking in the right direction ?

Might be an unpopular opinion, but I think all problems were very good and interesting. Congrats to the authors for a beautiful contest. I enjoyed doing the contest very much. Thanks!

Did someone constantly get wrong answers on problem B?

How to solve C?

How to solve B?

E looks standard. Can it be solved by dp with d&c?

upd: i think i overcomplicated it

C is too hard

The difference between C and D was massive.

did anyone else also got wrong answer on test 5 in E

I think that this round had very interesting problems with pretty beautiful possible solutions. Thanks for the contest!

My solution to problem E:

First, create the prefix sum array $$$p_0 = 0, p_i = a_i + p_{i-1}$$$ and compress it. Let $$$dp_i$$$ denote the best answer for the prefix upto element $$$i$$$. Suppose the last segment we take containing $$$i$$$ goes upto $$$\ell+1$$$ and misses $$$\ell$$$. Then $$$\ell < i$$$ and we must have $$$p_i \geq p_{\ell}$$$, and the best possible answer in this case would be $$$dp_{\ell-1} + (i - \ell)$$$. To efficiently compute these values, create a max segment tree over the compressed $$$p_i$$$ values and each time we compute $$$dp_i$$$ as $$$i$$$ plus the maximum over the segment $$$[0, p_{i}]$$$ in the segment tree and after performing $$$dp_i = \max(dp_i, dp_{i-1})$$$ (in case we don't take $$$i$$$ in the optimum answer) we update the $$$p_{i+1}$$$th location by maximising it with $$$dp_{i} - (i+1)$$$. That's it, done. Overall solution works in $$$\mathcal O(n \log n)$$$.

https://www.youtube.com/watch?v=1jbhevleu-Y Copy of Problem B...Do Something

ABCforces

my total score : 390-8*50.. It looks very difficult, was this contest really hard?

Problem D cost much time for me and I didn't have enough time for E.

2D dynamic programming with 6 different arrays to maintain (RL, RL_sum, LL, LL_sum, LL_cnt, LL_cnt_sum) is too easy to make mistake at some details. I've spent much time to find a bug that I allocated too much space on the stack for 2D arrays (using something like ll RL[n][n], where n=3000) instead of declare them as global variables.

Update: Now my submission 192969220 has been accepted.

#include <bits/stdc++.h>

using namespace std;

char nl = '\n';
char sp = ' ';
using ll = long long;
using vb = vector<bool>;
using vi = vector<int>;
using vl = vector<ll>;
using vvb = vector<vb>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using si = unordered_set<int>;
using sl = unordered_set<ll>;
using tsi = set<int>;
using tsl = set<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using tmii = map<int, int>;
using tmll = map<ll, ll>;
using mii = unordered_map<int, int>;
using mll = unordered_map<ll, ll>;
using pqi = priority_queue<int>;
using pqig = priority_queue<int, vi, greater<int>>;
using pql = priority_queue<ll>;
using pqlg = priority_queue<ll, vl, greater<ll>>;
using pqpii = priority_queue<pii>;
using pqpll = priority_queue<pll>;

#define tp3(T) tuple<T,T,T>
#define tp4(T) tuple<T,T,T,T>

#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define outrange(x,min,max) ((x)<(min) || (x)>(max))

#define nano (chrono::system_clock::now().time_since_epoch().count())
#define second_since_start ((nano-start)/1e9)
#define init_rng mt19937 rng(nano)
#define randint(a,b) ((a)+rng()%((b)-(a)+1))

void yesno(bool a) {
	cout << (a ? "YES\n" : "NO\n");
}

template<typename L, typename R>
ostream& operator<<(ostream& out, const pair<L, R>& p) {
	out << '(' << p.first << ',' << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, unordered_set<T>& v) {
	for (auto &i : v) out << i << ' ';
	out << nl;
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

template<typename K, typename V>
ostream& operator<<(ostream& out, unordered_map<K, V>& m) {
	out << '[';
	for (auto &[k, v] : m) {
		out << k << ':' << v << sp;
	}
	out << "]\n";
	return out;
}

namespace segtree_single_point{
#define sti segtree<int>
#define stl segtree<ll>
	
	template<typename T>
	T lambda_add(T x,T y){
		return x+y;
	}
	
	template<typename T>
	T lambda_min(T x,T y){
		return x<y?x:y;
	}
	
	template<typename T>
	T lambda_max(T x,T y){
		return x>y?x:y;
	}
	
	template<typename T>
	class segtree{
	public:
		segtree(vector<T> &source, T (*merger)(T,T), T defaultValue=(T)0){
			this->merger=merger;
			this->defaultValue=defaultValue;
			int n=source.size();
			int L=1;
			while(L<n) L<<=1;
			size=L;
			vector<T> v(2*L,defaultValue);
			data=v;
			for(int i=0;i<n;i++) data[L+i]=source[i];
			for(int i=L-1;i>=1;i--) data[i]=merge(data[2*i],data[2*i+1]);
		}
		
		void add(int index,T value){
			put(index,data[size+index]+value);
		}
		
		void put(int index,T value){
			_put(size+index,value);
		}
		
		//查询闭区间[l,r]
		T query(int l,int r){
			return _query(0,size,l,r+1);
		}
		
		void show(){
			cout<<data;
		}
		
	private:
		vector<T> data;
		T (*merger) (T,T);
		int size;
		T defaultValue;
		
		T merge(T left,T right){
			return (*merger)(left,right);
		}
		
		void _put(int i,T value){
			data[i]=value;
			if(i==1) return;
			int j=i^1;
			if(i>j) swap(i,j);
			_put(i>>1,merge(data[i],data[j]));
		}
		
		T _query(int L,int R,int l,int r){
			if(L>=r || R<=l) return defaultValue;
			int index=(size+L)/(R-L);
			if(index>=size) {
				return data[index];
			}
			if(L>=l && R<=r) {
				return data[index];
			}
			int mid=(L+R)>>1;
			T ans=defaultValue;
			if(r>L) ans=merge(ans,_query(L,mid,l,r));
			if(l<R) ans=merge(ans,_query(mid,R,l,r));
			return ans;
		}
	};
}

using namespace segtree_single_point;

const int MAX=200005;
ll a[MAX];
ll sum[MAX];
int dp[MAX];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int _t=1;
//	cin>>_t;
	while(_t--){
		int n;
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>a[i];
		}
		sum[0]=a[0];
		for(int i=1;i<n;i++){
			sum[i]=sum[i-1]+a[i]; //prefix-sum
		}
		// assign the indexes of different values of sum[i] in the segment tree
		vl sums;
		for(int i=0;i<n;i++) sums.push_back(sum[i]);
		sort(all(sums));
		mll inv; // we use this map to find the index from a prefix-sum value
		for(int i=0;i<n;i++){
			if(i>0 && sums[i-1]==sums[i]) continue;
			inv[sums[i]]=i;
		}
		
		vi v(n);
		for(int i=0;i<n;i++) v[i]=-1e9;
		sti st(v,lambda_max,-1e9); // initialize the segment tree with size n and 
		//initial value -inf, query the range maximum
		dp[0]=(a[0]>=0)?1:0;
		st.put(inv[sum[0]],dp[0]);
		for(int i=1;i<n;i++){
			int index=inv[sum[i]];
			if(sum[i]>=0){
				dp[i]=i+1;
			}else{
				dp[i]=max(dp[i-1],i+st.query(0,index));
			}
			st.put(index,max(st.query(index,index),dp[i]-i));
		}
		cout<<dp[n-1];
	}
}

Was D just a DP on pos[previous][current] then looping through [current+1, n) to try placing the next particle?

The observation there I believe is that for all values <= a[i] + (a[i] — a[p]), the direction is left, while the rest are right, so you can do some casework there to add on that subarray after precomputing prefix sums (the number of dots is equal to the number of adjacent RL's that show up in the final subsequence), but I had a stroke implementing ;-; does anybody have a simple enough implementation of that idea?

B was much more difficult than C In B only case we need to worry about is n%20==19 but even after that it was more of implementation problem than maths which it seemed to be initially

Feels like massive cheating on C, I might be wrong but it feels like it.

What is test 2 for B?

guessforces

Any proof for C I solved it by just some observations

The worst round

Imagine asking how to solve D and getting -13 ^D

It was great PatternForces Round <3

I wish C was 1500-1600, but unfortunately it's more likely to be 1200

Anyone know why my sol for D is wrong?

dp[i] stands for sum where i is chosen, and tot[i] is total of chosen & not chosen

dp[0] = 1;
tot[0] = 1;
for (int i = 1; i < n; i++) {
	dp[i] = 1;
	for (int j = 0; j < i; j++) {
		if (j == 0) {
			dp[i] = (dp[i] + 1) % mod;
		} else if (x[i] - x[j] < x[j] - x[j - 1]) {
			dp[i] = ((dp[i] + tot[j - 1]) % mod + mod_pow(2LL, j + 0LL, mod)) % mod;
		} else {
			dp[i] = ((dp[i] + dp[j]) % mod + mod_pow(2LL, j + 0LL, mod)) % mod;
		}
	}
	tot[i] = (tot[i - 1] + dp[i]) % mod;
}
cout << (tot[n - 1] - n + mod) % mod << '\n';

I wast stuck in problem C for approximately 2 hours, In problem C multiple kind of pairing was possible so it must be mentioned in the question that we can output any valid answer. I am not talking about order of pairs... actually you can pair any number with 2 values and accordingly I found 2 valid answer exists for each odd number.

Any Hints For D? I Was Thinking In A DP Direction :(

Toooooooooooooo much Cheating

Can anyone explain E for noobs?

Why is answer no for even n in C?

An unbalanced round. I got ABC very quickly, but couldn't come up with a fast enough solution for D in time and didn't attempt further problems. I won't say that the problems were bad because they weren't (C was just guessing a pattern, didn't like it that much; others were good). I just think that there should've been a 1600-1800 rated problem between C and D. But the round was still nice.

Actually had more trouble with C than F haha.

solved D during the contest, but forgot that modular arithmetic template takes $$$O(\log n)$$$ to calculate $$$2^n$$$... So got TLE couple of minutes before the end after simply rewriting formula I got on paper :(

contest submission: https://codeforces.com/contest/1788/submission/192959799

upsolve submission: https://codeforces.com/contest/1788/submission/192968394

Great contest with good problems , thanks!

Great contest, and super fast rating changes, wow! Absolutely loved all the problems that I read (A-E)!

Also, while I understand the need to have tight TLs on D, as $$$n^3$$$ solutions were to be rejected, I'm slightly irked by the fact that my Java submission failed despite being $$$n^2log(n)$$$. Anyway, that was to be expected since I was using TreeMaps, and Binary Search is understandably faster. So yeah, happy to have learned one more thing :)

Great contest with very clear statements!

ok thanks

AC submissions at the last second

Ac submissions at the last second is very nice , but i am pretty sure that last second submission of problem D by gsmdfaheem is copied. i have seen exact same code that is leaked at just 10 minutes before the contest end.

he just changed the variable names.

In B if i print 1 as 01 it consider it wrong but both are equivalent integers and no intructions are provided regarding leading zero .

stupid testing got WA 2 times.

According to me my E is working but my solution gets WA on test 5 can anyone please help me where i am lagging https://codeforces.com/contest/1788/submission/192944044

GOT AC LAST SECOND

D just 3 seconds before!!

The time limit of F is too tight. I wrote the correct solution but got TLE on pretest 58. I think it's better to decrease the value of $$$n,q$$$ to 1e5 or increase the tl to maybe 5 secs.

Problems are fun! thanks to authors :)

Can someone give a small test case on which my solution 192923926 fails?

Very very very standard problem E and F. I cannot accept that.

Weak testcase in B no. In the statement, given 1<=n<=1e9. Unconciously, I used int(as datatype) and passed the pretest. After the contest I noticed my mistake and expected to get wrong answer. But, after final judgement , my solution passed all the testcase :)

192907426

Great contest! you can find the video editorials for problem C and D here .

hope this helps you! happy coding!

Hello! I submitted two implementations of treap in E, and the "faster" version works 5 times longer! Can anyone explain it? "slower": 193052447 "faster": 193052503 I know that "faster" gets TL on a test with a = {0, 0, 0, ..., 0}, but I can't realize the reason of O(n) height of a treap.

hopeforces

Lately I receive a message that my submission 192896600 is same as 192935411.I cheked it and find that his solution to the problem is different from mine.I guess may be comments at the end of the code is the reason why two submissions is thougt as same.

In addition, I can give evidence that I used this template before him. mine:188824606 his:189071540

[user:KAN][user:MikeMirzayanov][user:azberjibiou]