riadwaw's blog

Google Code Jam 2015.
By riadwaw, 10 years ago, translation, In English

Registration is started!

Schedule:

  1. Qualification April 10 23:00 UTC
    Discussion
  2. Round 1A April 18 01:00 UTC (anyone who get fixed number of points in qual).
    Discussion.
  3. Round 1B May 2 16:00 UTC (anyone who was allowed to participate in 1A, but didn't advance to round 2 yet)
    Discussion
  4. Round 1C May 10 09:00 (anyone who was allowed to participate in 1A, but didn't advance to round 2 yet)
  5. Round 2 May 30 14:00 UTC (Top 1000 from each 1X round)
    Discussion
  6. Round 3 June 13 14:00 UTC (Top 500 from Round 2)

T-shirts are for top 1000 in Round 2.

Distributed Code Jam is also introduced

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

Comments Comments (58)
| Write comment?
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Only for justice) http://mirror.codeforces.com/blog/entry/16872

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

    Well, I didn't notice that. I'll probably leave it since this post has more info:)

    → Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +26 Vote: I do not like it

EDIT: I changed the whole comment, because it turned out that things looks somehow different than I thought. I noticed that DGCJ is not the first competition to introduce distributed problems (as stated on DGCJ homepage), because first one was polish competition Algorithmic Engagements, but the idea comes from the same person ((Jakub) Onufry Wojtaszczyk) and before rushing with that brand new idea on such a big scale like GCJ it was firstly tested in AE. But computers and software used to handle that distributed round of AE (and even a sample problem) was provided by Google, so it is fully OK for Google to take credits for that.

Btw it would be nice to have a link to GCJ's page in blog entry about it :).

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

    They must have known about AE. Of course, their right to use this format is unquestionable (if I remember correctly, one Polish Google guy [who is known by some in competitive programming world] came up with this idea and made sure everything was alright at Google's side). But in my opinion, calling it the first competition is a bit... sad. It'd be good to hear some representative's opinion on this issue.

    But by the way, hey, guys, it's a distributed GCJ round! Distributed rounds are really fun! (confirmed!)

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

      Not a regular reader of Codeforces forums, but I stumbled into this thread by accident. So, the EDIT in Swistakk's post explains the story pretty well — we wrote the distributed constest judge here at Google, and before we ran GCJ with it we decided to run a smaller-scale contest — the distributed round of AE.

      That said, I agree the wording was unfortunate, and when I noticed, I changed it: right now it says it's the first global competition of the type, which — to the best of my knowledge — is true.

      → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    If you are familiar with those distributed rounds, could you give an idea how all that works?

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

      I'll tell you how it worked in AE.

      Say you're given a problem (count how many times '0' occurs in the given sequence). You're usually given two libraries/packages:

      • a library helping with communication (providing functions like: number of available nodes, number of node this instance of program is running on, send message (for example a number or string), broadcast message, wait for message from node #x, wait for any message sent to you etc.) This library was common for all the tasks.
      • if the input is large, there is also an additional library which provides the input (in our example it could be GetN — get length of the sequence and GetNumber — get specific number in the sequence).

      You need to send a source code which is able to use these libraries, compute the result and output it (it needs to be output by exactly one node).

      As far as I remember, you usually needed to come up with a solution working in time like (at least, it had to be significantly faster than when run on 1 computer). Of course, you had to remember there are some problems going out of the fact that your program is running on multiple machines; you obviously needed to exchange some information between machines, but if you exchanged too much, you'd slow down your program significantly.

      Example solution for this task: divide the sequence evenly between machines. Say the sequence is arr[0..N-1]. Each node can count number of zeros in arr[MyNode()], arr[MyNode()+NumNodes()], arr[MyNode()+2*NumNodes()] and so on. Then each node sends its result to a "master-node", which sums all the results and outputs it.

      If there are N elements in array and k nodes, the running time of such algorithm is .

      Each problem was run on each input on something like 10-100 machines (of course, it's possible you'll be given even something like 1000 machines on GCJ).

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

        And did you have some sort of testing environment (for example some naive implementation of that library or smth like custom test?)

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

          They gave us an implementation which was an offline environment in which each node was a separate local thread.

          You might want to check this out: http://potyczki.mimuw.edu.pl/l/36/ (pl).

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

            Many thanks for the link! Now, with tutorial, it is much better to understand :) Hope, GCJ team will publish some too.

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

              Yea, we will :)

              The reason we haven't published any concrete technical specs is we're still in the process of determining the list of languages we'll be able to support (because I figure that any more technical announcement should contain the API we'll expose for communication between the nodes, and to specify the API we need to know the languages).

              I expect (disclaimer: this is not an official Google position) we'll publish the details somewhere mid-May.

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

            Cool, thanks.

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

      You may look at Distributed Code Jam FAQ for a sample problem, and at Contest Rules, point 4.2 (A), for some requirements that the submissions must satisfy. On the same page it is mentioned that it might be possible to submit test runs.

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

      You can get a rough impression of how things look like by looking at my 2 codes: http://ideone.com/aeFqU6 & http://ideone.com/6heC9R . First problem was to count LCS of two sequences up to 100000 elements.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i'm trying to change my gcj username but it says that i can't change the password more than two times for year and the last time i changed it was last year, any ideas?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

