When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, history, 7 years ago, In English

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.

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

| Write comment?
»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the diffence between simple codejam?

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

    This contest is exclusively for hiring, and unlike Codejam, only university graduates from Asia Pacific region are eligible to participate.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      I read nowhere in the rules that only Asia Pacific region is allowed and I was able to register?

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +11 Vote: I do not like it

          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!

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 2   Vote: I like it +5 Vote: I do not like it

            Yeah, "you must be legal resident of..." (Asian countries) is gone too!

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

            Oh! I didn't notice that. Thanks for bringing it to my attention.

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

    As I know:

    • problems are easier than normal GCJ.
    • target audience are univ students.
»
7 years ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

flashmt : Sorry?

»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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?

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

    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.

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

      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.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    2) You can apply for intern any time online. GCJ APAC is just another way of applying.

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

    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.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).

»
7 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

Hmm it doesn't seem to just depend on the ranks.
Up to which rank in Google APAC tests are students called for interviews? — Quora

Competitive programming experiences actually do make interviews a bit easier but a good understanding of other CS subjects is also required :)

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

    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.

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

      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.

»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

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

    Bertrand's_ballot_theorem

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Contest is coming

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it +45 Vote: I do not like it

It is so sad that politics prevent Cuban competitors for taking part in this events. :(

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 3rd problem?

»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What are some tricky test cases for second problem?

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    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)

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve B?

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

    I used dp, where dp[i][j] >= 1 if you can match s1[1..i] and s2[1..j]

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

      Can you please post your code?

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

        Not sure this will help :D

        Code
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Please describe your transitions ...

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

          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.

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

            I think this is the same as OR

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

              I mean why does the state depend on dp[i][j - 1], and not just dp[i - 1][j - 1]?

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                Rev. 3   Vote: I like it 0 Vote: I do not like it

                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
                
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve problem C ?

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

    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.

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

I have the worst working solution for problem B.

Open at your own risk
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
7 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

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

»
7 years ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

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!!

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      You Know nothing Jon Snow brother :D

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      GCJ, GCJ APAC/Kickstart have anti-cheater check. It is always run before the results are finalized.

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

        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.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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.

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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.

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

    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 :(

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    Thank you for your info. I will let the people in charge of the contest know about your comment.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      code_witcher is innocent as he submitted early . thedark ranked-251 copied his code. Then why code_witcher has to suffer because of thedark??

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        Making your code public during contest (like submitting code in public mode on ideone) is also considered as cheating.

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

          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)

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it +28 Vote: I do not like it

            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.

»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Cheaterheater only cares about upvotes. He doesn't check his facts, and he blatantly abuses his anonymity, by accusing anyone he can even slightly have the chance of accusing. He accused me of cheating for no good reason, and abused me in private messages as well. He had no proof that I cheated. He hoped that everyone here is just stupid, and that they will upvote him.

Thankfully, some people investigated his claim against me and concluded that his claims are baseless, and downvoted him. So, he deleted his blog( but I have screenshots ) and started bothering me in PM again!! This time, he wanted to know why I haven't commented on his comments about other cheaters, as, according to him, by not replying on his comments, I am supporting cheaters, and this is conclusive proof that I myself am a cheater.

This guy knows no sense, and he wouldn't think twice before causing embarrassment to someone innocent. As far as I can tell, he just wants to plant a seed of doubt against someone and waits to see if it works!

Don't trust his claims without checking proof against his accusations! This time, he might be correct about his claims, but he doesn't always check facts. In fact he told me that if I support him by commenting in his favor, I will get upvotes for sure!! This guy only cares about upvotes. Beware, everyone! Don't let him fool you this way. Check his claims before believing him.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    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 .

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it +13 Vote: I do not like it

      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!

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it -13 Vote: I do not like it

        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 :(

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 3   Vote: I like it +3 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            Rev. 2   Vote: I like it -34 Vote: I do not like it

            ..

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

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                Rev. 2   Vote: I like it -21 Vote: I do not like it

                ..

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

                  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.

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

          This report was made by CheaterKiller not Cheaterheater.

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

            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.

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

              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??

              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                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.

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

                  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

            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
              Rev. 2   Vote: I like it +15 Vote: I do not like it

              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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 3   Vote: I like it +3 Vote: I do not like it

      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.

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

        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.I_love_Captain_America again -_-

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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!

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

            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 day

            Can you tell before this message of yours when I have PM you??

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

              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

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

                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.

»
7 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Has anyone got a call after the first round?

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

    Some people ranked under 200 with good resume got an email from Google indicating that they are shortlisted for the interview round.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for updating blog !! Almost forgot !

»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

What's the approach to B?

  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    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.

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

    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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I did a 2d ternary search for x and y. (It passed!)

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

      Thought sth like this might work.

      So did you search alternating for x and y?

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

        Find best y for Left x and best y for Right x and then compare and drop the worse 1/3rd of X interval

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

          This is exactly how I solved it too, though I can't prove it.

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

            I always wonder how someone can code without proving first. If the logic is wrong, the coding+debugging time is waste.

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

              well if no other logic can be deduced and those submitted problems count goes up and your rank goes down , then just code !! ;p

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

          How do we know that the optimal on X is the total optimal?

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

            For each X we look for optimal Y, so in the end we have optimal (X,Y).

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

              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.

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

      Code plz and any references to 2d ternary(or binary search) resources online ?

»
7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

lets share outputs for large problems!

My MD5:

A) 855edd00646d21d3fed07a8ae8c0e57a correct

C) 17a976798f02fa46bdc229026da5a180 wrong

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    both my hashes are different, maybe just due to whitespace?

    edit: now systest has finished

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      That's because everyone has different inputs, even for large tests.

      BTW how to solve C large?

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        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

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C large?

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

    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 !

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

      You must've had to check the height of the tree as well, when computing val. O(r*c*k*h*T) ?

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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)

»
7 years ago, # |
Rev. 2   Vote: I like it +40 Vote: I do not like it

Did anyone else receive 12 hours pre alert mail half an hourvsfter contest end?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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 :(

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

      Even i had almost missed the round if not for the good man who updated this blog yesterday!

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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~

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

UPD: Less than 24 hours for Round C.
Do check the schedule. It has changed

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

    Hi! Can you tell me what exactly changed?

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

      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