### I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, history, 14 months ago, ,

UPD 2: Round B is this Sunday (May 7th) — 5.00 GMT. Time

UPD: Round A is this Sunday Mar 5th — 5.00 GMT. Time

Hi,

GCJ Kickstart (previously called GCJ APAC) will have its Practice Round this weekend. Schedule.

For problem difficulty, you can see previous year's GCJ APAC.

This year, it has 6 rounds (you can see them in the Schedule above).

For university students, this is a good chance for applying to Google. If you have high rank in these rounds, you will automatically pass the 1st phone interview round (which might be difficult for competitive programmer, e.g. flashmt failed his phone interview =)). If you have good result, you will get contacted by recruiter. You can see more details in FAQ.

•
• +104
•

 » 14 months ago, # | ← Rev. 2 →   0 What is the diffence between simple codejam?
•  » » 14 months ago, # ^ |   0 This contest is exclusively for hiring, and unlike Codejam, only university graduates from Asia Pacific region are eligible to participate.
•  » » » 14 months ago, # ^ |   +12 I read nowhere in the rules that only Asia Pacific region is allowed and I was able to register?
•  » » » » 14 months ago, # ^ | ← Rev. 2 →   0 It used to be for Google APAC. Not sure if it holds true for the new one or not. Also, please check the FAQ. They've mentioned specific schedules for different countries, where only APAC and Oceanic countries are mentioned.
•  » » » » » 14 months ago, # ^ |   +11 Looking at the difference between- The 2016 APAC Test FAQ and Terms, and- The 2017 Kickstart FAQ and Terms,the restriction that said "You must be a student enrolled in a higher (post-secondary) education institution" is no longer there.Sounds like that's more daytime contests for us!
•  » » » » » » 14 months ago, # ^ | ← Rev. 2 →   +5 Yeah, "you must be legal resident of..." (Asian countries) is gone too!
•  » » » » » » 14 months ago, # ^ |   +5 Oh! I didn't notice that. Thanks for bringing it to my attention.
•  » » 14 months ago, # ^ |   0 As I know: problems are easier than normal GCJ. target audience are univ students.
•  » » » 14 months ago, # ^ |   0 Wow! Cool!
 » 14 months ago, # | ← Rev. 3 →   +10 flashmt : Sorry?
•  » » 14 months ago, # ^ |   +49 Yes?
•  » » » 14 months ago, # ^ |   +11 Just a bad joke, nevermind..
 » 14 months ago, # |   +12 What does"preferred schedule" imply in FAQ? Does it mean that a quiz taker from India will be ineligible to compete in Round A/B?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +10 I'm guessing that it makes things easier if everyone from a cluster competes against each other in the same contests, rather than having to compare people based on their performances in disjoint contests.Though if anyone is serious about applying to work at Google, I can't see why they wouldn't do all of the contests, as well as all Codeforces, TopCoder, AtCoder, Yandex, Russian Code Cup, etc. rounds in the year before applying, because they would need a lot of practice for Google's onsite interviews anyway. That's a whole day of problem-solving and coding. There would be little opportunity to get things wrong the first time. The psychology of the situation will mean you're working at 10% of your normal performance. How much preparation time is reasonable to spare? It's a competitive exercise, so it makes sense to spare at least as much as other people would.
