It was really nice round. Wish everyone's rating to increase.

I can solve F like this: for every edge E find the maximum number that appears in the pathes that contain E and set that number for e. After all check if there is a contradiction the answer is -1, otherwise output the edge numbers. Its complexity is O(n*m). Does anybody has any better solution?

For F, Can anyone tell me any optimization in my code!

Time limit exceeded on test 268 :(

https://mirror.codeforces.com/contest/1296/submission/70317535

Thanks!!

Thanks for this round! Waiting for another Div.3 rounds :)

We have a direct formula in B, that is (s-1)/9+s;.

Well this is a bit off-topic ; but is anyone else also experiencing some un-expected indentations in their codes in codeforces submissions ?

As for example : code 1 — https://mirror.codeforces.com/contest/1296/submission/70274974

code 2 — https://ideone.com/126Qo1

These are exact same codes ; just codeforces does some un-usual indentations

Example 2 : code 1 — https://mirror.codeforces.com/contest/1296/submission/70317304

code 2 — https://ideone.com/DtpiMq

Any take on this ? maybe MikeMirzayanov ?

Do basically in D, we could kill monsters in any order?

I used Bubble Sort to solve E1 ->70281553 and I wonder if it's correct.

By the way, What are A and L represent in E1's tutorial

Thanks qwq

Hello.I got WA with my C's submission and i don't even know what is the problem. Is there any body can help me indicate where i should fix? Please. 70292288

DSU solution for E1: https://mirror.codeforces.com/contest/1296/submission/70272613
If there exists i, j that $$$ s_i > s_j $$$ and $$$ i < j $$$, there must be $$$ c_i \neq c_j $$$ , in other words, $$$ c_{i, 0} $$$ always exists with $$$ c_{j, 1} $$$ and $$$ c_{i, 1} $$$ always exists with $$$ c_{j, 0} $$$. $$$ s_i $$$ is the i-th char. $$$ c_i $$$ is the color of the i-th char. We use dsu to union $$$ c_{i, 0} $$$ and $$$ c_{j, 1} $$$, $$$ c_{i, 1} $$$ and $$$ c_{j, 0} $$$. Before union if we find $$$ c_{i, 0} $$$ and $$$ c_{j, 1} $$$ is already united, we print "NO".
Then, we just color 0 or 1 for every char. We color i-th char into 0, and color any char united with i for every i-th. This can be implemented in O(n), although my submission is O(n^2).

E2 Hard Version I wonder if the solution it to calculate the longest decreasing subsequence? Not the least decreasing subsequence? Is it right?

There is an $$$O(1)$$$ per test case solution for B.

If $$$9$$$ is a factor of $$$s$$$, the answer is $$$\lfloor \frac{s}{9} \rfloor \times 10 +s\bmod 9-1$$$.

Otherwise, the answer is $$$\lfloor \frac{s}{9} \rfloor \times 10+s\bmod 9$$$.

I've found few Guys Rampantly Cheating during Contests. Can Anyone please guide me, how to take this forward and make sure that this is seen by MikeMirzayanov , and there accounts are banned!

Manthan_144

and

rajan_ladani

Here are the Submissions they did in Codeforces Round 617 (Div. 3), and it clearly Shows that they are Big Cheats!

The Submission Of E1/E2 is clearly copied, and several redundant while loops have been added in order to escape from the copy-checker mechanism!

Manthan_144 :: 70282306

rajan_ladani :: 70294414

Apart From this they have also copied A,B,C,D

Guys please dont be cheats, and respect the community!

[deleted]

In Easy version tutorial, it said, "Let's go from left to right and carry two sequences s1 and s2. If the current character is not less than the last character of s1 then let's append it to s1, otherwise, if this character is not less than the last character of s2 then append it to s2, otherwise the answer is "NO".

While in Hard version, I also see the solution like find the minimum position i which satisfies the current character is not less than the last character of s_i by binary search, and append it to s_i. If not found, create a new sequence s_cnt and append it to s_cnt. How to prove it with Dilworth theorem?

In problem D, the number of secret technique needed can be simply calculated by (h-1)%(a+b)/a

Hey, so for problem C, I have thought of an alternative solution where, I have made prefix arrays of l,r,u and d. Now, since the robot ends at the same location in a substring, I just need to see substrings of powers of 2(as only then he will be back at the same location) from 1 to 18(according to constraints) in the whole array. So if at any time, delta(l)==delta(r) and delta(u)==delta(d). Those indeces are my answer.

However, I am getting WA on a test case whereas I cant find any testcase to contradict. All the non-truncated test cases are passing. Please help: https://mirror.codeforces.com/contest/1296/submission/70330963

For E1, there is a O(N) dp solution 70333509

I still don't understand the parity stuff in A. Someone please help a noobie

I WANNA KNOW THE PROBLEM ABOUT THIS CODE; I THINK IT'S RIGHT.

include<stdio.h>

void main() { int t, i, n, j, a, t1=0; scanf("%d", &t); for (i = 0; i < t; i++) { t1 = 0; scanf("%d", &n); for (j = 0; j < n; j++) { scanf("%d", &a); if (a % 2 == 1) t1++; } if (t1 % 2 == 1) printf("YES\n"); else printf("NO\n");

}

} THANK YOU;

