As a participant I hope to get 1300+ rating or even better, Specialist

Also Happy Birthday Max, sending you best wishes

As a tester I recommend you to take part in this beautiful round

As a tester, I can say that the tasks are cool and interesting

As a tester, I wish Max all the best on his birthday! Also, round is going to be fun, trust me ;)

p.s. имя нам улей

Is this rated? Please dont downvote. Tomorrow is my birthday.

As a tester good luck! You will need it

As not a tester good luck!

As "еритв" I also recommend you to participate in this round!

P.S. Имя нам улей

happy birthday Max

may i reach my Max rating in this contest

Happy birthday to bro Max

As a tester I recommend you to take part in this round!

Can I hope ......

as a tester, I can say that the round is interesting, I recommend participating

as an author, i recommend you this round!!

Feliz Cumpleanos Max!!! I express my deepest regrets for not being able to participate in the round for I am participating in the Teamscode competition which unfortunately has overlap w/ this round. :/ GL to everyone!!!

as someone who just saw this announcement, it might going to be a good round. GL on the round guys!

What is meant by “All of the problems are original” ?

Happy birthday to Max!

dori dori dori dori

As a tester, this round is mid and I don't recommend to participate.

As A participant I wish to reach Expert hopefully, and Happy 30th Birthday to Max <3

Happy Birthday Max!! Best wishes!

Happy birthday to Max!

how to have huge postive delta:)

A very Happy Birthday to Max.

I hope he gets Max happiness and we all get Max positive delta so that we can have Max smile on our faces after the contest and practice at our Max level to surpass our Max rating.

As a tester I recommend you to take part in this round!

As a participant I hope to get 1200+ rating or even better, Pupil

Thanks for this round and good luck to everyone!

as a normal person, please downvote me

Happy Birthda ，Max！

Happy B-day Max

As a participant, hoping to be pupil this time. Also Happy birthday Max best wishes from my side too.

As a participant, I hope to get a rating of 1200+ to become a pupil. Guys, please suggest ways to improve my logic-building skills.

Happy Birthday, MAX, wish you all the best in your future endeavors.

As a regular participant I hope I reach 1200+ rating...

Thanks for the round.. Looking forward to it.

As a participant, I hope to become pupil.

Also Happy Birthday Max.

Max is lucky to have a cousin like induk_v_tsiane. Happy Birthday, Max, Best wishes to you.

As a tester, I recommend everyone to participate in this round. The tasks are interesting. I wish you all good luck and positive delta.

Happy birthday, Max!

Happy birthday Max !

The score distribution is very nice and hope that the tasks are cool and interesting.

Also Happy Birthday Max, sending you best wishes <3

☠️☠️☠️

Happy BirthDay Max !.Wish you the best.

Happy Birthday MAX. I wish you the best. And wish me that i can reach my MAX rating by participating in this contest.

Happy birthday to MAX!

I'm hoping for a big negative delta to celebrate my birthday too(((

Happy Birthday, Max. Best wishes to you.

Hope my fever goes down so i can participate.

Also,best wishes to Max.Have a great day.

Hope u guys have a good "fate" round.

buru nyuu

Happy Birthday Max,sending you best wishes

I hope to get Candidate Master rank before the first day of my 3rd semester which will start 2 days after this round :)

And also.... happy birthday max ^_^

UPDATE: I failed :(

All the best to all my friends.....

Hope to solve 3 question in this contest.

Hope, this day, Max, will help everybody to reach their MAX rating)

wish u good luck and happy 30th birthday!!

Happy Birthday, Max c:

Happy Birthday Max:)

good luck & have fun

Happy Birthaday Max, Sending you best best best wishes

Looking forward for the contest desparately...

Also, Happy Birthday Max Tell him we sent virtual hugs :)

Happy birthday Max!

Lets Goo. My first coding contest ever. So anxious and excited at the same time

Dear Max, Warmest congratulations on your birthday! I hope this special day brings you immense joy, wonderful memories, and a year filled with success and happiness. Wishing you all the happiness your heart can hold. Warmest regards, Faizullakh, Dilettante_786

