amnesiac_dusk's blog

By amnesiac_dusk, history, 6 days ago, In English

We invite you to participate in CodeChef’s November Cook-Off, this Sunday, 22nd November, from 9:30 pm to 12:00 am IST. 2.5 hours, 5 problems.

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.

Joining us on the problem setting panel are:

Prizes: The top 10 Indian and top 10 Global participants will receive CodeChef laddus, with which the winners 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!

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

»
4 days ago, # |
  Vote: I like it +38 Vote: I do not like it

Gentle Reminder: Contest starts in ~150 minutes.

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

Is there some problems with the time?? The div2 page shows the contest will end in an hour while the page where both the div1 and div2 options are there shows the contest will end in 30 mins.

UPD:-IT HAS BEEN FIXED NOW.

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

Unbalanced contest :(

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

Could have had a better difficulty gradient (C was much tougher than B, which made the contest speed forces), but other than that, nice contest.

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

Uh is it just me or did the contest length change to 3 hours?

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

    Yeah

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

      Ah, I reloaded the page a few minutes later and saw the announcement. I do find the addition of a problem during the contest to be rather sketchy though.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    This is actually really bad management of codechef, no announcement whatsoever. Everywhere its still written 2.5 hour.

»
4 days ago, # |
Rev. 3   Vote: I like it -14 Vote: I do not like it

Div 2

1st prob — 5000+ subs

2nd prob — 2700+ subs

3rd prob — 65 subs

Whattttt? Seriously how hard is it to have a balanced problemset if you take a month to prepare 2 contest.

On a side note, how do you solve the 3rd prob?

»
4 days ago, # |
  Vote: I like it +79 Vote: I do not like it

Div-1 was perfectly balanced as all things should be. Thanks for the round.

»
4 days ago, # |
  Vote: I like it +46 Vote: I do not like it

:P the Wikipedia page that was linked in the problem statement for Set Queries had the solution.

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

How to solve "Hiring Workers" ?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    We can see that the lcm of all groups should be equal to x so we can first divide the number x into coprime factors such as x=(p1^c1)*(p2^c2)... where p1,p2.. are prime numbers now if k is greater than or equal to the the number of prime factors we assign the remaining groups as 1.

    If k is less than the number of prime factors we can check by brute force as x cannot have more than 7 distinct prime factors and even if k is 6 we have to check 6^7 cases.

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How in the world will someone know the upper cap is 7! You must be a genius to figure that out. Kudos.

      • »
        »
        »
        »
        3 days ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        Just multiply the smallest 8 prime numbers.

        • »
          »
          »
          »
          »
          3 days ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Thank you, that's really neat. I spent about 2 hours and I couldn't figure that out. I was trying to come up with a some greedy approach. This proves I'm dumb!

    • »
      »
      »
      3 days ago, # ^ |
      Rev. 2   Vote: I like it +10 Vote: I do not like it

      There's a way to do it using bitmask dp too (by iterating over submasks), in like P^2*3^P time or something (don't exactly remember the complexity), where P is the number of prime factors of X and P<=7.

      • »
        »
        »
        »
        41 hour(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is there any resources for understanding bitmasks partition dp?

»
3 days ago, # |
  Vote: I like it +3 Vote: I do not like it

Video editorials for 4 problems have been uploaded here. The other 3 videos will be uploaded over the next day or two.

»
3 days ago, # |
  Vote: I like it +8 Vote: I do not like it

For HIRINGWO can someone tell whether there was another approach other than brute force when $$$k$$$ was less than number of distinct prime factors? that was like $$$6^{8}$$$.

Also for KDIAMS do we make graph with diameter 2 only no?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    "Also for KDIAMS do we make graph with diameter 2 only no" ==> you can also have a complete graph which will have diameter as 1.

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In hiring workers problem, I find a pair of least sum and having LCM x and then added k-2(k-2 groups having only 1 worker) to sum of pair. what went wrong in my approach? Somebody please help

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is your answer for $$$(k, x) = (3, 30)$$$?

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      12 (1+5+6). Oh! I got the mistake. It should be 10(2+3+5). Thanks brother :)

»
3 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice problem set but too many observation related problems :(

»
3 days ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

https://youtu.be/nTAQi-7fd1E made a video on Hiring workers. Give it a watch if you are stuck.

»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.codechef.com/viewsolution/39783935

Can someone please help me in finding as to where I am wrong in my solution for yesterday's Hiring Worker's solution?