It's OK to solve F in $$$\mathcal{O}(n\log^2 n)$$$ with Segment Tree Beats! (introduced here: https://mirror.codeforces.com/blog/entry/57319) and HLD. But it's rather long...

Maybe set or other DS can solve it, too.

My code: 70340529

For E1/E2, I simply used the strategy that when we consider elements from left to right, we need to "sink" each element into the correct position, which requires the current element to be a different color than any previous elements that are greater than it. We then set this color in both the answer and in another array that indicates the maximum color used for each letter. Any subsequent letters less than this letter must be a new color.

This reduces the problem to range-maximum and point update for an array of size $$$AL$$$. If we had to sort integers instead of characters, a segment tree can be used instead, but due to the small size of the alphabet one can just do this naively on a plain array.

[Deleted.]

For problem E2, there is a greedy solution :https://mirror.codeforces.com/contest/1296/submission/70332678 while read in a new alphabet, check all colors that have been chosen, if all colors are greater than it, choose a new color, then record its number to print.

There is also $$$O(n^2)$$$ solution for E1, basically find position of max element (if there's more than 1 pick rightmost), then we want to make suffix pattern from that position like this "100..000" so we can move it to the last element (if we can't then answer is NO) then bring that maximum element to the end and recurse to subproblem with string length n — 1.

In Problem D. when h%(a+b) is 0 , why we have to rollback. As the monster is killed by us and we got the point. Can you please explain.

Wow there are a lot of different solution to E1. Here is another one:

For all j < i, if s[j] > s[i], add an edge between i and j. The answer is the two coloring of the resulting graph, if it exists.

regarding the colouring strings question,If we simply just store maximum element in two colour after each i ,0<i<n,it would be enough.Let max of first colour be in a and second in b.We take condition such that b>=a. Initially assign them a=-1 and b=-1.Then if s[i]<a,spliting is not possible.If it is greater than o a but less than b it must replace a.Else it must replace b,which gives us our answer in o(n). below is the code I used

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,a=-1,b=-1;
    string s,g="";
    cin>>n;cin>>s;
    for(int i=0;i<n;++i)
    {
        //if(a>b)swap(a,b);
        if(s[i]<a){cout<<"NO\n";return 0;}
        else if(s[i]>=b){b=s[i];g+='0';}
        else {a=s[i];g+='1';}
    }cout<<"YES\n";cout<<g;
    return 0;
}

Hi, what's wrong with my solution. It gets TLE, but works in O(n^2). https://mirror.codeforces.com/contest/1296/submission/70360668

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int cnt=0;
		int num;
		cin>>num;
		int rem=num;
		while(num-10>=0)
		{
			cnt++;
			num=num-10+1;
		}
		cout<<rem+cnt<<endl;
	}
	return 0;
}

In the above code for B why I am experiencing TLE on test 3

why g pushback index i , i do not see connection

Could anyone explain what is the least decreasing subsequence in problem E2

Another cool trick for Problem C avoiding maps with pairs as keys.

Let's replace all the L elements with -1, the Rs with +1.

Similarly, replace all the Us by -1,000,000 the D's by +1,000,000.

The problem is to find the shortest subarray with 0 sum.

Can someone explain the solution for Problem C??

Thanks for the nice set of problems. In problem 1296D - Сражение с монстрами, it was understood implicitly that each player hit decreases the health points of the monster by the hitting power of this player. Nonetheless, it might have been worthwhile to mention this rule explicitly in the problem statement.

Can someone explain me problem C(Walking Robot)? In simple words.

problem e, any two neighboring (!!!) neighboring, is the key word for me, I've missed that word

E1 can also be solved using bubble sort because it's based on swapping successive elements. All elements that are swapped should have different colors.

The n^2 solution to F TLE on test case 271 in Java. I was able to have it just about pass by lazily computing the parent arrays instead of precomputing all of them.

Could anyone explain me how the formula h[i] = ((h[i] + a — 1) / a) — 1 came in Question D?

Why problems aren't rated yet?

В авторском решении мы сортируем монстров по значению секретной техники. Но в условии говорится, что бой идет от первого к последнему поочередно. Или я что то не так понял. Объясните кто нибудь. Спасибо.

Did anyone solve problem F in python? I'm getting exceed memory limit on test 148, mostly solution is same as in editorial. solution

There is a much more elegant solution to E2. Assume we are processing a certain character at an index say i. Also assume that the previous characters have been alloted best possible colors. Now in order to give this the best possible color we need to consider some possibilities such as the color given to it should not have been given to any character lexicographically greater than it. Now in order to achieve this we consider the mex or the minimum possible color that we could give it. To find the mex, we make sets consisting of : {z} , {z,y} , {z,y,x} and so on till {z,y,x,...,a}. We will put the minimum possible values that have not been given to any character in the specific set. Then if we have this info the color is easily found bu using the set {s[i] + 1 — 'a' , ... ,x,y,z} . Then comes update. It is pretty easy too. Increase all the sets before the current set if their value is lower than the current color. https://mirror.codeforces.com/contest/1296/submission/70695446 . If anyone has further queries they are more than welcome.