Who is Max?

As a participant I just hope to get rated and nothing else

Also Happy Birthday Max, sending you best wishes

can anyone tell me, if there is any correlation between the question's score and rating? A score of 1000 means, the question is around 1000 rating difficulty level?

As a participant I hope to get 1600+ rating or even better,Become first time Expert.

As a participant I hope to get 1800+ rating or even better, Candidate Master

Also Happy Birthday Max, sending you the best wishes

puranyaa

AGC Codeforces ?

It was a nice contest. Hoping to become Candidate Master in my next one. : )

Good visible tests! Really helpful. Hope pretests are good too.

-clear statement -nice problem that's a perfect contest , thanks to the organizers

How to solve C?

Segment tree for E?

Speedforces

It was hard D for me,but easy for others :(

New OEIS sequence when

Is it just me or was that round way harder than usual?

How to solve D?

Nice contest, hope to become expert this round!

Hi guys, I have a question that need your help.

Example with problem B, my idea: sort all arrays (A[n]), and the result is sum of second element each array (sum (A[i][1]), 1<=i<=n) (except the min — A[i][1] with 1<=i<=n), and the min value of all elements.

I tried to solve this problem with 3 — 4 wrong times answer. In each try, I realize something, and test the output with codeforces system, when wrong, I find some test cases, realize something (or not), and solve again. So, I cannot prove some problems I solved, like problem C. What happened with me! How can I improve my algorithm?

Also HappyBirthday Max.

how I solved C

   vector<int> p(10);
   iota(p.begin(),p.end(),1);
   auto get = [&](vector<int> q)->i64{
      int mx = 0,sum = 0;
      for(int i = 0;i < 10;i++){
         sum += q[i] * (i + 1);
         mx = max(mx, q[i] * (i + 1));
      }
      return sum - mx;
   };
   do{
   	if(get(p) == 303){
   		for(int i = 0;i < 10;i++){
   			cout << p[i] << " ";
   		}
   		cout << "\n";
   	}
   }
   while(next_permutation(p.begin(),p.end()));

output: 1 2 3 4 5 6 10 9 8 7

Are there any hacks for problem F? I got Wrong Answer on Pretest 3.

I have no idea how to solve A, but I know how to solve F:

First, let's notice that we will take courses at most $$$logmaxW$$$ times because after that time spent on traversing a road will be equal to $$$1$$$. Also, all courses will be taken in the first possible city/node (to minimize time spent on the rest of the travel). I have precomputed with binary lifting:

$$$up[i][j] -$$$ $$$2^j$$$-th ancestor of node $$$i$$$

$$$cnt[i][j] -$$$ the number of nodes $$$u$$$ on path from node $$$i$$$ to the $$$2^j$$$-th ancestor of $$$i$$$ such that $$$s[u]=$$$ '$$$1$$$'

$$$sum[i][j][k] -$$$ time spent on traveling from node $$$i$$$ to $$$2^j$$$-th ancestor of $$$i$$$ if the skill is equal to $$$c=2^k$$$ all the time (without including the time needed to take that $$$k$$$ courses).

Let's define $$$f(u,v,k) -$$$ time spent on traveling from node $$$u$$$ to node $$$v$$$ if the skill is equal to $$$c=2^k$$$. This can be calculated in $$$O(logn)$$$ using arrays $$$up[i][j]$$$ and $$$sum[i][j][k]$$$.

For answering the query ($$$a,b$$$), we will find the necessary time to travel from $$$a$$$ to $$$b$$$ for every $$$k$$$ from $$$0$$$ to $$$logmaxW$$$, where $$$k$$$ will be equal to the number of taken courses. For each of the results, we need to find the first node $$$u$$$ on the path from $$$a$$$ to $$$b$$$ such that $$$s[u] =$$$ '$$$1$$$' and the closest node $$$v$$$ to $$$a$$$, but not on the path from $$$a$$$ to $$$b$$$, such that $$$s[v] =$$$ '$$$1$$$ and the result will be equal to $$$min(k \cdot T + f(a,u,0)+f(u,b,k),k \cdot T + f(a,b,k))$$$ Final result will be the minimum of this results. Overall time and memory complexity are equal to $$$O(nlognlogmaxW)$$$.

I solved C by pre-computing and saving the answers :)

