Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Visual explanation of the last Google Codejam 2017 question

asrp.github.io

Post reply on HN
Print view View original

21–30 of 33 posts

Re: Visual explanation of the last Google Codejam 2017 question

#21

Post by mlgh »

kgwgk wrote: post #4

Their analysis in terms of chess pieces also helps: https://code.google.com/codejam/contest/3264486/dashboard#s=...

Thank you! After reading blog-post I had zero understanding of what the problem is about and how they solve it. Tried to read again - no luck. Then I opened codejam link and saw that it's basically about placing maximum amount of bishops using maximum matching. (Other parts of problem are trivial)

That's really sad that this pattern of bad explanations is so frequent in the internet.

Re: Visual explanation of the last Google Codejam 2017 question

#22

Post by allenz »

dorianm wrote: post #16

Now I just need to understand flow networks: https://en.m.wikipedia.org/wiki/Flow_network

I think college lectures are still the best resource for learning problem solving. You might want to work through https://youtu.be/xWTc8xuHX00?list=PL-XXv-cvA_iDbtIylJDpPPJfa...

Re: Visual explanation of the last Google Codejam 2017 question

#23

Post by anonymoushn »

stevebmark wrote: post #20

Is this trolling? I don't understand most of it and it ends in the middle of the unfollowable explanation.

After you reduce it to maximum bipartite matching you just use whatever stock algorithm for bipartite matching you want.

Another comment links to the official writeup. The official writeup says that you can think about it as the "rook subproblem" and the "bishop subproblem" separately. This is the easiest way to think about it imo.

Re: Visual explanation of the last Google Codejam 2017 question

#24

Post by anonymoushn »

asrp wrote: post #15
conistonwater wrote: post #8

It's not really a maximum matching problem if a greedy algorithm works.

Which greedy algorithm do you mean? I meant that bipartite matching was enough for getting the answer, not that the two are equivalent.

There's a greedy algorithm explained at the bottom of this post: https://code.google.com/codejam/contest/3264486/dashboard#s=...

Re: Visual explanation of the last Google Codejam 2017 question

#25

Post by yodsanklai »

hartator wrote: post #2

I wonder if there is a real cause and effect relationship between being good at this kind of games and being a good coder. I suspect not.

I wonder too. I think it's like asking whether a math olympiad champion would make a great engineer. Certainly they have a lot of potential because they show extraordinary abilities, but there is much more to being a good coder than just being able to solve very short and extremely specific problems.

I've been playing these games for a couple of years (initially, for interviews preparation), and it's been very instructive. The competition format makes it convenient and addictive. There's no doubt that I improved a lot on algorithms, data structures and on "small scale" coding. While this is useful, it is quite different than what you do when working on real projects.

Re: Visual explanation of the last Google Codejam 2017 question

#27

Post by dorianm »

allenz wrote: post #22
dorianm wrote: post #16

Now I just need to understand flow networks: https://en.m.wikipedia.org/wiki/Flow_network

I think college lectures are still the best resource for learning problem solving. You might want to work through https://youtu.be/xWTc8xuHX00?list=PL-XXv-cvA_iDbtIylJDpPPJfa...

Thanks, I'm gonna see what can be applied to my own problems

Re: Visual explanation of the last Google Codejam 2017 question

#28

Post by master_yoda_1 »

I was also confused about algorithmic skill and software engineering skills. But I got clarification after working in industry for a while.

1) Most of the software engineering work is product development, just wrapping already existing algorithm and optimized computer program into apis and test and maintain it.

2) There are very few software engineering work involving writing algorithm and optimized computer program.

One example, everyone here might have just used mysql database. But if you look into the code, you might see there are complex data structure, and algorithm are being used.

https://github.com/mysql/mysql-server

Its a good thing to solve these kind of algorithmic problems.

Re: Visual explanation of the last Google Codejam 2017 question

#29

Post by Baeocystin »

yodsanklai wrote: post #25
hartator wrote: post #2

I wonder if there is a real cause and effect relationship between being good at this kind of games and being a good coder. I suspect not.

I wonder too. I think it's like asking whether a math olympiad champion would make a great engineer. Certainly they have a lot of potential because they show extraordinary abilities, but there is much more to being a good coder than just being able to solve very short and extremely specific problems. I've been playing these games for a couple of years (initially, for interviews preparation), and it's been very instru…

Math Olympiad Champion::Great Engineer as Excellent Sentence Diagrammer::Great Writer.

Puzzles are fun, but it's best not to put too much predictive faith in them, because otherwise you're just affirming the consequent. Exceptional individuals are quite likely to be good at puzzles, but you cannot (in my experience) assume that because someone is good at puzzles, they have actual skill in solving real-world problems. I've worked with too many counterexamples.

Re: Visual explanation of the last Google Codejam 2017 question

#30

Post by nindalf »

yodsanklai wrote: post #25
hartator wrote: post #2

I wonder if there is a real cause and effect relationship between being good at this kind of games and being a good coder. I suspect not.

I wonder too. I think it's like asking whether a math olympiad champion would make a great engineer. Certainly they have a lot of potential because they show extraordinary abilities, but there is much more to being a good coder than just being able to solve very short and extremely specific problems. I've been playing these games for a couple of years (initially, for interviews preparation), and it's been very instru…

When I was preparing for interviews I found that the skill that overlapped between interview puzzles and everyday work was the "head interpreter" as I call it. Typically you end up relying on the IDE and the compiler telling you if what you're writing makes sense or not. Static analysis by the IDE would only tell you if you've made a syntax error, you would need to run a test to tell if what you've written makes logical sense too.

So there's a couple of advantages if you can execute code in your head line by line while storing state as well. You can be slightly faster and more correct while coding yourself and while reviewing the code that others have written. Typically in the latter case you don't have the benefit of the compiler or running tests.

In my anecdotal experience I found an improvement in my "head interpreter" after practising interview questions for a while because typically you're not allowed to execute your code. I can't say if any of the algorithms I learnt and practised helped, but this, in my opinion, made me slightly better at my day job.

Post reply on HN