•  » » » 14 months ago, # ^ |   +5 I dunno I think interviews at companies like Google are easier than contest problems, but also somewhat different. I would argue that sites like Leetcode are better for interview preparation, despite problems themselves being far less interesting than CF and similar.
•  » » » » 14 months ago, # ^ |   +13 For sure, the preparation I'm talking about is not about learning more advanced algorithmic techniques. It's about getting through lots of problems, writing clean, readable code, learning to make no mistakes, and learning to explain what you're doing without sounding like you're delirious.
•  » » 14 months ago, # ^ |   +20 While nothing in the official FAQ suggests you need to compete within the "preferred schedule" to get a recruitment opportunity, I have an inkling that competing outside the "preferred schedule" alone won't get you that interview call.A little bit of history for people not in the know: APAC was traditionally held in July-December period. For Indian and Chinese students, the first 2-3 rounds are important as this is where you have the most chance of getting an interview call (This is not a rule, it's just been correlated over the years). After that the chances are minimal.However starting with Kickstart 2017, the schedule has been expanded to throughout the year. Naively you'd think that gives some Indian and Chinese senior students a double advantage. They just competed in APAC 2017 and now they have a chance to compete in the first few rounds of Kickstart 2017 before they graduate mid-2017.So from what I make of it, the "preferred schedule" is Google's way of telling you that you should compete anytime you want. But that recruitment opportunity will probably present itself in the "preferred schedule" window only.NOTE: I see that they have removed any restrictions regarding students actively enrolled in University in the APAC region, from the Official FAQ for Kickstart 2017. However, if you look at the homepage for the same, you should notice two things: "It's time for Code Jam's Kickstart competition! Formerly known as the APAC University Test, Kickstart isn't only bringing a new name, it's bringing even more rounds of coding quizzes -- to an even bigger audience across the Asia-Pacific region." (see bold text). "Be sure to review the Terms and Conditions (Note: Any student enrolled in a degree-seeking program in the Asia-Pacific region is encouraged to participate)" (see bold text) Disclaimer: I had an onsite interview with Google India after APAC 2017 Round B.
 » 14 months ago, # | ← Rev. 2 →   0 1). Doesn't Google APAC start in July second week rather than March? Why they have started so early?2). Plus before May can I apply for intern and if not selected shift to placement for further rounds as I would be in fourth year after that?3). Lastly why the name has been changed( due to banning of few countries )?Please someone clarify this.
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 2) You can apply for intern any time online. GCJ APAC is just another way of applying.
•  » » 14 months ago, # ^ |   0 1) I'm guessing this is because Google also takes Winter interns and they're always hiring for full-time positions.2) I'm having difficulties understanding the sentence. You can apply for intern during the application periods as long as you're currently enrolled as a student in an academic institution.
 » 14 months ago, # |   0 Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).
 » 14 months ago, # | ← Rev. 3 →   +16 Hmm it doesn't seem to just depend on the ranks.Up to which rank in Google APAC tests are students called for interviews? — QuoraCompetitive programming experiences actually do make interviews a bit easier but a good understanding of other CS subjects is also required :)
•  » » 14 months ago, # ^ |   +9 It would depend on interviewer. I know some friends of mine who were asked other CS subjects, especially in phone screening. But for me, luckily I was only asked about algorithm and other common sense questions.
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +10 Yes it does depend on the interviewer, but the questions typically won't be very difficult for interns.For me, it was a little bit of everything.Algorithms and data structures, architectures, easy maths and some past experiences.
 » 14 months ago, # |   +1 well, beyond of rules' discussion, i would like to know how can be solved the second task, i was watching some solutions but they are like magic for me :D. Thanks in advance.
•  » » 14 months ago, # ^ |   +1 Bertrand's_ballot_theorem
•  » » » 14 months ago, # ^ | ← Rev. 3 →   0 I used DP[vote day][Avotes-Bvotes]. Bertrand's_ballot_theorem method sounds like magic :)As M<=N<=2000 I feel DP was expected solution
 » 14 months ago, # |   +5 Contest is coming
•  » » 14 months ago, # ^ |   0 Thanks. I was going to update the blog for this but you were faster :D
•  » » » 14 months ago, # ^ |   0 One day before contest~
•  » » » » 14 months ago, # ^ |   0 ~ 2 hours ~
•  » » » » » 14 months ago, # ^ |   0 15 minutes
 » 14 months ago, # |   0 Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).
 » 14 months ago, # |   +45 It is so sad that politics prevent Cuban competitors for taking part in this events. :(
•  » » 14 months ago, # ^ |   -21
 » 14 months ago, # |   0 How to solve 3rd problem?
•  » » 14 months ago, # ^ |   0 I think facebook hackercup had a very similar problem.
•  » » » 14 months ago, # ^ |   0 Can you share the link?
 » 14 months ago, # |   +14 Square Counting Solution : https://www.quora.com/How-many-squares-have-all-four-vertices-in-an-n-times-n-grid-of-dots
•  » » 14 months ago, # ^ |   +1 Quite similar to "Counting Lattice Squares" from The 2013 ACM-ICPC Asia Phuket Regional Contest: link to problem
 » 14 months ago, # |   0 What are some tricky test cases for second problem?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 efaa*bb ef* should be TRUE *aaaaabbaaa*b b*a*b*bcca*ab should be FALSE (not 100% sure here, but I passed small+large)