Edit: I also forgot to congratulate Max, HBD Max :D

so disappointing when u are rank 2 15 min in the contest and now ur rank 500 at the end cuz some stupid mistakes... got a little positive delta though, nice little birthday present:P

I mistakenly read the meaning of problem B and got stuck for a long time.

Anyway, thank you for holding this high-quality round!

218576719 For A problem , can someone please tell me why am I getting runtime error(at pretest 1), even when this code runs fine in my sublime text.

Can anyone help me with what's wrong with this code for problem D? My basic idea was to sort the segments and stitch them together and finally apply a binary search for each xi to see in which stitched segment it lies.

#include <bits/stdc++.h>
using namespace std;

#define ANAND ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rep(i, m, n)  for (ll i = m; i < n; i++)
#define DEBUG(x) cout << "debug: " << x << "\n"
#define PRINT(x,n) rep(i,0,n) cout << x[i]<< " "; cout << "\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"

typedef long long ll;
typedef vector<ll> vec;
typedef pair<ll,ll> pll;
typedef vector<pll> vecp;
struct Foo
{
  ll x, y, z, w;
};
struct G {
	ll l, r, b;
};

bool operator<(const Foo& lhs, const Foo& rhs)
{
  // assumes there is a bool operator< for T
  return tie(lhs.x, lhs.y, lhs.z, lhs.w) < tie(rhs.x, rhs.y, rhs.z, rhs.w);
}

ll GCD(ll a, ll b){if (a == 0)return b;if (b == 0)return a;return GCD(b, a % b);}

