sarthakmanna's blog

By sarthakmanna, history, 5 weeks 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 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.

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

»
5 weeks 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).

»
5 weeks ago, # |
  Vote: I like it +80 Vote: I do not like it

:orz:

»
5 weeks 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.

  • »
    »
    5 weeks 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. :)

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

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

  • »
    »
    5 weeks 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.

»
4 weeks 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 :)

»
4 weeks 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).

»
4 weeks 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).

»
4 weeks 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).

»
4 weeks 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).

»
4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Codechef seems down, is it still rated ?

»
4 weeks 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 ?)

»
4 weeks ago, # |
  Vote: I like it +131 Vote: I do not like it

.

»
4 weeks 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?

  • »
    »
    4 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

Thanks for such good problems :)

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

»
4 weeks 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 :(

  • »
    »
    4 weeks 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)

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

      Thanks!!

    • »
      »
      »
      4 weeks 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.

    • »
      »
      »
      4 weeks 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.

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

        Question not clear

        • »
          »
          »
          »
          »
          4 weeks 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:(

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

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

    • »
      »
      »
      4 weeks 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?

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

    You can see the editorial here.

»
4 weeks 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.

»
4 weeks 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

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +33 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    You can use binary search to solve it.

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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..

        • »
          »
          »
          »
          »
          4 weeks 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 ..

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

Thank you for such a nice problem set :)

»
4 weeks ago, # |
Rev. 2   Vote: I like it +45 Vote: I do not like it

Not bad problems!

»
4 weeks 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).

»
4 weeks 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).

»
4 weeks ago, # |
  Vote: I like it +31 Vote: I do not like it

It was a nice problemset .

»
4 weeks 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

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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.