Visual explanation of the last Google Codejam 2017 question(asrp.github.io)
asrp.github.io
Visual explanation of the last Google Codejam 2017 question
https://asrp.github.io/blog/gcj_qual2017
9 comments
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.
That's really sad that this pattern of bad explanations is so frequent in the internet.
[deleted]
Could this be easily solved with the Z3 theorem prover? Is Z3 an acceptable programming language for this code jam.
Looks like you would be allowed to use it: https://code.google.com/codejam/terms
'You may use any programming language to solve a Code Jam problem. However, for any round after the qualification round, the compiler, interpreter, libraries, and external services you use must be available such that anyone else can use it for free without a time limitation and without violating any rights of any person or entity'
'You may use any programming language to solve a Code Jam problem. However, for any round after the qualification round, the compiler, interpreter, libraries, and external services you use must be available such that anyone else can use it for free without a time limitation and without violating any rights of any person or entity'
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.
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.
The more I scroll, the stupider I feel. Ugh.
This wasn't my intention. I hope the feeling subsides!
I did try to keep it short although some parts still (fortunately) shows how to come to those conclusion. That might give it the impression of being smart but the presentation is definitely selected among many idea and rearranged.
I did try to keep it short although some parts still (fortunately) shows how to come to those conclusion. That might give it the impression of being smart but the presentation is definitely selected among many idea and rearranged.
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.
This is about hitting the high notes, as Joel Spolsky put it in his [post].
A lot of people are good software engineers and can wrote good software. To get Jeff Deans that write revolutionary software, we don't yet have a better method than training people in these abstract, very hard problems, making them compete and hoping for the best.
As much as we software engineers / computer scientists believe we are special snowflakes, this exact same method is applied to most STEM PhD to professor tracks, mathematics, classic music instrument players, [athletes], and what have you.
[post] https://www.joelonsoftware.com/2005/07/25/hitting-the-high-n...
[athletes] http://rittersp.com/wp-content/uploads/2014/03/Chambliss-Mun...
[musicians] http://www.nytimes.com/images/blogs/freakonomics/pdf/Deliber...
A lot of people are good software engineers and can wrote good software. To get Jeff Deans that write revolutionary software, we don't yet have a better method than training people in these abstract, very hard problems, making them compete and hoping for the best.
As much as we software engineers / computer scientists believe we are special snowflakes, this exact same method is applied to most STEM PhD to professor tracks, mathematics, classic music instrument players, [athletes], and what have you.
[post] https://www.joelonsoftware.com/2005/07/25/hitting-the-high-n...
[athletes] http://rittersp.com/wp-content/uploads/2014/03/Chambliss-Mun...
[musicians] http://www.nytimes.com/images/blogs/freakonomics/pdf/Deliber...
And, of course, being good at coding competitions doesn't mean that you're necessarily a good software engineer. The Jeff Deans are rare. "Hoping for the best" is pretty accurate.
I suspect there is a real relationship. General intelligence is a real phenomenon. Being smart at one task indicates, though does not guarantee, that you'll be smart at another task.
This is of course a different question than whether this test provides maximum predictiveness of future success. But it seems obvious to me that the test provides some information. It's really hard for a variable to be completely non-informative.
Lastly, I think it's important for us to not be too defensive. I sense, perhaps incorrectly, that sometimes we don't want to give value to tests we are bad at, because doing so would imply we aren't as good as feel we are.
This is of course a different question than whether this test provides maximum predictiveness of future success. But it seems obvious to me that the test provides some information. It's really hard for a variable to be completely non-informative.
Lastly, I think it's important for us to not be too defensive. I sense, perhaps incorrectly, that sometimes we don't want to give value to tests we are bad at, because doing so would imply we aren't as good as feel we are.
> doing so would imply we aren't as good as feel we are.
Or to put it more pessimistically: even worse than we feel we are. Impostor syndrome and all that.
Or to put it more pessimistically: even worse than we feel we are. Impostor syndrome and all that.
I've interviewed and rejected many TopCoders and IOI competitors. Not sure why but it seems like a totally different skillset than software engineering.
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.
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.
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.
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.
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.
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.
This has been discussed here before: https://news.ycombinator.com/item?id=9695102
I don't even bother replying to their recruiters any more. The interview process tells me more than enough about the company.
I don't even bother replying to their recruiters any more. The interview process tells me more than enough about the company.
It ensures they have the basic: writing code. That you can learn alone on your computer when you are 15. That's entry level developer.
The part where you make large software, working in teams, to serve real users, can only be learnt on a job.
These competitions are not looking for anything fancy. They recruit juniors, they'll be trained on the job.
The part where you make large software, working in teams, to serve real users, can only be learnt on a job.
These competitions are not looking for anything fancy. They recruit juniors, they'll be trained on the job.
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
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.
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.
It's not really a maximum matching problem if a greedy algorithm works.
It's probably easier to come up with the reduction to maximum bipartite matching than to come up with a working greedy algorithm for bishops.
Which greedy algorithm do you mean?
I meant that bipartite matching was enough for getting the answer, not that the two are equivalent.
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=...
How did you make the animation?
I, um, recorded my screen while a loop was running to change values. Its a bit of a hack.
What are you using to render the animation then?
I think Inkscape uses Cairo for rendering. So eventually Cairo.
P.S., thanks for answering some of the questions in here! Guess I should reformulate that last part.
P.S., thanks for answering some of the questions in here! Guess I should reformulate that last part.