Please don't do that, don't give me hope :)

Do you want to get more contribution?say "as a"?

He couldn't complete his sentence. Perhaps some big stone fell on him while he was typing. Sad.

yes same

i tried everything to find my interests and nothing felt like i enjoy doing them

as i started CP on codeforces 2 months back i feel like this is all i want to do for the next large amount of my time :) really thankful to the best internet community

so Madara Uchiha saved you, huh.

educational=(4problems or more)*adhoc XD

what is adhoc?

cout << "YES\n";

those who dont want jobs out of it will loose hope soon

hope i remain specialist today:)

hope i will become master one day:)

hope

Are you planning to cheat?

There was but it got deprecated: HackForces. Now it's only present on Topcoder with name TopHacker.

MathForces!

And a forth: MathForces...

come on!

This feels deep. You have my upvote sir

This is the most relatable meme I've seen on codeforces. Especially after yesterday's contest and today's.

before contest i was confident that i will be successfull in protecting my specialist badge. after contest i am confident i will be successfull in getting demotion to pupil

Yeah, but I thought C and D made up for it!

Fu**ing B costed me 7 WA because of floats.

I solved C considering three cases:

1. If we are at index 0, we only have one option, i.e. to start a cycle from here.

2. If we are at the last index, we only have one option, i.e. to end the current cycle.

3. If we are at an index in the middle: We check if b[index+1] == a[index+1].

• If this is true, then we need to terminate the current cycle and start a new one
• We again have 2 options here. We can either continue the current cycle with the existing length summed with the Number_of_vertices[index] - 1 - (b[index+1] - a[index+1]).
• The next option is to start a new cycle from here with length b[index+1] - a[index+1].
• The reason why this is always true is that the rest of the cycle remains unaffected by the choice we make at this index.
• Another option is to terminate the current cycle here after adding Number_of_vertices[index] - 1.
• Remember to add 2 every time you expand the current cycle to count for the edges used to link the chains together.

Link to code: https://codeforces.net/contest/1476/submission/105933562

You can use some dp to store maximum length cycle including all vertices of a[i] as ans[i].

See my solution:https://codeforces.net/contest/1476/submission/105907608

It can be solved by dp; firstly, let dp[i] denote the longest length at ith chain, "the longest length" means the longest length you can get before the cycle is formed, so we can get dp[i]=max(dp[i-1]+c[i]-1-abs(a[i+1]-b[i+1])+2,abs(a[i+1]-b[i+1])), then we update the answer by dp[i-1]+c[i]+1. one thing to be noticed is that when a[i+1]=b[i+1], dp[i] should set to 0.

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define FULL(x,y) memste(x,y,sizeof(x))
using namespace std;

const int N=100005;
int t,n;
ll c[N],a[N],b[N],dp[N];

int main() {
	cin>>t;
	while(t--) {
		cin>>n;
		for(int i=1;i<=n;i++) cin>>c[i];
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>b[i];
		for(int i=1;i<=n;i++) {
			dp[i]=0;
		}
		ll ans=0;
		dp[1]=abs(a[2]-b[2]);
		for(int i=2;i<n;i++) {
			dp[i]=max(dp[i-1]+c[i]-1-abs(a[i+1]-b[i+1])+2,abs(a[i+1]-b[i+1]));
			ans=max(ans,dp[i-1]+c[i]+1);
			if (a[i+1]==b[i+1]) {
				dp[i]=0;
			}
		}
		ans=max(ans,dp[n-1]+c[n]+1);
		cout<<ans<<endl;
	}
	return 0;
}

I thought so, but after seeing that the length of the chain can be 1e9, I knew it wasn't a graph problem.

Yes, C isn't greedy.

I solved it using greedy.

Note that the structure of the graph only depends on the parity of time elapsed. Therefore, we can use $$$(node, parity)$$$ as stage and use DSU to maintain the reach-ability between stages and the sizes of connected components.

Make a left_c and a right_c array which represents the maximum number of cities city i can traverse that lie strictly on it's left and it's right respectively.

Then, notice that if there lies a path b/w city i and city i-2, then city i can traverse all those different cities that city i-2 can because at time t and time t+2, all paths are exactly the same. If there just exists a path b/w city city i, and city i-1, then increment one to the left_c array for the city i. And, do similar things for right_c.

Answer for the i_th city is left_c[i]+right_c[i]+1

You can check my submission

take range of get the smallest number x with x*n >= k

or if n > k : x*n >= ceil(n/k)*k

I had a terrible day too!

At least some previous contests had interesting problems I could not solve and I got negative delta, but this one was Painfully pointless to me :(

the division with 1 huh? Yes it took me some time as well. But no worries mate I lost 1 hour on C not because I could not find the solution but just because I forgot a simple 'else' statement. Look at my submissions on C if you don't believe. Like what separates the successful from the unsuccessful I believe is just the ability of removing the blindness effect that I don't even know what casts it upon us. It's like we are in a MOBA arena and we have a passive ability of getting blinded for 1 hour randomly. We can be blind friends together hit me up if you ever want us to do a Virtual Contest together and then laugh at our blindness.

Bro how did multiplying by 100LL instead of 100 get the answer in B ?

Who is copying?

Same here

I thought the same but dismissed it quickly because how is that not TLE? Each string can match to potentially all $$$m$$$ patterns. So $$$O(m^2)$$$ sized graph (or DAG) right there? The only explanation I can think of is that maybe because of the contraint that each pattern is distinct this bound can be tightened? Do you have the proof?

EDIT: Oh got it. smh. Each string can only match to atmost 16 patterns (because of distinctness constraint) so size of graph is bounded $$$O(m)$$$.

Yes, and the answer is the topological sort of the DAG.

The dp seems to be off by one, since the indices go up to $$$n$$$ (as there are $$$n + 1$$$ cities).

I still didn't understand the problem. Can you explain it?

Yeah I wouldn't understand if there were no sample testcases.

Integer overflow

Mo's algorithm

only $$$O(\sqrt n)$$$ different values in the cnt array, so then apply Mo's algorithm to it and use a list to maintain different values in cnt, and then for each query take out all values and brute force

total complexity is $$$O(m\sqrt n\log n+n^{5/3})$$$.

your last nodes can be in first chain.It means your cycle can't go above it.

try to use multiplication instead of division in check, that can be a problem.

Take a look at this comment

If there are multiple $$$p_i$$$s match the same $$$s_j$$$, then the specified constraint is basically implying the specified pattern exists before all other $$$p_i$$$s. Thus, we can keep track on the indices of patterns and build a dependency graph based on the constraints. For any specific $$$s_j$$$, there would be at most $$$2^k$$$ distinct patterns matching it. Thus, at most $$$2^k$$$ edges would be added to our dependency graph. Hence, the problem is reduced to check if a given directed graph with $$$n$$$ vertices and at most $$$m\times 2^k$$$ edges is acyclic, and if so, report any topological order. This can be solved by topological sort.

There are a few trivial cases to notice, like the specified pattern not matching the given string or different occurrences of the same string being matched by different patterns, you may refer to my submission 105914103 for implementation details.

Try 1 2 1 1 1000000000