It would be great if google at least was letting Iranian coders participate in codejam without using VPN or Tor -_-

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

    By the way, GCJ is now closed to Crimean coders as well. Do they also need a VPN to participate?

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

      Maybe, when I was trying to register I kept receiving 403 Forbidden:

      403. That’s an error.

Your client does not have permission to get URL /_ah/conflogin from this server. That’s all we know.

      And when I used TorBrowser I successfully registered :)

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

        Do you need to use Tor to actually participate, or it is enough to use it during registration? Does practice mode work without Tor?

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      Yes, we need to use VPN in Crimea too.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        Can you submit your solutions in practice mode when not connected via a VPN? If so, it might be that the IP address is only checked at the time of registration, i.e. you don't need to use VPN during the contest.

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

        Isn't it prohibited by the rules?

        I thought, that terms and conditions are published to follow them, not to find the tricky way to break them.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +84 Vote: I do not like it

          One has not only a legal, but a moral responsibility to obey just laws. Conversely, one has a moral responsibility to disobey unjust laws.

          — Martin Luther King Jr.

          → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +34 Vote: I do not like it

          You expect us not to participate just because of some stupid rules ?

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

            I don't think it's okay to cheat in any way. And I don't think, that the rules are stupid.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 years ago, # ^ |
                Vote: I like it +55 Vote: I do not like it

              This particular rule is not stupid, it is evil.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 years ago, # ^ |
                  Vote: I like it +30 Vote: I do not like it

                I agree, that this rule is not fair at all. In fact, I know a lot of guys from Crimea, who deserve to participate in Code Jam. But I think that this rule was introduced for a reason (I believe that there are some juridical problems that Google doesn't want to meet with).

                And it also seems to be a good idea to follow all of the contest rules, not only those that we like.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 years ago, # ^ |
                    Vote: I like it +19 Vote: I do not like it

                  The reason is probably US sanctions against Crimea. Well, these sanctions are evil too. Also, I doubt that these sanctions apply to all online services, as otherwise Google would have to ban users from Crimea, Iran, etc from search and Gmail as well. So, I think that Google could permit those users to participate in online rounds without being able to receive any prizes (including t-shirts), and that would not be against the law. However, Google chose not only to ban them from all rounds, but also to implement technical measures to prevent them from participating, and that is evil.

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

                  Dozens of users in different topics mentioned, that Codeforces is not a good place to discuss politics, so I won't.

                  Speaking about rules of programming contest  –  I don't think that it's okay to break them, even the unfair ones.

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

                  ===============================================

                  You quoted Martin Luther King above, while there is a well known Russian proverb that is, imo, suits better to describe what's going on.

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

                  eatmore,

                  Though Codeforces is not place for political discussion, I still want to second your opinion and I want to add that this opinion is true whichever version of reality person belongs too.

                  Version 1: Crimea is under occupation by Russian Federation. In this case there is no logical sense in putting up additional sanctions against Crimea — if people already being oppressed by Russia, why US adds more punishment on top?

                  Version 2: Crimea democratically voted to become independent and then democratically voted to join Russia. Then sanctions specifically against Crimea do not make sense, because there is no sense in putting up sanction against people's desire to be where and what they want to be. Especially by country which once fought their own war for Independence.

                  So I can understand both parties involved when people talk about anti-Russia sanctions, but I fail to understand anti-Crimea sanctions. That's why I think it is just pure evil.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 years ago, # ^ |
                    Vote: I like it +39 Vote: I do not like it

                  =================================================

                  It's anti-Russian actually, but in a way more neat and elegant form. You should understand that the one who pays orders the music and Google is free to make this kind of decision.

                  I wonder why nobody complains because of VK Cup which is held for Russian-speaking only. Why none of you calls it "pure evil"? You both are pretty biased...

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

                  Because VK Cup is pure evil because only people who 14-23 years old can participate in it

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 years ago, # ^ |
                    Vote: I like it +44 Vote: I do not like it

                  Codeforces is not place for political discussion. Full stop.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 years ago, # ^ |
                    Vote: I like it +40 Vote: I do not like it

                  1. There is a difference between holding a competition for 1 country and holding a competition for all but 1 contry.

                  2. I think that holding a competiton for 1 (or small amount) country, when it is easily doable to make it available for all people is pretty evil. Moreover I heard that if some people from other countries will try to compete in VK using some translators or anything, then it would be 'unethical' which kinda makes it even more hilarious.

                  → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +35 Vote: I do not like it

        What in the serious fuck.

        Politics may not have a place in CF (rightfully), but Google is inserting it in Codejam rules. What needs to be discussed is: which rules are okay?

        Note that the rule says "ineligible for the contest" and not "ineligible for the prizes etc.". It really tells people to GTFO whatsoever if they're from certain countries. And that IMO is not okay.

        Google has the right to make their own rules. We have the right to boycott them if we don't agree with the rules. It actually works quite well if enough people do it, and the number of people in latter rounds of GCJ is reasonably small, so if people actually wanted to do it, we could send Google a clear message that we don't like politics being pushed onto us.

        And VK Cup is different. Some contests are more or less local and intended as such, for example for organisational reasons. If I had an equal problem with VK Cup (which I don't, I have competed, improved and therefore can further compete in Russian contests — and am doing just that :D; I haven't been forbidden official participation because of my country, provided I don't cause unnecessary trouble), the same logic dictates I should have equal problems with national olympiads and random contests I haven't really heard of. GCJ is intended to be an international contest.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it +50 Vote: I do not like it

          Google has the right to make their own rules.

          I don't think it's that simple. There is something called a law and Google has to comply with it, just like everyone else. If you want to blame someone for the restriction of the contest in Crimea, blame the American government.

          If you still believe this is Google's fault: what could they possibly have to gain by doing this? I honestly don't see any benefit in reducing the pool of potential participating talent.

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

            Hmm, I read the sanctions themselves, and it is pretty bad. http://www.treasury.gov/resource-center/sanctions/Programs/Documents/ukraine_eo4.pdf

            See section 5, a). It mentions "services", which should include giving you contest problems to solve (it's open to interpretation, as with any law, but I guess this would be the main argument for why the situation is what it is).

            But if giving Crimean coders contest problems is forbidden, then a US person making any round where a Crimean coder participates would automatically make them break the law, right? And if a US based company makes a contest, then they should forbid Crimean coders from participating or risk breaking the law if they participate, right?

            ... that's not what's happened so far. tyamgin participated in a TC SRM since the sanctions went into effect. I'm sure we can find more. But there was no problem with that, so why now with GCJ?

            I'm sure we can agree that this particular situation applies to everyone equally. Either everyone breaks the law by making a contest for everyone including Crimean coders, or no one does. Yet, Google explicitly chose to exclude people from the contest itself, something that no earlier contest during the sanctions (as far as I'm aware and nobody has pointed out other cases here). Another valid point here: why is the ban only from this one Google thing?

            They don't have to do it this way.

            I honestly don't see any benefit in reducing the pool of potential participating talent.

            One country isn't much to a big corporation.

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

              St. Petersburg is not Crimean city, you know this? ;)

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

                Oh, I misunderstood the earlier comments. The point still stands, though.

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

              Disclaimer 1: I work at Google, in Warsaw, Poland. Disclaimer 2: I am definitely not speaking as a representative of the company.

              The argument "TopCoder did it, so it's obviously OK" isn't very strong. As Xelios says, law is open to interpretation. And people (and countries) are much more likely to sue Google than they are to sue TopCoder over the same thing.

              Also, evil, seriously? I mean, I know people have strong feelings about programming contests, but "evil"? Isn't that a bit strong? The problems are still available online, so if you're participating for the pleasure of solving them, you can still solve them, no matter what your place of origin is. Sure, you won't get the thrill of competition. And you won't get the formal recognition by Google if you do well. But if I have to weigh this against a risk of someone suing Google over this, and Google dropping Code Jam altogether — it's definitely not obvious to me the right choice is to risk it.

              Finally, I feel a bit of hypocrisy here, because it's "us" now. There was a list of places in which the contest was void in the previous years as well (for instance, in 2014: Cuba, North Korea, Quebec, Saudi Arabia, Sudan, and Syria). Did you cry out then?

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

                You word your post in a way that sounds strange when it's a reply to mine (you refer to what I said indirectly and to what eatmore says directly) — did you really mean to reply to this post? :D

                >Did you cry out then?

                I didn't know about such rules. I don't generally read rules (common sense works; I sometimes leave when common sense doesn't work).

                Can I do anything about it myself? No. I proposed a boycott if enough people were to join; nobody reacted to it. It's better to spend my time and effort better, then.

                Since it's a dead thread, I won't reply further, but: the right choice is to fix this world itself.

                → Reply
»
10 years ago, # |
  Vote: I like it +56 Vote: I do not like it

I'm surprised at the place of Washington state, I thought it was around Washington D.C.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +65 Vote: I do not like it

    Look, St Petersburg! We hava been there for VK Cup 2012! But why it is in Florida now? :P

    → Reply
»
10 years ago, # |
  Vote: I like it +25 Vote: I do not like it

On the webpage it's stated that Google interns can't compete; I'll be doing an internship at Google this summer, but the period of my internship only includes the OnSite Finals (for which I'll certainly not qualify). Does anyone know if I'm allowed to participate in the previous rounds or has been in a similar situation?

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

    I don't think it's an issue while you're not employed at Google (before internship), but why don't you just ask them?

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      Thanks for your answer. I thought asking here would be faster and someone else may profit from the answers.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    I have been in exactly the same situation last year. I've participated in rounds till the third and even passed to the Onsite Finals, then I asked their representative if I'm able to participate in Onsite Finals, and they replied me that I can't. That wasn't a big surprise =)

    As far as I understand, it's not the violation of the rules to participate in rounds until you are intern (i. e. you will recieve T-Shirt).

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was the rule about collaborating with others changed this year? I just noticed that this year we are allowed to collaborate with others in Qualification Round, according to this page https://code.google.com/codejam/faq.html

