sarthakmanna's blog

Invitation to Coders' Legacy 2020 (Rated for all)
By sarthakmanna, history, 4 years ago, In English

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 l_returns, 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.

  • Vote: I like it
  • +152
  • Vote: I do not like it

Comments Comments (79)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +80 Vote: I do not like it

:orz:

→ Reply
»
4 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    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. :)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +38 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +65 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -40 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -18 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +26 Vote: I do not like it

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

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Codechef seems down, is it still rated ?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?)

→ Reply
»
4 years ago, # |
  Vote: I like it +131 Vote: I do not like it

.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -17 Vote: I do not like it

Thanks for such good problems :)

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    $$$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.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problems were nice.How to solve 4th problem ?
PS: not able to figure out what is wrong with my code :(

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +9 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Thanks!!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Question not clear

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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:(

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can see the editorial here.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can use binary search to solve it.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like 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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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..

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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 ..

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Thank you for such a nice problem set :)

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +45 Vote: I do not like it

Not bad problems!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

It was a nice problemset .

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    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.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    2
2 3
zba
bbb
2 3
zb
bb
ab

    The answer for both of the cases should be same: zbab. But on first test case, your solution prints zbaz.

    → Reply