Google Codejam APAC 2017 — Round B coming

8 years ago, # ^ |

+12

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

→ Reply

mkrjn99

8 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

EvgeniSergeev

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

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

mkrjn99

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

As I know:

problems are easier than normal GCJ.
target audience are univ students.

→ Reply

flpt0x

8 years ago, # |

← Rev. 3 →

+10

flashmt : Sorry?

→ Reply

flashmt

8 years ago, # ^ |

+49

Yes?

→ Reply

flpt0x

8 years ago, # ^ |

+11

Just a bad joke, nevermind..

→ Reply

TooDumbToWin

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

→ Reply

EvgeniSergeev

8 years 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.

→ Reply

poikniok

8 years ago, # ^ |

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.

→ Reply

EvgeniSergeev

8 years 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.

→ Reply

babhishek21

8 years 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.

→ Reply

gXa

8 years ago, # |

← Rev. 2 →

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.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

lnishan

8 years ago, # ^ |

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.

→ Reply

8 years ago, # |

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

→ Reply

lnishan

8 years 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? — Quora

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

→ Reply

8 years ago, # ^ |

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.

→ Reply

lnishan

8 years 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.

→ Reply

Go5H

8 years ago, # |

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.

→ Reply

har_vi

8 years ago, # ^ |

Bertrand's_ballot_theorem

→ Reply

ariel.nowik

8 years ago, # ^ |

← Rev. 3 →

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

→ Reply

-emli-

8 years ago, # |

Contest is coming

→ Reply

8 years ago, # ^ |

Thanks. I was going to update the blog for this but you were faster :D

→ Reply

8 years ago, # |

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

→ Reply

mnaeraxr

8 years ago, # |

+45

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

→ Reply

Ishan.nitj

8 years ago, # |

How to solve 3rd problem?

→ Reply

8 years ago, # ^ |

I think facebook hackercup had a very similar problem.

→ Reply

Ishan.nitj

8 years ago, # ^ |

Can you share the link?

→ Reply

Single_Ready_To_Mingle

8 years ago, # |

+14

Square Counting Solution : https://www.quora.com/How-many-squares-have-all-four-vertices-in-an-n-times-n-grid-of-dots

→ Reply

sokokaleb

8 years ago, # ^ |

Quite similar to "Counting Lattice Squares" from The 2013 ACM-ICPC Asia Phuket Regional Contest: link to problem

→ Reply

8 years ago, # |

What are some tricky test cases for second problem?

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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)

→ Reply

8 years ago, # ^ |

My output for these cases is the same, but my DP solution failed.

→ Reply

kmalhotra30

8 years ago, # |

How to Solve B?

→ Reply

8 years ago, # ^ |

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

→ Reply

kmalhotra30

8 years ago, # ^ |

Can you please post your code?

→ Reply

8 years ago, # ^ |

Not sure this will help :D

Code

string 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<vector<int>> dp(n+1+5, vector<int>(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;
            }
        }
        
    }
}

→ Reply

AshishYadav

8 years ago, # ^ |

Please describe your transitions ...

→ Reply

xennygrimmato

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

I think this is the same as OR

→ Reply

xennygrimmato

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

← Rev. 3 →

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

→ Reply

abcdef6199

8 years ago, # |

How to solve problem C ?

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # |

I have the worst working solution for problem B.

Open at your own risk

#include <bits/stdc++.h>
#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<<i<<" "<<j<<" "<<ca[i]<<" "<<cb[j]<<endl;
    if((ca[i]<0)||(cb[j]<0))return false;

	if((i==n)||(j==m)){

	   if((i==n)&&(j==m))return true;

	   if(i==n) return (pb[j]==-1);

	   return (pa[i]==-1);
	}


	if(dp[ca[i]][cb[j]][i][j]!=-1)return dp[ca[i]][cb[j]][i][j];
    
    if(ca[i]==0){
    	dp[ca[i]][cb[j]][i][j]=foo(i+1,j,n,m);
    	return dp[ca[i]][cb[j]][i][j];
    }

    if(cb[j]==0){
    	dp[ca[i]][cb[j]][i][j]=foo(i,j+1,n,m);
    	return dp[ca[i]][cb[j]][i][j];
    }

	if((a[i]!='*')&&(b[j]!='*')){

		if(a[i]!=b[j]){
			dp[ca[i]][cb[j]][i][j]=false;
		return dp[ca[i]][cb[j]][i][j];
		}
		dp[ca[i]][cb[j]][i][j]=foo(i+1,j+1,n,m);
		return dp[ca[i]][cb[j]][i][j];
	}
   
    if((a[i]=='*')&&(b[j]!='*')){
      bool f1=false,f2=false;

      	ca[i]--;
      	f1=foo(i,j+1,n,m);
        ca[i]++;

        f2=foo(i+1,j,n,m);
        dp[ca[i]][cb[j]][i][j]=(f1||f2);
        return dp[ca[i]][cb[j]][i][j];
    }
   
   if((a[i]!='*')&&(b[j]=='*')){
      bool f1=false,f2=false;
      
      cb[j]--;
      f1=foo(i+1,j,n,m);
      cb[j]++;
      
      //cout<<i<<" "<<j+1<<endl;
      f2=foo(i,j+1,n,m);

      dp[ca[i]][cb[j]][i][j]=(f1||f2);
      return dp[ca[i]][cb[j]][i][j];
    }

    bool f1=false,f2=false,f3=false;

    f1=foo(i,j+1,n,m);
    f2=foo(i+1,j,n,m);
    f3=foo(i+1,j+1,n,m);
    dp[ca[i]][cb[j]][i][j]=((f1||f2)||f3);
    return dp[ca[i]][cb[j]][i][j];
}

