Hello Codeforces community,

I would like to invite you all to **Coders’ Legacy 2020**, the contest held annually by KeyGEnCoders, the programming club and CodeChef Campus Chapter of Kalyani Government Engineering College. This contest will be **rated for both divisions** .

The contest starts on **15th July at 21:00 IST** . You will have **3 hours** to solve **7 problems**. The ranklist will be ICPC style with the penalty set to 20 minutes.

The problems have been prepared and tested by me, avijit_agarwal, its_aks_ulure, souradeep.99 and indrajit1. I would also like to thank smit_mandavia, jtnydv25, nagpaljatin1411 and Taran_1407 for providing valuable feedbacks and helping us set up the contest.

There are laddus for top performers as well. Please check the contest page for more details.

Good luck. :)

**UPDATE 1:** Contest starts in 30 minutes. All the best.**UPDATE 2:** Contest starts in 2 minutes. All the best. **UPDATE 3:** Contest has ended. Thanks for participating.

The problems have been moved to practice session. The editorials can be found at https://discuss.codechef.com/search?q=cole2020%20%23editorial.

Congratuations to the winners:

1. uwi

2. html_sanek

3. solaimanope

4. sam__2

5. progmatic

There were certain issues during the contest. We sincerely apologise for that.

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

Nice idea, we will think of renaming it from next year onwards.

meooow orz

With Codechef contests, I never know what quality to expect. Is this another random contest made by an arbitrary university and just hosted on Codechef? Or is it official like Cook-offs and Lunchtimes?

It's clear on Codeforces as there is GYM tab with trainings and unofficial competitions.

Actually, since this contest is rated for both divisions, the problems have been verified and tested by the CodeChef admins. Therefore, you can expect a decent problemset in this contest. We'll be more than glad to hear the feedbacks from you after the contest.

We hope to see you in the ranklist. :)

@sarthakmanna dont know ,but the rating didnot increase ,even after increase in rank from last contest ,how it is rated then??

You can also check their last year's problem set. Coders' Legacy 2019 (Rated for all). It was combined rated round for all.

Although previous rounds don't promise that next round will be good as well. But still can be a good estimate about the upcoming round's quality.

The random contest made by an arbitrary university is never rated if CodeChef admin's feel it's not up to the mark of their regular rated (Cook-Off, Lunchtime or Long) contests.

In case of a bad quality round. They also own partial responsibility along with setters/testers.

sarthakmanna will you provide the editorials, I would love to learn from nice problems :)

Sure, they are ready.

Auto comment: topic has been updated by sarthakmanna (previous revision, new revision, compare).Auto comment: topic has been updated by sarthakmanna (previous revision, new revision, compare).Auto comment: topic has been updated by sarthakmanna (previous revision, new revision, compare).Auto comment: topic has been updated by sarthakmanna (previous revision, new revision, compare).What is the point of keeping $$$10^7$$$ inputs in an already implementation heavy contest?

If the questions are not challenging enough idea-wise, I don't think increasing the constraints to forcefully make the implementation harder is the way to go.

The time limits have been verified by multiple testers. Try to come up with a more optimised solution.

I used cin,cout with ios_base in 3rd problem and wrote a O(n) solution and it gave me tle 5 times until i used scanf,printf.There should not be this strict bound on constraints.This is always an issue on codechef.

Really? I didn't need to do that at all. What were you doing

What was your complexity?

O(n). I looped through array 4 times. Also had a stack.

My was O(n). Takes 0.3 secs with cin cout and fast IO

It was already mentioned in the problem statement to use fast IO right? Its already known that scanf, printf works a bit better than cin, cout. Also one more optimization could have been to add "\n" instead of endl when using cout.

Even 2*10^6 would have avoided inefficient solutions passing so there was no point for this much strict constraints.

Changing endl to '\n' worked for me. I spent 15-20 min on that. Although I learnt something new it was quite frustrating.

`#define endl '\n'`

Elegant! Thanks. Adding this to my list of macros

Make sure to comment this out on the interactive problem.

Yes! Thanks for the heads-up

Is it just me getting 500 error always or this is common?

So am I

The CodeChef dev team is looking into it.

Also getting nothing but 500-s now :-(

Check now

Yep, all fine, thx!

Codechef seems down, is it still rated ?

It's still rated. The CodeChef team is looking into it.

Is it will be extended by a certain time?

We will announce if such a decision is taken.

sarthakmanna I submitted Door fires bracket and after that page was showing error . I refreshed and after 10 minutes it got submitted . But in my submissions it is showing submitted two times . So i have got 40 minutes penalty whereas i deserved only 20 minutes . Please look into this .(You can see both submissions are exactly same and why i will submit same solutions two times ?)

Kindly send an email to help@codechef.com

.

I don't understand the change in output format of CLLEXO. Should we now output all answer string separated by space?

The format is still same as shown in sample output. There was a typo in the statement which is fixed now.

I don't have high expectations from Codechef contest but this was a good contest ...It keeps me engage for the 3 hours ...We can't be too negative always about certain things... Thank you so much

Exactly! For the first time, I sat 3 hrs straight. Thanks for such a well-balanced contest.

Thanks for such good problems :)