We can solve E2 by DP:

why my code is accepted (E2) Should it give time limit exceeded error.. void solve() { long long n,i,j,k,l; string arr; cin>>n>>arr; std::vector v; set st; char last[n]={'a'}; for(i=0;i<n;i++) { for(j=0;j<n;j++) { if(arr[i]>= last[j]) { v.push_back(j+1); last[j]=arr[i]; st.insert(j+1); break; } } } cout<<st.size()<<endl; for(i=0;i<v.size();i++) cout<<v[i]<<" "; return; }

• So excited! for E2 i think i get a really easy way to solve.
• the main idea which inspires me is MikeMirzayanov's tutorial in E1 Note that the actual problem is to divide the string into two subsequences that both of them are non-decreasing and the beautiful greedy solution.
• for E2 we just need to divide the string into more parts, so why not we repeat and continue the E1's greedy work.
• here is my submission
• the key part is the double loop by which we can find the first character no bigger than s[i] in array k ,once we find ,the work is just the same as E1.
• Also there is another important thing. Though it's a double loop, the time complexity actually is not n^2 thanks to the second loop variable j is within 26(so the size of k doesn't need 2*10^5). and this promise that it won't TLE.(you can rewrite it by a binary search if you like)
• though i can't exactly explain why greedy still works .Hoping for someone to add.

For E1,you can just connect the inverse counts(j<i and str[j]>str[i]) and see if this is bi-partitie graph

71648393

In E1/E2 Can someone explain the proof that number of colors is equal to number of non decreaing subsequences?

Problem F can also be solved in $$$O(n \log^2(m))$$$ with smaller larger optimization: 74863530

In editorial, it was said: O(n log n) for C no. problem. I found it O(n). But both idea are almost same & passes in time limit. Here is my submission: 88148367 Is my submission really O(n) (time complexity) ?

in Problem E1 we can also solve using bubble sort and bipartite graph.

Proof problem D with Dilworth's theorem ( the only way i can find out )
Might be wrong, it's my first time write such thing.
1. Lemma 1: swap only happened if the two numbers are consecutive initially: Consider if they are not consecutive there will be three types (in each type we need to remove everything beteewn and swap them ,finally got a 0 1,lets proof they are all bad)
— (1) 1 0xxxx0 0(xxxx means some 1s and 0s maybe empty)(in this case 0xxxx0 can be only one 0 too) Once you remove every 0 between them ,and swap them ,it is as same as swap the first 0 with 1 and remove every 0 after them
— (2) 1 1xxxx1 0 Same as (1)
— (3) 1 0xxxx1 0 Once you remove 0xxxx1 it will cost more than 2 remove ,so we can remove the first 1 and last 0 and the xxxx instead
2. Lemma 2 : We can do the swap at first (this is pretty easy by using Lemma1 let's skip it)
3. Lemma 3 : After all the swap the answer will be "input.size()-length of Longest Increasing Subsequence" (easy to proof)
4. Lemma 4 : If the numbers of operation is higher , the cost will be higher. The cost of operation is 1e12(+1) if there is any case that has higher number of operation but has a lower cost , than there will be at least 1e12 swap there,which obviously won't happend
5. Lemma 5 : The swap won't decrease the numbers of operation : Let's say the maximum numbers of opertion is x and we can remove one of the 0/1 and get a greedy better condition so the maximum numbers of opertion is at most x.
6. Lemma 6: Finaly, lets proof there will be no more than 1 swap : — Lets consider the antichains of the array , there are only 3 kinds : "1" "0" "10". — Once we execute one swap we may increase 1 antichain (and decrease the length of Longest Increasing Subsequence) witch is ,split "10" to "0" and "1".
— And it may not change the amount of antichain,according to lemma 3 and Lemma 5 this will increase the numbers of operation ,and according to Lemma 4 this is harmful
— Lets consider when will the harmful swap happen, once we split the "10" and got "0" and "1" ,if there is a free "1" antichain in front of them ,the "0" will combining with it;And if there is a free"0" after it the "1" will cobining with it
— If there are more than one swap ,and both are not harmful than the "1" of the front one will combining with the "0" of the back one ,and that means one of them are harmful So , there won't have no harmful swap if there are more than one swap ,and according to Lemma 4 ,we can't execute two swap.

So we can finally solve the problem We are going to record two array :how much number 0 before i and how much number 1 after i
— the least cost with out swap will be (1e12+1)*(input.size()-(biggest before[i]+after[i]+1))
— and lets find every consecutive number "10" in the initial array,the least cost is (input.size()-2+before[i-1]+after[i+2])*(1e12+1)+1e12(i is the position of "1")
The answer will be the minimum cost of them.
Just write this for fun , there should be some easier ways to proof it ,but i can't find out them

Problem C can be reduced to finding smallest subarray with sum 0 which is a standerd problem if we replace the the character 'L' with 1 and 'R' with -1 and 'U' with some bigger values like 10^7 and 'D' with the negative of 'U' ie -10^7 or vice versa submission link