int main()
{
  ios_base::sync_with_stdio(false);cin.tie(0);

  freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

  int tc;cin>>tc;for(int t=1;t<=tc;t++)
  {    
     cout<<"Case #"<<t<<": ";
    
     cin>>a>>b;

     for(int i=0;i<a.size();i++)
     	ca[i]=(a[i]=='*') ? 4 : 1;

     for(int i=0;i<b.size();i++)
     	cb[i]=(b[i]=='*') ? 4 : 1;

     int n=a.size(); int m=b.size();

     for(int i=0;i<6;i++)
     {
     	for(int j=0;j<6;j++)
     	{
     		for(int k=0;k<=n;k++){
     			for(int g=0;g<=m;g++)
     			{
                  dp[i][j][k][g]=-1;
     			}
     		}
     	}
     }

     pa[n]=pb[m]=-1;

     for(int i=n-1;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<<res<<endl;
  }
          
  return 0;
}

→ Reply

xennygrimmato

8 years ago, # |

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?

→ Reply

8 years ago, # |

← Rev. 3 →

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

→ Reply

CheaterKiller

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

→ Reply

asali_ram_kumar

8 years 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.

→ Reply

8 years ago, # ^ |

You Know nothing Jon Snow brother :D

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

asali_ram_kumar

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

+17

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

→ Reply

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

→ Reply

8 years ago, # ^ |

+17

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

→ Reply

8 years ago, # ^ |

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)

→ Reply

8 years 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.

→ Reply

8 years ago, # |

+28

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.

→ Reply

8 years 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 .

→ Reply

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

→ Reply

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

→ Reply

8 years ago, # ^ |

← Rev. 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.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

-34

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

← Rev. 2 →

-21

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

This report was made by CheaterKiller not Cheaterheater.

→ Reply

8 years ago, # ^ |

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.

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

teja349

8 years ago, # ^ |

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

→ Reply

CheaterKiller

8 years 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.

→ Reply

8 years 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.

→ Reply

8 years ago, # ^ |

← Rev. 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.

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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!

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

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.

→ Reply

Death_Scythe

8 years ago, # |

+13

Has anyone got a call after the first round?

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # |

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

→ Reply

8 years ago, # ^ |

+10

These information is usually not public.

→ Reply

teja349

8 years ago, # ^ |

+20

its may 7 th not may 5 th. Please correct it.

→ Reply

8 years ago, # ^ |

Fixed. Thanks :)

→ Reply

8 years ago, # |

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

→ Reply

8 years ago, # |

Thanks for updating blog !! Almost forgot !

→ Reply

8 years ago, # |

+14

What's the approach to B?

→ Reply

achaitanya.sai

8 years 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:

$\text{[math]}$

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.

→ Reply

spiderbatman

8 years ago, # ^ |

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.

→ Reply

YourRatzon

8 years ago, # ^ |

+15

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

→ Reply

8 years ago, # ^ |

Thought sth like this might work.

So did you search alternating for x and y?

→ Reply

YourRatzon

8 years ago, # ^ |

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

→ Reply

lsmll

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

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

→ Reply

YourRatzon

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

8 years ago, # ^ |

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

→ Reply

WasylF

8 years ago, # |

← Rev. 3 →

lets share outputs for large problems!

My MD5:

A) 855edd00646d21d3fed07a8ae8c0e57a correct

C) 17a976798f02fa46bdc229026da5a180 wrong

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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

edit: now systest has finished

→ Reply

lsmll

8 years ago, # ^ |

← Rev. 2 →

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

BTW how to solve C large?

→ Reply

8 years ago, # ^ |

← Rev. 3 →

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

→ Reply

8 years ago, # |

C large?

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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 !

→ Reply

8 years ago, # ^ |

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

→ Reply

8 years ago, # ^ |

← Rev. 2 →

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)

→ Reply

-emli-

8 years ago, # |

What's the approach to A?

→ Reply

achaitanya.sai

8 years ago, # ^ |

→ Reply

8 years ago, # |

← Rev. 2 →

+40

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

→ Reply

torquecode

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

→ Reply