How to solve Unique Substring faster than n log^2 n?

$$$n\log{n}$$$ sufarray, for all $$$l$$$ find $$$\min(r\,\colon\,s[l,r]\text{ is unique})$$$ and write $$$i$$$ at the point $$$(l, r)$$$, where $$$i$$$ is the position of $$$l$$$ in the sufarray, then each query $$$(l, r, k)$$$ can be reduced to looking for the minimal number in the rectangle with $$$l \leq x \leq r - k + 1$$$ and $$$y\leq r$$$. Build a segment tree for $$$x$$$'s where in $$$[x_l, x_r]$$$ we store all pairs $$$(r, i)$$$ where the number $$$i$$$ is written in $$$(l, r)$$$ and $$$x_l\leq l\leq x_r$$$, sorted by $$$r$$$, then we sort queries $$$(l, r, k)$$$ by $$$r$$$ and iterate over them in this order, lazily maintaining the minimal $$$i$$$'s in the segtree's nodes, thus making $$$O(n\log{n})$$$ single modifications in total.

Problems were nice.How to solve 4th problem ?

PS: not able to figure out what is wrong with my code :(

DFS from n,m node and mark all nodes which can lead to it. Do a BFS kind of soln from 1,1 and go to nodes which are valid and having minimum char at particular depth. ( Basically solve diagonally )

Time complexity O(n*m)

Thanks!!

Probably an implementation mistake in 2nd part, 1st part I did fine,i guess.

Can you elaborate a bit because i am confused that by solving diagonally and taking the minimum will it always give correct.For example what if we take the minimum from 1st level and then the minimum from 2nd level then the minimum in the 2nd level may not come from the same path as in level 1.

Question not clear

Got my mistake I was thinking of pushing every element in a level but we only have to push the minimum ones.Now I feel I am so dumb why I was not able to get this small thing:(

Yes right. Just iterate children of min at 1st level nodes.

Solving diagonally basically means solving level wise and taking the minimum at a particular level while checking if the path from that particular minimum node is valid. Am I getting right?

You can see the editorial here.

problem C was purely data structure based(Stack, Queue). I liked it a lot. It's not like it was very easy. It might be a very good problem for Div2-B at least. That's what some people are saying if some(say 1) such data structure based problem will appear in Div2 then it will be great. However I am agree that it's difficult to create such problem.

How to solve CLLEXO? I was trying to compare right and below character but could not decide in case both are equal. Thanks

Check my comment above.

Is there a non cancer way of solving CLBIT. I came up with a persistent segment tree + segment tree beats + LCA, but sadly couldn't implement it.

$$$O(nq)$$$ lol https://codeforces.com/blog/entry/67001

just HLD -> Seg tree -> Trie

The intended solution was with Trie and DSU. Check the editorial here

Ahh, Phineas and Ferb. You shall forever have my heart <3

Somebody please tell me what's the logic of the 2nd problem?

You can use binary search to solve it.

My logic was to draw a perpendicular line to x=y and check where it's intersection lied. All midpoints of the walls would lie on x=y so the coordinate of intersection should let us know which wall it was lying close to. (Yes I used lowerbound binary search)

I don't know what's wrong with this approach. Anybody can help me figure out?

This soln seems correct. Maybe you did some mistake in implementation. However I convert every wall into a value. x+y For each query (x1,y1), just add them. Check how many walls have x+y < x1+y1 and so on..

I also did that lol. I tried with dividing by 2 and then I just did by normal addition since I knew both coords like on x=y and the intersection have same division by 2.

It totally messed this contest ..

Each wall is a straight line of the form x+y=a. For a point (x1, y1) to lie outside the line, x1+y1>a should satisfy. So for each point, you just have to find the last line/wall such that it is outside the line/wall. This can be done by binary searching (x1+y1) in the array of sorted walls.

Thank you for such a nice problem set :)

Not bad problems!

Auto comment: topic has been updated by sarthakmanna (previous revision, new revision, compare).Auto comment: topic has been updated by sarthakmanna (previous revision, new revision, compare).It was a nice problemset .

Hey! Can someone help me in finding what test cases my code for CLLEXO is failing? My Solution

sarthakmanna avijit_agarwal First I found out all the cells reachable from n,m. Then I did the queue implementation of bfs starting from 1,1 which took the coordinates of the cell and the letter in its parent cell as input. For the lth character of my answer I considered all cells with i+j-1=l and having parent cell equal to the (l-1)th character of the answer string.

I don't know exactly which test cases are failing in CodeChef. But your code fails on this test:

The answer for both of the cases should be same:

`zbab`

. But on first test case, your solution prints`zbaz`

.Thanks. I resolved the issue and got AC.