IceKnight1093's blog

Invitation to CodeChef Starters 133 (Rated till 6-Stars) — 8th May
By IceKnight1093, 6 months ago, In English

We invite you to participate in CodeChef’s Starters 133, this Wednesday, 8th May, rated till 6-Stars (ie. for users with rating < 2500).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good luck!

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

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Excited & Hoping for another good Starters!

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

You went TOO FAR with FIREWORKS. It's frustrating that [100'000][1'000] passes but [1'000][100'000] does not. Especially because it's tricky to tell which one is faster without submitting both. At least there are no penalties for wrong submissions...

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

    The intended solution uses $$$\mathcal{O}(N)$$$ memory — though I did try to be reasonably lenient with the time limit to account for stuff like this since many different implementations are possible.
    Unfortunately if your constant factor is a bit too bad (using $$$\mathcal{O}(N\sqrt N)$$$ memory or even worse, $$$\mathcal{O}(N\sqrt N)$$$ multiset operations — at which point it's both an extra log and bad constant) you'll end up with issues anyway.

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

      I agree that using multiset is lazy in this problem and should not be allowed.

      However, memory allocation is not an issue because I was getting TLE, not MLE. A lower memory limit could have better indicated your interest in linear memory usage, and hence a lower constant factor. By the way, I also find it frustrating that time and memory limits are hidden by default so it's not immediately obvious when a limit is unusual.

      The issue is high memory utilization with patterns that benefit an unusual memory layout. I think the CodeChef team did not perform due diligence by not checking these details extensively and ensuring consistent behavior for different coding styles.

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

        Unfortunately, custom memory limits aren't possible yet — every problem has a fixed memory limit of about 1.5GB (this is a relic from back when SPOJ was used as a backend, but has remained the same after the judge migration; hopefully sometime in the future custom memory limits will be a thing).

        As for the time limit being more visible, yes, I agree. I'll see if something can be done about it.

        → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

TOOFAREZ is nice

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

For Too Far For Comfort (Easy Version) I noticed that we have to have groups of (k chosen elements) in alternating fashion and those groups can be arranged $$$k!$$$, however since $$$n$$$ % $$$k$$$ might not not be zero, so we would have some left overs and they would be arranged in $$$\frac{k!}{(k - n MOD k)!}$$$ ways. Since there are $$${m \choose k}$$$ ways to choose k elements we get final formula for k as $$${m \choose k}$$$ $$$* k!$$$ $$$* \frac{n}{k}$$$ $$$* \frac{k!}{(k-(n MOD k))!}.$$$ But this didn't worked can someone tell me what I can do or am doing wrong??

code
→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your first idea is wrong if i get it correctly, you can have something like that(1 2 3 3 1 2 1 2)

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

      How is it wrong? I said we have groups of K elements and the last remaining block can have any of the K elements. How does this example counter my idea?

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

        Ok I'm sorry , Every block of size k can be in any form so you should make y equal to power(fact[i],j);

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

          Yup I realised it.. thanks

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

    I have realised my mistake, arranging $$$n / k$$$ groups where each group has $$$k$$$ elements can be done in $$$k! ^{\frac{n}{k}}$$$ ways and for the last $$$rem$$$ = $$$n$$$ mod $$$k$$$ elements we can have $$$k \choose rem$$$ * $$$rem!$$$ = $$$\frac{k!}{(k-(n MOD k))!}.$$$ ways.

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

      you can rearrange them in $$$k!^{n/k}$$$ ways not in $$$k!*(n/k)$$$.

      → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please provide a case where this code might be possibly failing?

Problem link ABC Conjecture 3.

Solution Link:Code

Approach: there can be two ways i.e either delete all a's or all c's for all abc subsequences

1-Starting from left ,i store position of subsequence "abc" using two pointer 2-Starting from right i ,stored the position of subsequence "cba" which is the opposite of "abc" but this way i stored the last subsequence possible 3.For 1st i deleted all c's and counted the operation 4.For 2nd i deleted all a's and counted the operations Then the minimum of them is the answer. The Code fails in hidden testCases

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Detailed Video Editorial for Powered Parameters Question

https://www.youtube.com/watch?v=O_beUC97fIA

Language => Hindi

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I saw div2A question in ZS OA that held last month...

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

why this passes on div2 B -> ac , but this not -> WA (any counter-case? or just some precision error)

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE for hard version of too far https://www.codechef.com/viewsolution/1059497149 can anyone tell error as time complexity is n * log(n) only

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

    Hey bro can you have a look here and help me with this question approach Here

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

      len : 20 string : aabcabcbcbbcbbaabbbc

      your output : 5. expected output : 4

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

    Use constant time ncr. Your ncr involves division on the fly which adds lg M to complexity.

    → Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

could you post the editorials here as well , CC discuss section is not loading ?

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

discuss section is not working, please fix it

→ Reply