•  » » » 14 months ago, # ^ |   0 My output for these cases is the same, but my DP solution failed.
 » 14 months ago, # |   0 How to Solve B?
•  » » 14 months ago, # ^ |   0 I used dp, where dp[i][j] >= 1 if you can match s1[1..i] and s2[1..j]
•  » » » 14 months ago, # ^ |   0 Can you please post your code?
•  » » » » 14 months ago, # ^ |   0 Not sure this will help :D Codestring s1, s2; in >> s1 >> s2; int n = s1.size(), m = s2.size(); //dp[i][j] = 1 if can match s1[0..i-1] and s2[0..j-1] vector> dp(n+1+5, vector(m+1+5, 0)); dp[0][0] = 1; for (int i = 1; s1[i-1] == '*' && i <= n; ++i) { dp[i][0] = 1; } for (int j = 1; s2[j-1] == '*' && j <= m; ++j) { dp[0][j] = 1; } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (s1[i-1] == s2[j-1]) { dp[i][j] += dp[i-1][j-1] >= 1; } if (s1[i-1] == '*') { int add = 0; for (int x = 0; x <= 4; ++x) { while (j+x-1+add < m && s2[j+x-1+add] == '*') dp[i][j+x-1+add] += dp[i-1][j-1], ++add; dp[i][j+x-1+add] += dp[i-1][j-1] + dp[i-1][j] >= 1; } } if (s2[j-1] == '*') { int add = 0; for (int x = 0; x <= 4; ++x) { while (i+x-1+add < n && s1[i+x-1+add] == '*') dp[i+x-1+add][j] += dp[i-1][j-1], ++add; dp[i+x-1+add][j] += dp[i-1][j-1] + dp[i][j-1] >= 1; } } } } 
•  » » » » » 14 months ago, # ^ |   0 Please describe your transitions ...
•  » » » » » 14 months ago, # ^ |   0 Can you specifically explain this part: dp[i-1][j-1] + dp[i][j-1] >= 1?My solution idea is the same as yours, didn't pass Small input — don't know what case(s) I missed.
•  » » » » » » 14 months ago, # ^ |   0 I think this is the same as OR
•  » » » » » » » 14 months ago, # ^ |   0 I mean why does the state depend on dp[i][j - 1], and not just dp[i - 1][j - 1]?
•  » » » » » » » » 14 months ago, # ^ | ← Rev. 3 →   0 Sorry, this is very bad code :D I think I just added it to handle the cases where one of the strings ends with * and they are uneven lengths, e.g. a* a 
 » 14 months ago, # |   +3 How to solve problem C ?
•  » » 14 months ago, # ^ |   0 Maybe this-Binary search on edge length.For the current edge length, make a cube at one of the extreme points in the space(note that there may or may not be a star here). Count all the stars that can be included in this cube.Now consider the farthest point in space from this chosen point. For each unincluded star, shift it's position equal to the difference of the chosen point from it's corresponding farthest point. So, now the two cubes completely overlap, after shifting some stars. If all stars are inside this cube, then we can search for a smaller edge length.
•  » » » 14 months ago, # ^ |   0 Please elaborate a bit more , chosen points and movement of stars ! Bit unclear.
 » 14 months ago, # |   +6 I have the worst working solution for problem B. Open at your own risk#include #define endl '\n'; using namespace std; typedef long long int LL; const int N=2005; int ca[N],cb[N]; int pa[N],pb[N]; string a,b; int dp[6][6][N][N]; bool foo(int i,int j,int n,int m) { //cout<>tc;for(int t=1;t<=tc;t++) { cout<<"Case #"<>a>>b; for(int i=0;i=0;i--) { if(a[i]!='*'){ pa[i]=i; } else{ pa[i]=pa[i+1]; } } for(int i=m-1;i>=0;i--) { if(b[i]!='*'){ pb[i]=i; } else{ pb[i]=pb[i+1]; } } bool fnf=foo(0,0,a.size(),b.size()); string res = (fnf) ? "TRUE" : "FALSE"; cout<
 » 14 months ago, # |   0 For problem B, an alternate solution idea that I had was to find the intersection of 2 automata.This open-source Python library allows easy creation of State Machines. So, you can perform stuff like: parse("[bc]*[ab]*") & parse("[ab]*[bc]*"). However this was too time-consuming as some small inputs were taking almost 6 seconds to run.Is a fast solution possible involving automata interesection?
 » 14 months ago, # | ← Rev. 3 →   +5 I have some queries regarding Google Kickstart :When would interview process would start for today's first round and Is they are hiring for summer internship for this year or placement for next year. And who are eligible for interview process i.e people who are graduating in this year or in 2018 ?? And how many peoples they are approximately taking for both internship and for placements?Thanks in advance :D
 » 14 months ago, # | ← Rev. 3 →   +25 Hello, we have cheaters too.See places 244 and 251 at here. Download (or look here and here) their solutions for second problem (13 points), names of variables and functions changed but compare 2 codes, same algorithm, same operations in same places...They cheated for third problem too (you can see their solutions here and here). Also they are from same school, this is their codeforces accounts: thedark and code_witcher (if you think maybe they are not cheaters, see their templates). Shame on you guys!!