And this is the GCJ FAQ page from 2014 https://web.archive.org/web/20140424085243/https://code.google.com/codejam/faq.html. There were no exception in 2014.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Odd, I was pretty sure the rules were like that last year too. It's so they can warn people they catch collaborating in the qualifying round without having to disqualify them.

    ETA: Maybe it was only in the rules, but not in the FAQ.

    → Reply
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

If I solved A small, can I send my solution to A small again to test the A big before submiting to big tests?

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

    Don't know, but at least you certainly can run it locally, on the small test you already have, and compare the outputs.

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

    No, you can't

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I missed the practice for Distributed GCJ, so can some kind coder out there answer my few questions?:

  1. Are the .h files provided to test (for reading input)?
  2. Is there dashboard of the practice contest somewhere? I tried to look at past contests, but could not find it.
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We have header files, but each testcase is a separate header (which you have to download separately), for example:

    // Sample input 1, in CPP.

#include <cassert>

long long GetN() {
  return 7LL;
}

long long GetTaste(long long index) {
  switch ((int)index) {
    case 0: return 10LL;
    case 1: return -2LL;
    case 2: return 5LL;
    case 3: return -4LL;
    case 4: return 3LL;
    case 5: return -5LL;
    case 6: return 1LL;
    default: assert(0);
  }
}

    You can write your own header, of course. Messaging library is automatically added by dcj when running locally (you must include message.h, of course, but include path will be added by dcj).

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

    The dashboard is at https://code.google.com/codejam/contest/4264486/dashboard You can see .h files of each problem there.

    → Reply