// map<ll,ll> ok;
void SOLVE() {
	ll n;
	cin >> n;
	vector<Foo> v(n);
	rep(i,0,n) {
		ll l, r, a, b;
		cin >> l >> r>> a>> b;
		Foo ok;
		ok.x = l; ok.y = r; ok.z = a; ok.w = b;
		v[i] = ok;
	}
	sort(v.begin(), v.end());
	vector<G> pre;
	ll l = v[0].x,r = v[0].y,a= v[0].z,b = v[0].w;
	rep(i,1,n) {
		if (b >= v[i].x) {

			b = max(v[i].w, b);
			r = max(r, v[i].y);
		} else {
			G ok;
			ok.l = l; ok.r = min(r, v[i].x); ok.b = b;
			pre.push_back(ok);
			l = v[i].x;
			r = v[i].y;
			a = v[i].z;
			b = v[i].w;
		}
	}
	G ok;
	ok.l = l; ok.r = r; ok.b = b;
	pre.push_back(ok);
// 	cout << "===\n";
// 	for (auto& h: pre) {
// 		cout << h.l << " " << h.r << " " << h.b << "\n";
// 	}
// 	cout << "===\n";
	ll N = pre.size();
	ll x;
	cin >> x;
	rep(i,0,x) {
		ll val;
		cin >> val;
		ll L = -1, R = N;
		bool flag = false;
		while(L <= R) {
			ll mid = (L+R)/2;
			ll ol = pre[mid].l, oo = pre[mid].r, ob = pre[mid].b;
			if (mid >= N || mid < 0) break;
			if (val >= ol && val <= oo) {
				cout << max(val, ob) << " ";
				flag = true;
				break;
			} else if (val <= ol) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		if (!flag) {cout << val << " ";}
	}
	cout << "\n";
}

signed main() {
	ANAND;
	
	ll _;
	cin >> _;
	while(_--) {
		SOLVE();
	}
	return 0;
}

Problem A: You can just sort the array. Find the subarray starting from the first element, ensure that all elements of the subarray are equal, and just print the subarray. The next part will be for array C.

Problem B: Just store the first and second minimums from all arrays. Then sort the stored values. The ans will be first [0] + second [1] + second [2]...+second [n-1]

Problem C: Create a permutation of size n. Then use a for loop. Reverse the given sorted permutation for j = i to n. Calculate and store the maximum of all n possible answers.

I hope it is helpful.

Hello, I would like to report an issue on question 4. Basically, I ran the code on two different online C++ compilers. For the first test case, I got the correct results on those sites. However, when I run the same exact code using CodeForces, these are the results it is giving.

14 14 23 15 28 22 
14 14 14 14 22 1967396643 14 14 15 
7 8 7 
15 14 14 30 24 17 31 4 8 
32 32 32 5 8 1967396643 4 32 

I am losing my mind because I have no clue where this random large numbers are coming from in 2nd and 5th lines. Can someone either explain or if CodeForces admin thinks this is a mistake on their side, can I get the credit for the problem?

Here's my code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
using namespace std;


int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        pii arr[n];
        for (int i = 0; i < n; i++) {
            int l,r,a,b;
            cin >> l >> r >> a >> b;
            arr[i] = make_pair(b,l);
        }
        int q;
        vector<int> original;
        vector<pii> queries;
        queries.clear();
        cin >> q;
        for (int i = 0; i < q; i++) {
            int x;
            cin >> x;
            queries.push_back(make_pair(x, i));
            original.push_back(x);
        }
        sort(queries.begin(), queries.end());

        sort(arr, arr+n);
        vector<pii> brackets;
        pii currbracket = make_pair(-1,-1);
        for (int i = 0; i < n; i++) {
            if (currbracket.first == -1) {
                currbracket = arr[i];
                continue;
            }
            pii currele = arr[i];
            if (currele.second <= currbracket.first) {
                currbracket = make_pair(max(currbracket.first, currele.first), min(currele.second,currbracket.second));
                if (i==n-1) {
                    brackets.push_back(currbracket);
                }
            } else {
                brackets.push_back(currbracket);
                currbracket = make_pair(-1,-1);
                if (i==n-1) {
                    brackets.push_back(arr[i]);
                    break;
                }
                i--;
            }
        }
        int ans[q];
        int index = 0;
        for (int i = 0; i < q; i++) {
            int currquery = queries[i].first;
            while(index < n && currquery > brackets[index].first) {
                index++;
                continue;
            }
            if (index >= n) {
                ans[queries[i].second] = original[queries[i].second];
            } else {
                if (currquery < brackets[index].second) {
                    ans[queries[i].second] = queries[i].first;
                } else {
                    ans[queries[i].second] = brackets[index].first;
                }
            }
        }
    
        for (int i = 0; i < q; i++) {
            cout << ans[i] << " ";
        }
        cout << "\n";
        
    }
    return 0;
}

Thanks for this great round, Also Happy Birthday Max

how to solve E?

is there a way to prove and solve C without resorting to brute force with next_permutation and print? What happen if a certain language doesn't have next_permutation like C++?

If it's not easy to prove and much easier to observe by brute force then it's total BS

Yay! Hello expert for the third time. Why is my performance so inconsistent? :(

Thanks for this great round that is full of ideas .

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

I'm new to the platform, don't know how it works completely but solution like this should be illegal right? 218544590

might be one of the most trash solutions of A, but i solved it using scc (strong connectivity components). I built a graph where edge uv meant v % u = 0 and get all scc using Kosaraju algorithm. Then, if there is just one component, there's no solution; otherwise we can put the last component (in topological sort of condenced graph) into c-array and other components into b-array.

I thought those with rating above 2000 don't read whole problem and just go through the code just by reading Input/Output section. And that mistake costed me time and patience -_-

In first problem I submitted without knowing that I was supposed to print the size of array B & C (How dumb can I Be :( .. ) Still hope to get +ve delta

And can someone explain how to apply BS in D? I tried but it was too new way to implement that I failed. Please explain :)

Thank you for this contest!

Can anyone provide their lazy segtree implementation to D?