•  » » 14 months ago, # ^ |   -12 as far as i know in google codejam or apac/kickstart google don't check palgiarsm check.Correct me if i am wrong.then why they changed their variables name even ?i think both account is being used by same user.
•  » » » 14 months ago, # ^ |   +2 You Know nothing Jon Snow brother :D
•  » » » » 14 months ago, # ^ |   -13 what??they are in google???reply plz
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 GCJ, GCJ APAC/Kickstart have anti-cheater check. It is always run before the results are finalized.
•  » » » » 14 months ago, # ^ |   +6 there should be anti-cheater checker.and these two cheaters must get thier punishments because there are some people who competed by their honest thinking and they are deserving.
•  » » » » 14 months ago, # ^ |   +2 They should be disqualified and won't be allowed for further rounds also. Atleast disqualify them so that people like me who have given the contest with honesty would not suffer a loss of 2 ranks. It might be possible some deserving people can just miss Google opportunity because of these cheaters.
•  » » » » 14 months ago, # ^ |   +2 Then how the cheaters thedark and code_witcher escaped so easily. Please run it once again to do justice to people.Otherwise I may miss the interview opportunity.
•  » » 14 months ago, # ^ |   +9 Not expected from you guys this thing I thought that you were the one of the best coders. But now I know that you were mere Cheaters. Feeling sad after hearing this shame on you guys. Leave Google you are even not fit for small startups :(
•  » » 14 months ago, # ^ |   +17 Thank you for your info. I will let the people in charge of the contest know about your comment.
•  » » » 14 months ago, # ^ |   -22 code_witcher is innocent as he submitted early . thedark ranked-251 copied his code. Then why code_witcher has to suffer because of thedark??
•  » » » » 14 months ago, # ^ |   +17 Making your code public during contest (like submitting code in public mode on ideone) is also considered as cheating.
•  » » » » » 14 months ago, # ^ |   0 They are doing CP since more than a year and half.What you say that they don't know this thing submitting code in public mode on ideone can lead them to fall in plagiarism -_-. So don't call it a case of ideone plagiarism. Please say something code_witcher ? Don't be quiet otherwise you will be disqualified due to thedark(theCHEATER)
•  » » » » » » 14 months ago, # ^ |   +28 They are doing CP since more than a year and half.What you say that they don't know this thing submitting code in public mode on ideone can lead them to fall in plagiarism Ok. So ideone thing didn't happen and he shared his code intentionally. Cool.
•  » » 14 months ago, # ^ |   -32 But you are clearly wrong this time and looks like you are trying to get upvotes . Even none of among both the cheaters thedark and code_witcher had apologized and said anything yet why did they fell so low just to get higher ranks so as to get rejected in interview rather than in the first round itself .
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +13 I already said he's right this time. But he wrongly accused me and didn't apologize. So if he can't have the integrity to admit that he was wrong, don't expect others to apologize :)I am not looking for upvotes, as, if that were the case, I'd have commented in favor of Cheaterheater. That would've been a real people pleaser sort of comment, and that would've guaranteed that at least he and his other fake profiles, and this other friends would've upvoted me. Instead, I chose to warn people. Whether or not people see the logic in my actions, is up to them.If he is capable of collecting real proof, why did he not collect real proof against me, instead of the bullshit bogus proof he had? He even tried to embarrass me by spamming all over my blog posts. At least I have no respect for him, such an upvote greedy!
•  » » » » 14 months ago, # ^ |   -13 I don't know about your case sorry but here he has provided real proof for sure. And if somebody have accused you wrongly you have full right to protest and put your objection people are not blind BTW :D But here its a crystal clear case of uncontrolled cheating and I suffered a loss of 2 ranks which I wanted to upgrade and surely many were thinking in the same way due to these stupid cheaters who are hiding somewhere beneath their bed :(
•  » » » » » 14 months ago, # ^ | ← Rev. 3 →   +3 I am not against the fact that cheaters are getting reported. I don't support these cheaters. All I wanted to say is, that Cheaterheater didn't make an innocent mistake against me. He knew well that his claim makes little sense. He tried to embarrass me, tried to make me comment in his favor, and didn't once apologize. Just because he reported cheaters doesn't make him great. He is just as shitty as these real cheaters.But what's done is done. I hope both the cheaters and Cheaterheater get the message, that people are not stupid. If you cheat, you'll get caught and if you intentionally do something to embarrass someone, that is also wrong, so don't do it. :)In the end, I want to say that these cheaters must be punished! If they get away, then it's sending the message that cheating is fine, nothing wrong with it. Some action must be taken.
•  » » » » » » 14 months ago, # ^ | ← Rev. 2 →   -34 ..
•  » » » » » » » 14 months ago, # ^ |   0 I am only asking people to not blindly trust these claims, and check proof, as I faced first hand what it feels like to be wrongly accused. You won't understand that, but what if people blindly believed this guy and believed that I cheated? Think about that.
•  » » » » » » » » 14 months ago, # ^ | ← Rev. 2 →   -21 ..
•  » » » » » » » » » 14 months ago, # ^ |   0 Thank god most people here are not stupid! His blog about me had got 5-6 upvotes when I opened it first. Clearly, those people didn't investigate the matter, and blindly trusted this guy.
•  » » » » » 14 months ago, # ^ |   0 This report was made by CheaterKiller not Cheaterheater.
•  » » » » » » 14 months ago, # ^ |   0 In PM, he told me he and CheaterKiller work together, and he also asked me about participating in Kickstart, and I saw him here( although in a different context ), so I wrote this here. I'm not going to write the same thing under all his comments, so let's just leave it here.
•  » » » » » » » 14 months ago, # ^ |   0 But whatever wrong happened to you , you can write a blog for that explaining every detail but narrating your own past stories on some serious issue would not be encouraged.So please think before writing. Your comments seems like you wanted to distract people from the current cheating topic and wanted to attract towards your own stories though I hope this is not exactly in your mind right??
•  » » » » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 That was not my intention. Don't worry nobody will get distracted. I_Love_Hoang_Yen already said he will alert Google about this, so the rest is up to Google, not CF community.Actually I had forgotten this incident completely. He accused me 10 days ago, but this guy sends me PM today with more nonsense, so I thought he is not very trustworthy.
•  » » » » » » » » » 14 months ago, # ^ |   +3 Y dont you put screenshots of PM as reference for your arguments of him PM today wiht more nonsense. PS:This is just out of curiosity wanted to see those messages
•  » » » » » » » 14 months ago, # ^ | ← Rev. 2 →   +15 I'm not working with someone together, sometimes someone reports cheaters and I'm inspecting cheaters, if they are indeed cheaters, I'm sharing it.UPD: Actually, this is not work :D, I'm making this because I hate cheaters (I have real story about why I hate cheaters) and inspecting cheaters are kinda funny.
•  » » 14 months ago, # ^ |   -10 What will I do with up votes -_-??And secondly I deleted the post that is my way of saying sorry and 100 clap for you how you used that thing against me like a bullshit.And what you are saying me in PM why don't you tell everyone that thing I have no objection if you will post our entire conversation without editing any of your PM to me.Also mistake is done by humans only so I corrected it and only based on one mistake you can't insult or judge about anyone. And last but not the least as said by CheaterKiller I hate cheaters (I have real story about why I hate cheaters) and inspecting cheaters are kinda funny.
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +3 Don't pretend as if I'm making stuff up.[[[[[ And also don't pretend as if you never cheated. But I am not going to accuse you here. We both know you cheat. But that's a secret :) ]]]]]Next time, make such accusations from your real account. It's not fair that you hide behind a mask, and I have to reply from my real account. Unless you get the guts to do that, keep your mouth closed. And DO NOT PM ME.Last but not the least, every time someone comments, this blog pops up in recent activity column. So let's be mature and end this as soon as possible. At least I don't want to reply to you. Rest is up to you.
•  » » » » 14 months ago, # ^ |   0 It's my real account BTW I do not participate in codeforces contest as in USA most rounds are in morning hours and I m working so not able to do codeforces rounds.And I ping you or you ping me see our conversion MR.BlackVsKnight again -_-
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 Lol!! You pinged me. I only pinged you after you spammed my blog posts, to tell you that you're wrong in doing so.If this is your real account then why did you spam me within an hour of creating this account :) You think everyone is an idiot except you. Maybe it's the other way round!
•  » » » » » » 14 months ago, # ^ |   0 Are you serious dude Why don't you see this message of yours to me :If you have problem with someone, at least you should consider talking to them one to one first, instead of spamming all over them. You created this account just to embarrass me openly in front of everyone. Just think about what you've done, and for what?The rest I leave to you. I believe you're a grown up capable of understanding simple logic.Have a nice dayCan you tell before this message of yours when I have PM you??
•  » » » » » » » 14 months ago, # ^ |   0 That was 10 days ago, after you shitposted all over my blog posts. I already admitted that, and what you expect nobody will say anything to you even if you try to embarrass them? What about your pings yesterday?And what's your explanation for your account creation time being so close to your spams over my blog posts? You think anyone will believe your lie that this is your real account? LOL
•  » » » » » » » » 14 months ago, # ^ |   +1 What you wanted to proof?? I already apologized to you ..I think you are absolutely free but I have to work otherwise they will fire me from office unlike you.
 » 13 months ago, # |   +13 Has anyone got a call after the first round?
