PraveenDhinwa's blog

Invitation For CodeChef November Lunchtime 2016
By PraveenDhinwa, history, 8 years ago, In English

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 [email protected])

Good Luck! Hope to see you participating!!

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

Comments Comments (14)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder : Contest begins in 12 hours.

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

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

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

Alert : Contest starts in 10 minutes!

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

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

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

    It also seems kinda weird that no one solved any problem..

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

      I'm also having the same problem T_T

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

      There is an issue with the submissions. People are getting wrong login/password error. We are working on to fix it. Regret the inconveniences :(

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

        Its okay now. Please check !!

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

          It's still showing sometimes but at least it works 1/2 of the time now.

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

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +8 Vote: I do not like it
    • 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! .

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

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

→ Reply