Блог пользователя PraveenDhinwa

Invitation For CodeChef November Lunchtime 2016
Автор PraveenDhinwa, история, 8 лет назад, По-английски

Hello CodeForces Community,

Let me take this oppourtunity to invite you to CodeChef November LunchTime 2016 at https://www.codechef.com/LTIME42. For those who aren’t aware, LunchTime is an IOI Style contest wherein you can score based upon the number of test cases you pass in the problem..

Joining me on the problem setting panel are:
Contest Admin and Setter: PraveenDhinwa (Praveen Dhinwa)
Problem Tester: animeshf (Animesh Fatehpuria) and quite a help of kevinsogo(Kevin Charlest Atienza)
Editorialist: pkacprzak (Pawel Kacprzak)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: VNOI Team
Russian Translator: CherryTree (Sergey Kulik)

I hope you enjoy solving them. Please give me your feedback on the problem set in the comments below after the contest. You shall find the rest of the details about the contest below.

Time: 26th November 2016 (1930 hrs) to 26th November 2016 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your http://www.timeanddate.com/worldclock/fixedtime.html?msg=CodeChef%3A+November+Lunchtime+2016&iso=20161126T1930&p1=44&ah=3 .

Details: https://www.codechef.com/LTIME42

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, please [https://www.codechef.com/user/register] (register here) in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck! Hope to see you participating!!

  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Reminder : Contest begins in 12 hours.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

"Number of testcases you pass" ~ Like hackerrank partial scoring? or you are talking about subtask?

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Alert : Contest starts in 10 minutes!

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Why do I have "Wrong Login or Password!" when I'm successfully logged in via Facebook?

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Can someone explain the solution for the fourth subtask of the problem chef and balanced polygons?

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится
    • Iterate over each point in the given convex polygon.
    • Fix the point as the lowest point of the convex polygon(s) we are trying to construct, and do a DP.
      The DP state is (curIndex, lastChosen, diff) where curIndex is the current point we are considering, lastChosen is the index of the last chosen point, and diff is the difference between number of red points and blue points that we have picked up till now. We want diff to be zero at the end, as it would imply equal number of blue and red points.
    • At each state in the DP, we can either choose curIndex as one of the vertices of the polygon we are constructing or we can ignore it and go ahead. Note that this problem becomes really similar to Knapsack DP if we can somehow do the transitions efficiently.
    • To do the transtions efficiently, just precompute for each triple of points (i, j, k) in the polygon, the number of blue and red points that are inside the triangle formed by the triple. Also compute the same for each line segment represented by a pair (i, j). This can be done using brute force in O(N3 * M).

    The only geometry we actually need in this problem is just a function to check if a point is inside a triangle or not. Here is my solution.

    Hope that helps! .

    → Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

Sad story: Submitted 4th question's solution to 3rd, debugged for 1.5 hours the correct code(introduced bugs to optimize thinking TLE), now just re-submitted exactly the same in practice to get AC :( — https://www.codechef.com/viewsolution/12144569
https://www.codechef.com/viewsolution/12146772

→ Ответить