•  » » 13 months ago, # ^ |   +3 Some people ranked under 200 with good resume got an email from Google indicating that they are shortlisted for the interview round.
 » 13 months ago, # |   0 Did anyone get any email from Google in last few days? I_love_Hoang_Yen please can you provide the current status of Google hiring process or can ask the Google hiring team is they finish taking any more peoples according to performance in round A or still they are interested to take some more??
•  » » 12 months ago, # ^ |   +10 These information is usually not public.
•  » » » 12 months ago, # ^ |   +20 its may 7 th not may 5 th. Please correct it.
•  » » » » 12 months ago, # ^ |   0 Fixed. Thanks :)
 » 12 months ago, # |   0 Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).
 » 12 months ago, # |   0 1 hour to begin
 » 12 months ago, # |   0 Thanks for updating blog !! Almost forgot !
 » 12 months ago, # |   +14 What's the approach to B?
•  » » 12 months ago, # ^ | ← Rev. 3 →   +20 I managed to solve it in this way - It is not hard to realize it as an unconstrained nonlinear optimization problem: Fortunately, there are lot of solvers available to solve this problem. I used CVXPY to solve. Here is the code:  obj = 0 X = Variable() Y = Variable() for _ in range(n): tmp = map(float, raw_input().split(' ')) a.append(tmp) obj = obj + (max_elemwise(abs(tmp[0] - X), abs(tmp[1] - Y)) * tmp[2]) objective = Minimize(obj) prob = Problem(objective) prob.solve() print "Case #%d: %.9f" % (test + 1, prob.value) Obviously this is not intended way of solving. But I just wanted to share my approach.
•  » » 12 months ago, # ^ |   0 I think(after googling) you can go from given formula to manhattan distance by rotating everything by 45 degrees, then find center there and rotate it back.
•  » » 12 months ago, # ^ |   +15 I did a 2d ternary search for x and y. (It passed!)
•  » » » 12 months ago, # ^ |   0 Thought sth like this might work.So did you search alternating for x and y?
•  » » » » 12 months ago, # ^ |   +5 Find best y for Left x and best y for Right x and then compare and drop the worse 1/3rd of X interval
•  » » » » » 12 months ago, # ^ |   0 This is exactly how I solved it too, though I can't prove it.
•  » » » » » » 12 months ago, # ^ |   0 I always wonder how someone can code without proving first. If the logic is wrong, the coding+debugging time is waste.
•  » » » » » » » 12 months ago, # ^ |   0 well if no other logic can be deduced and those submitted problems count goes up and your rank goes down , then just code !! ;p
•  » » » » » 12 months ago, # ^ |   0 How do we know that the optimal on X is the total optimal?
•  » » » » » » 12 months ago, # ^ |   0 For each X we look for optimal Y, so in the end we have optimal (X,Y).
•  » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   +3 I couldn't prove that it's unimodal during contest, but it was actually quite easy to prove. For each point, if we consider it's function fi(y) such that fi = {|y-yi| if |y-yi| >= |x-xi|,|x-xi| otherwise}then we have unimodal function in f. Sum of fi is also unimodal. Hence ternary search works.
•  » » » 12 months ago, # ^ |   +3 Code plz and any references to 2d ternary(or binary search) resources online ?
 » 12 months ago, # | ← Rev. 3 →   0 lets share outputs for large problems!My MD5:A) 855edd00646d21d3fed07a8ae8c0e57a correctC) 17a976798f02fa46bdc229026da5a180 wrong
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 both my hashes are different, maybe just due to whitespace?edit: now systest has finished
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 That's because everyone has different inputs, even for large tests.BTW how to solve C large?
•  » » » » 12 months ago, # ^ | ← Rev. 3 →   0 Didn't know that :)I made 3d array[i][j][k] = max sum and tried every i,j,k as starting position. (k > 1 only if array[i-1][j][k-1] > 0)not very fast, but ran in < 1 min with -O3 :D
 » 12 months ago, # |   0 C large?
