Kerim.K's blog

Invitation to CodeChef April Lunchtime 2019 sponsored By ShareChat
By Kerim.K, history, 6 years ago, In English

Greetings Codeforces community!

CodeChef presents the April Lunchtime sponsored by ShareChat. This is a 3-hour contest designed for school students, but all programmers are welcome to participate. Don’t forget that our problems are available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

ShareChat — India’s fastest growing social network is seeking both interns and full-time employees to join their dynamic team. Job opportunities are open to programmers across the world and internship opportunities are exclusively aimed at final year B.Tech students who have already been placed and looking forward to gaining startup experience. Don’t forget that you must participate in the contest to be eligible for internships and full-time jobs. Visit the contest page for more details.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

  • Setters: kingofnumbers (Hasan Jaddouh), Farhod (Farhod Khakimiyon), Kerim.K (Kerim Kochekov)
  • Tester: RedNextCentury (Joud Zouzou)
  • Editorialist: taran_1407 (Taranpreet Singh)
  • Statement Verifier: Xellos (Jakub Safin)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: Team VNOI
  • Russian Translator: Mediocrity (Fedor Korobeinikov)
  • Bengali Translator: solaimanope (Mohammad Solaiman)
  • Hindi Translator: Akash Shrivastava

Contest Details:

Start Date & Time: 27th April 2019 (1930 hrs) to 27th April 2019 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone

Contest link: https://www.codechef.com/LTIME71

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 Indian and top 10 Global school students from rank list will receive certificates and CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344. (For those who have not yet got their previous winning, please send an email to [email protected])

Winners of contest:

Division 1:
1) isaf27
2) uwi
3) Amoo_Safar

Division 2:
1) almogwald
2) repeating
3) ihdignite

Good Luck!
Hope to see you participating!!
Happy Programming!!

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

Comments Comments (17)
| Write comment?
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

RedNextCentury is Joud Zouzou :p

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

Can you change the timings ? Codejam is also at the same time

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

What was the intended solution for CHEFRAMI ? I tried O(N^2) DP which passed subtask but gave TLE (and sometimes WA) on the 2 large tests.

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

    My solution was dp[i] denotes minimum cost for cooking first i meals with stacking some of them in i. You can check the code: https://www.codechef.com/viewsolution/24106582

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

      Can you explain why doing this is optimal?

      dp[j] + x + mulsum[j][(i + j) / 2] + mulsum[i][(i + j) / 2 + 1])
      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        mulsum[i][j] denotes the cost of stacking all numbers from i to j in position i. The naive coding of the line you mentioned would be:

        dp[j] + x + (for all k from j to i: a[k] * min(k - j, i - k))

        So we optimize this with mulsum because for all k from j to (i+j)/2 that minimum function returns k-j and analogously we can say the other one.

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

    I have next solution :

    $$$DP[{i,j}]$$$ — minimum amount of energy to finish first $$$i$$$ groups and last group is finished at place $$$j$$$. There is just two different option for $$$i$$$-th group:

    $$$1$$$. it is first group finished at place $$$j$$$ — $$$DP[{i,j}]$$$ = $$$Best[i-1]$$$ + $$$X$$$ + $$$ENG[{i,j}]$$$.

    $$$2$$$. it is not first group finished at place $$$j$$$ — $$$DP[{i,j}]$$$ = $$$DP[{i-1,j}]$$$ + $$$ENG[{i,j}]$$$

    Where $$$ENG[{i, j}]$$$ is amount of energy to move all meals from place $$$i$$$ to place $$$j$$$ and $$$Best[i]$$$, optimal solution for first $$$i-1$$$ groups.

    You must be careful with $$$A_i=0$$$. Total complexity $$$O(N^2)$$$ per testcase.

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

    Bonjour! code link please?

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

    Similar idea:

    $$$ A=M+X \\ B=M+\frac{M^2}{X} $$$

    Using the condition $$$A\le B$$$ gives $$$X \le M$$$.

    Finding divisors ($$$X$$$'s) of $$$M^2$$$ in the range $$$[1,M]$$$ is easy.

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

    The problem was also solvable by using OEIS. I bruted the answer for $$$n = 1$$$ to $$$20$$$. Then put the sequence in OEIS. This is what I got: https://oeis.org/A018892. The last comment reads: $$$a(n)$$$ is the number of divisors of $$$n^2$$$ that are $$$\le n$$$. I compared that against the answer for small $$$n$$$ and it differed only by $$$n$$$. So, finally, I had to only add $$$n$$$ to the divisors of $$$n^2$$$ that are $$$\le n$$$.

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

How to solve The Last Droid?

→ Reply