Um_nik's blog

Invitation to CodeChef December Lunchtime 2020
By Um_nik, history, 4 years ago, In English

We invite you to participate in CodeChef’s December Lunchtime, this Saturday, 26th December, from 9:30 pm to 12:30 am IST.
Note the unusual time. It starts at 9:30pm instead of the usual 7:30pm

You will be given a total of 8 problems (6 in Div2, 6 in Div1) to solve in a duration of 3 hours.

Joining us on the problem setting panel are:

Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Prizes: Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube Channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Good luck and have fun!

As this is my first contest as CodeChef admin, I wanted to add few words from myself. Please do consider setting problems on CodeChef, we need your help to create great contests! One of the advantages of setting problems on CodeChef is that you don't have to create whole problemset by yourself (though it is certainly possible, you can write directly to admins to [email protected] for LunchTimes and to [email protected] for Cook-Offs). Many new authors can't create whole problemset without experience, and that's totally understandable! Sending problems for review allows you to get feedback for our admins (Um_nik, 300iq, jtnydv25, Ashishgup and Morphy), and if your problem is good, you will get the invaluable experience of setting a problem for thousands of participants worldwide while working side-by-side with some of the best minds in competitive programming. Some of the best problems in this contest are set by first-time problemsetters, at least on such a level, and they did a great job, I'm looking forward to working with them again.

Apologies to SeismicToss for messing up the announcement :)

The contest is unrated due to queue and server issues.

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

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

Should we start considering CodeChef as a regular place to compete xd?

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

    By problems you can, servers you need to risk it.

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

      Since revamping our judging infrastructure 8 months back, we have had virtually no issues with submission scalability, and can easily process more than 2000 submissions and IDE runs per minute. The issue with the last Cook-Off was that we were caught off-guard by the sudden increase in traffic, and it took time for the extra servers to be deployed. That is not a valid excuse though, and we apologize for the inconvenience. We'll make sure to have sufficient redundancies in the future :)

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

        Server down well this certainly aged well :\

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

          There Servers Are Not Working. Because, money is invested somewhere else, if you know, you know :P

          Also, similar thing was happens in last contest there was some bugs, i seriously feels so bad for problem setters and things like this happens :(

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

        "We'll make sure to have sufficient redundancies in the future." Yup, you totally did that.

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

        cLoUD SerVeR Go BrRrRRRrrrRrr ...

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

        We'll make sure to have sufficient redundancies in the future

        This aged poorly

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

        ;)

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

        Oof

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

        Ouch.

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

        I think you should stop trying at this point, we will give contests on CodeForces and AtCoder. You may continue on your conquest to monetize competitive programming on Unacademy and host Conversations with CodeChef on YouTube and while you're at it maybe start making video on Roadmaps as well like other “tech youtubers”. I understand there's no money in hosting competitions so it makes sense for a "For Profit" like you to not do it properly and place your resources on these. Also plagiarism issue isn't there on CF and AtCoder, you please continue on your path of becoming a “For Profit” with your “Parent” company Un-ethical-demy.

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

          You are being way too much harsh for just one contest , They had did many awesome works in the past , You should not forget them . BTW, I too don't like what Unacademy is Doing(Paid) , But Still they have done so many awesome things in past and are still doing it , You should take them into consideration before writing such a huge comment

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

        This is super disappointing. We became too confident about our judging capacity and so had way more test files than we usually do. Coupled with the large participation, we hit the limit which hasn't happened in the last 8 months. We are very sorry for the bad experience. We will be increasing our capacity in a couple of days.

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

          kitna chutiya banaoge translation : How much fool you will make us ?

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

            Bro, please don't use such words in a platform like this, if you don't like it just don't give those contests and move on, no need to harass people who make time from their busy schedules and make a contest for us. I too feel there's something off in codechef and would prefer codeforces anytime but I do respect both of them.

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

          Last few short contests were really interesting in codechef which was the reason for high participation in this lunchtime. But again said that, we would see decrease in participant in upcoming short contests on codechef because of today's issue. I think upsolving contests would be useful than waiting for judgement for more than 45mins.

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

          CodeChef_admin Seems like site is now up, Is there any possibility we can expect queue to decrease in next few mins? Else I think participants like me would upsolve problems later on. I am very much curious in checking my solutions for Even Sequence.

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

            Not in the next few minutes, no. By current rate, the queue will decrease somewhere close to the end of the contest.

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

        2020 came calling :)

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

      Time travel at its best :) Read my first comment at the top.

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

    tourist won 7 out of last 8 short codechef contests.

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

    Quality of problems has improved significantly recently, I enjoyed the last few contests, would recommend for participation :P

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