•  » » 12 months ago, # ^ | ← Rev. 2 →   +3 first made array bool dp[r][c][l] from row 1 to n using dp.dp[r][c][l] = true if there ends(bottom) of tree here in row r from col c to l.then make another array val[r][c][k] where val = max sum of tree chain which has top single point in row r col c and this tree is counted as kth from bottom in the chain. This dp was done from row n-1 to 1. dp[][][] was used in this computation.check my code in GCJ page if you want ! same handle as here !
•  » » » 12 months ago, # ^ |   0 You must've had to check the height of the tree as well, when computing val. O(r*c*k*h*T) ?
•  » » » » 12 months ago, # ^ | ← Rev. 2 →   0 even tho it looks like O(n^5) , but tigher upper bound will be around O((n^4)*lgn) as k will depend and increase accordding to row no..here n= 100(max constraint)
 » 12 months ago, # |   0 What's the approach to A?
•  » » 12 months ago, # ^ |   +1
 » 12 months ago, # | ← Rev. 2 →   +40 Did anyone else receive 12 hours pre alert mail half an hourvsfter contest end?
•  » » 12 months ago, # ^ |   +16 Damn! I received that mail now and I was setting alarms for 12 hours later. Then, I came here and came to know that round is already over :(
•  » » » 12 months ago, # ^ |   0 Even i had almost missed the round if not for the good man who updated this blog yesterday!
 » 12 months ago, # |   +5 All solutions and explanations here: https://github.com/ckcz123/codejam/tree/master/kickstart/2017/RoundB
•  » » 12 months ago, # ^ |   0 Hi~Thanks for the solutions. I don't understand problem B. Why the final point must be an intersection of two lines? Could you please explain it for me? Thanks~
 » 12 months ago, # |   0 In 2nd problem, Center Many applicants used Ternary search, but how can we prove that function will have only one local minima in the range[-1000,1000]??? We cant use Ternary search if we have more than one local minima in that range.
 » 10 months ago, # | ← Rev. 2 →   +4 UPD: Less than 24 hours for Round C. Do check the schedule. It has changed
•  » » 10 months ago, # ^ |   0 Hi! Can you tell me what exactly changed?
•  » » » 10 months ago, # ^ |   0 Timings and Dates have been changed from initial mentioned timings and dates. Note: Tomorrow contest starts at 0:30(IST) at night previously it was morning
•  » » » » 10 months ago, # ^ |   +1 Oh, Okay! Thanks :)Actually I checked the schedule on 20th and it was exactly as it is now.