the queue was long in the cookoff and the contest was lagging so if you could work on it then it would be great.

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

    Yes, sorry about that. Please see the comment above regarding this.

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

      Please make the website contest ready before holding the contests otherwise it seems to be frustrating. If users such as Ashishgup would write a blog on cookoff then it is obvious that there would be a heavy crowd in the contest.

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

Reminder 1 — Contest starts in 1 hour, 45 minutes.

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

Queue :(

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

    We are working on it. Please continue to solve other problems.

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

      round should be unrated . I got WA verdict after 20 minutes which i could have fixed early if there wasn't queue . Also website loading too slow.

      Also please tell if it's rated or not now instead of wasting 3 hrs and telling after that it's unrated .

      WHY PEOPLE DOWNVOTING THIS ?

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

        There is no time penalty in Lunchtime, so you did not lose anything?

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

          But there is something known as contest rank and acc. to what I know one would be lower in rank (and eventually lower in rating) if he/she doesn't solves the problem faster

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

          Time taken to solve a problem is taken into account (Did CC lied to you about that ? ). I could have fixed that in 2 minutes but i fixed after 22 mins. So yes i lost 20 minutes which i didn't deserved.

          Please make this unrated to recognize your fault at least . And please fix CC before hosting any rated round . It's now habit of CC to waste other people time.

          In div1 solving A,B fast mattered a lot and this queue ruined it.

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

          I was wrong, the time of last submission is used as a tie-breaker. Sorry.

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

            Not offending you but curious how you became admin without knowing codechef contest rules ?

            Also please make problems well balanced . First 2 submission 600 and 3rd only 35 . It should have been like 600,300,100 to be a well-balanced problem set.

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

              I'm not writing rules or configure the system to enforce these rules. My job is to choose problems and make sure they are well prepared.

              I know that IOI-style ignores time of submissions, so I assumed that it is the same here. I was wrong.

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

                Sir, I admire you. But, We Know the fact that why So Many Grand masters are interested in CC, money! And, it is ok.

                Also, i agrees that Question's Quality is good now, but don't just promote them blindly !!

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

                  What did I promote blindly?

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

            Ok

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

              I don't think you can judge difficulty gradient by contest that was basically stopped after 1 hour.

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

              Submission count of 3rd and 4th problem is low due to long queue of submission in first two problems. Even i found 4th problem easier than 3rd one. But we can't judge on submission count

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

                how to solve 3rd question?

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

                  I reduced the problem to find longest subsequence such that every segment of equal elements is of even length. And that is just simple dp.

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

submitted b 20 minutes ago still in queue.

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

Judge is too slow .

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

CC Judge..Please stop keep running and take some rest.

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

When you waited 15 mins for your submission and the website shows "unable to connect to codechef server" :(

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

    sme bro showing unable to connect again and again

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

And here goes the queue...

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

its working very slow .

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

My solution for SWAP10HG has been stuck for 40 min now T_T

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

    When I first submitted, it had like 100 submissions. Still showing server error.

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

Please declare it unrated now. It (judge servers) has reached the heights of all frustrations now!

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

Anyone facing queues ?

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

    bro issues!! im not even able to submit the code

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

      bro issues? that's something new

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

Unable to connect to the codechef servers and then you are allowed to make one submission in 120s

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

cc is the internet explorer of the programming websites.

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

I trying to submit a problem for 30 minutes. but codechef do not want to take the solution. xD

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

Ok now you can't deny the fact that it is getting frustrating now. Please make it unrated.

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

The codechef server is not loading. I have been waiting for 25 minutes to submit my code

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

Site loading too slow.

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

Make this shitty contest unrated! Unable to connect to codechef servers

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

Everyone when 300iq didn't make many tests last Codechef:

"Weak tests! Bad problems! So easy to cheese!"

But actually, he was just trying to lessen the load on the queue. Truly a 300 iq move.

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

Codechef is only focusing on their unacademy course.

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

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

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

    Thanks for making it unrated now (after half the time) otherwise its really disappointing if a contest is declared unrated at the last moment.

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

    Can you please also announce this on codechef contest page too? I don't think every participant is following this announcement on codeforces.

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

      He has done that already

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

        I can see that now, It was not present at the time when I checked before posting above comment. Maybe lag in comments also :P

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

codechef should do something because there are only two short contest in whole month and issue like this in those contest is very frustrating for all participants.

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

That was not a good way to end the year.

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

Codeforces smoothly handles over 15K participants every contest , to the contrary , cc can't handle even half the load...

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

    I think it is probably because of cf has pretests

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

      CF also has features like hacking phase, announcements for which we get notifications, we can ask our doubts/questions to the problem setters, leaderboard that updates in real time unlike every 1 minute or so and a leaderboard which accounts for people who have 0 correct submissions too. Also CodeForces is non-profit where I have seen only HarbourSpace sponsoring rounds and imho that is fine. CodeChef is blatantly supporting a scammy educational institute and yet still does not want to spend on their servers. They also offer certificates for money which cost a lot. You would think after all this, they would have better servers compared to CF.

      inb4downvotedbyindianfanboys

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

        Why do you think Unacademy is a scammy corporation? Have you EVER been to their youtube channel to see how much free material they have uploaded there? Every corporation that asks for your money isn't scammy. Byju's and WhiteHatJr might be scammy but unacademy is definitely not.

        Also codechef was only recently acquired by Unacademy. They asked Errichto to criticise them and tell them whats wrong. So they surely want to improve. Just give them their time. Its not like Codeforces didn't have any server problems in the past. Also, codechef is also non-profit. They don't tell you to buy their coure. They ASK you. Its completely upto you if you want to buy them. They dont even spam their homepage asking you to buy their courses.

        Call me an Indian Fan boy but I disagreed with your comment and downvoted it :-)

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

Contest Authors just wasted their problems. It would've been nice if this contest was on cf. :'(

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

What a way to end the year, CodeChef!

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

[user:CodeChef_admin,2020-12-26]Does contestant got laddus in an Unrated contest in codechef? Anyone knows about that? CodeChef_admin

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

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

    That is just happening from last 2 contest not every contest, you should not make such huge comment on the basis of a few time error

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

ahh, it was a cool problemset :'(. First atcoder doesn't allow to participate now this happens :/

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

    same feelings

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

    XOR palindrome problem was cool?

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

      Is it not?

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

        (I didn't want to answer before I got AC and the contest ended)

        I didn't mean to say it is a bad problem, just not very interesting. To me most of the time it was just somewhat tedious DS bashing.

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

          I thought it is an awesome problem with two nice observations and pretty simple implementation with trie. Maybe we have different solutions.

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

            Ok, there's a nicer solution. Then I won't complain. It is possible I overcomplicated — I had lazy propagation on a compressed segment tree (with custom operations).

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

I really feel sad for problem setters , there were so nice problems , queue ruined their efforts

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

you should give us more time and solve the server issue.Not making this contest unrated will solve the problem

→ Reply
»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it
only For Indian
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Stop spreading hate so much for CC, Don't forget what they have done for CP in Past in India.

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

Its very bad to see ppl cussing codechef, there can be problems like these and it happens in codeforces also (maybe less no. of time)... but I hope cc will show the reason officialy.

I am saying this is bad bcz, at first someone pay the authors to create contest for u to participate in and if something wrong happens than its totally their mistake... maybe they had judged it all wrong like no. of ppl and no. of files.

Actually as one of guy in comment was saying above, it more of seems very interesting case of how ur servers can get overwhelmed with these type pf things which no one can think of.

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

Is CodeChef worth giving the contest?? I had my submission queued for 25 mins. XD

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

    Yes, I strongly feel so. U need to experience a variety of problems. There is some pattern of problems and so the diff. b/w cc and cf. If u want to do it right way then I think u should practice problems from 2-4 diff platforms (while giving time to good problems not just solving easy everywhere).

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

      I totally agree with kesh4281 usually I have noticed nature of problems in codeforces and codechef are slightly different which really helps in learning.

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

.

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

Even though contest is unrated, do try Sum of Digits — https://www.codechef.com/LTIME91A/problems/SUMDIGIT. It has been made with a lot of work.

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

Offcourse, we want codechef not queuechef

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

Will we get verdict this year or in 2021?

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

Me after getting WA after 52 minutes in queue- meme

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

how to solve even sequence problem??? any hint.. problems were really awsm....

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

    Try using DP with 2 transitions, first transition is getting 2 equal number, and the second transition is delete the current number (delete a number and insert extra number to get a pair has tha same cost) .

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

"An even sequence has the following property: each maximal contiguous subsequence which contains only equal integers (i.e. the same integer repeated a number of times) has an even length. In particular, the empty sequence is even. A subsequence is maximal if it is not contained in a larger contiguous subsequence which contains only equal integers."

The example says seq "112" is not an even sequence. Why? The definition says it is.

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

    equal digit length should be even in this case length of digit 2 is not even -> "only equal integers (i.e. the same integer repeated a number of times) has an even length"

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

      Each maximal contigous subsequence...

      The 2 is obviusly not maximal.

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

        Yeah it is — it is not contained in any larger contiguous subsequence which contains only 2.

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

          how to solve this problem??

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

            Solution for Even Sequence: Dynamic Programming.

            Main intuition: Deleting elements is beneficial only when you are merging two disjoint subsequences whose elements are equal. To do so, it is beneficial to always pick the nearest such subsequence. Otherwise you can only add elements.

            First of all, condense all maximal contiguous subsequences. Then maintain answers for $$$dp[id][parity]$$$ which is equal to "the minimum cost such that i have processed till index id and all maximal contiguous subsequences are even except the last one, the last one has parity equal to the parity in the state".

            For transitions: You can either choose the immediately maximal contiguous subsequence OR you can choose the nearest previous contiguous subsequence whose elements were equal to the elements of the current contiguous subsequence. (You will have to use some optimizations like prefix sum for full score, also you will have to keep track of the last occurance of each subsequence)

            The answer is obviously — $$$dp[number of subsequences][0]$$$

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

Can anyone explain why is the answer for THREE (Three Letters) equal to $$$\displaystyle \text{min}\Big( \sum_{c \in A} \Big \lfloor \frac{f_c}{2} \Big \rfloor, \frac{|S|}{3}\Big)$$$ ?

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

    you can create a palindrome using only two ways.

    1st three same characters and 2nd 2 same characters and one different. So maximum number of palindrome of size 3 we can create is ∑c∈A⌊fc2⌋. Also it can't exceed size of string/3 so take minimum.

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

      Thank you for replying.

      I understand that these two things give two different upper-bounds on the answer, but can you prove why is the answer exactly the minimum of those? (i.e. why can't the answer be any other value that is lesser than those two things?)

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

        Can any of the admins comment on that, please? I am still unclear of the proof of the formula. Um_nik, Ashishgup

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

        Assume, you have an array of length n and there are x (x <= floor(n/3)) pair of numbers such that both of them are equal, you'll always have x numbers to insert between them to make them 3-length palindrome.

        Example 1:
        Example 2:

        So basically, you can never run out of the number of elements to insert between such pairs if x <= floor(n/3).

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

          This makes total sense now. Thanks very much!

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

I wrote a greedy solution to even sequence solution link

Can anyone tell me any case of failure.

My rough approach is to maintain a set of all odd length numbers we got. If the next sequence is of even length and that number is already present in set than remove all other element and add to answer and only keep that element else just remove all the element from set and add to answer.

If sequence is of odd length then add only to if it's length if of 1 and if it's already present than add to answer size of set — 1 and clear it.

P.S. — I got AC but still asking because everyone wrote DP, So greedy maybe wrong.

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

    Yeah my original solution was greedy as well, it basically depends on how you solve the underlying interval covering problem :D

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

If any one is stuck at even Sequence can watch this- https://youtu.be/EoQhlHe6PYA

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

Problem : K-Tuple Tree [Inclusion-Exclusion]

Did anyone try solving it using inclusion-exclusion principle? The idea is to first break the graph into different component by removing nodes labeled with 0 color. And then to calculate inverse, i.e total ways such the condition does not satisfy, i.e there are ATLEAST two nodes belonging to same component. Subtract above from total ways of assigning and you get the answer.

I was able to pass 4 subtasks but got WA on rest (for k > 3 I guess). I think there might be something wrong with my formulation of inclusion-exclusion. Can someone please help me with the solution?

Problem link : https://www.codechef.com/LTIME91A/problems/KTTREE

Solution link : https://www.codechef.com/viewsolution/40859580

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

Can anyone tell me what's the answer for problem Three Letters for case:

1 xxxyyyabc

To me it seems answer should be 2 but my code shows 3 & i got AC !!

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

Do you guys have any idea about this DIV-3 thing on codechef?

→ Reply