Блог пользователя kingofnumbers

Автор kingofnumbers, история, 9 лет назад, По-английски

Hi,

This is to remind you that Google Code Jam Round 1B will be tomorrow at this time, Top 1000 will advance to 2nd round.

let's discuss the problems after the contest.

Good luck.

  • Проголосовать: нравится
  • +78
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to register the contest?

Edit: "Coding has commenced! Registration is now closed." <== Okay :/

»
9 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

starts in 10 mins.
GL & HF

»
9 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Very Bad round for me . I didn't understand why my solution fails on B . B had 40+ % accuracy. I tried to be Greedy it failed( At the back of my mind I had a kind of proof).

Then I did a simply DP on integers but yet I recieved many WAs. Code .

Can someone provide some trivial test ? I think my understanding of the statement is wrong!

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well I solved in on small test, but failed on big one. Not sure why — maybe my solution is wrong, or just implementation (it is kinda complex, easy to make a mistake somewhere).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Small passed. I did it by brute force.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Input:

    1

    ?6 31

    Expected Output:

    26 31

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -8 Проголосовать: не нравится

      How to solve second question for large input.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        Go from left to right and try to assign digits either equal, or differing at most by 1 (to minimize the distance). If at some point prefixes differ, then you have to assign the rest free digits to 9 for the string with smaller prefix and assign all free digits to 0 for the other string.

        Otherwise, if you assign equal digits or they are given equal, just recurse further.

        Also, if you assign equal digits when both strings have "?" in this position, check only 0 0, it will minimize both scores.

        In such way the recursion never branches (or you can think that it has branches of length 1).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    1 ?5 10 This was in the test cases for small.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to do C small?

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You can bruteforce it with simple recursion (trying to pick all possible combinations of valid participants). With careful implementation it passes.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    for Csmall write a bitmask DP by storing a mask of topics already used. Complexity O(2N * N * N).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can use dynamic programming. The state is the set of all already placed topics (represented as binary mask). To make a transition, just iterate through all possibilities to place a new topic, and check if it is faked. The complexity is O(2n * n2)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Split topics into 2 sets — fake and real. Then for each fake topic check if there are first and second word in 'real' topics set. Try all possible splits, 2^N for each test.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It's simple: just check all the 2^n masks, O(n^2) for each mask.

    How to check it? For each topic marked as "fake" in this mask you should check whether the first word appears in the list of unfaked topics. Same for the second word. If both words do not appear — this mask can't be possible answer.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My brute-force solution with complexity O(2n * n) following:

    1. Try all possible 2n mask, where 1 means, that topic if fake.
    2. The answer is maximum of bitcount(mask) where for each fake topic there are not fake topics with same first and second words. This check procedure can be done with O(n) complexity.
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I did it with minimum edge cover. Build a bipartite graph and each entry is an edge connecting two vertices from the two sets. The answer is the total number of edges minus the minimum edge cover.

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Analysis can be found here.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +58 Проголосовать: не нравится

    I have a different solution to C than the analysis, and it does not involve being greedy at any stage. Consider the example they gave:

    HYDROCARBON COMBUSTION
    BIOMASS COMBUSTION
    QUAIL COMBUSTION
    QUAIL BEHAVIOR
    QUAIL CONTAMINATION
    GROUNDWATER CONTAMINATION
    GROUNDWATER HYDROLOGY
    

    Now, instead of finding minimum edge cover on the top graph, I simply find the maximum flow in the network below.

    The idea behind this is as follows. Let a single unit of flow represent a fake topic. Then it has to go through the middle edge, and only a single unit of flow can pass there. However, we have the additional restriction. Every word has to be in at least one legit topic. To enforce that the capacity of edges representing the words are their frequency minus one.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you show how you have enforced last condition by subtracting capacity by one? What is the final answer if flow is F. Isn't it F?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        The topics contained in the flow found here are fakes, while the remaining topics are real.

        By reducing the capacity of each word by one, you ensure that each word has at least one unused topic remaining after the fake flow is constructed, i. e. that each word has at least one real topic.

        Imagine that after finding the fake flow, you subtract the fake flow from the graph, remove the word capacity bounds (but keep the topic capacity bounds) and find the maximum flow in the resulting graph. Then you’ll get the real flow, and it will incorporate all remaining topics due to the unbounded word capacities. By ensuring that this graph contains at least one topic involving each word, you ensure that the real topics cover all words, which is good. Conversely, if you hadn’t reduced the word capacities by one before finding the fake flow, the fake flow might have taken up all topics involving a particular word and you’d be left with no real topic covering that word, which would be bad.

        Of course, you want to minimize the number of real topics, so you want to minimize the number of edges remaining after subtracting the fake flow (because each remaining edge corresponds to a real topic), so you want to maximize the number of edges in the fake flow, so you want the fake flow to be maximal.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      I don't understand why they mentioned greediness. The answer is simply n — (number of different first words) — (number of different second words) + (size of maximum matching).

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        I'm guessing it's because rather than explaining how to get the size of the edge cover, they also wanted to explain how to construct the edge cover itself.

»
9 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

when I see those large number of participants in GCJ I wonder are there a lot of competitive programmers who don't participate neither in CF nor in TC but only in GCJ?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +28 Проголосовать: не нравится

    I know a lot of guys who were active at CF/TC/CodeChef in past, and nowadays only participate in annual competitions like FHC, TCO, GCJ etc. A lot of people are active at online judges while preparing for ICPC, and then only participating in major competitions later.

    And also if you are considering active contestants, still a lot of them are only attending some small percentage of CF/TC contests, while trying not to miss events like GCJ.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      Also GCJ is quite friendly for languages like Python or even Sage, since you run everything locally and the time limit is a few minutes.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

      but this reasoning is still not enough to cover the very large numbers of participants in GCJ, if you look on the number of participants of qualification round it is around 27,000 and 22,000 out of them qualified to round 1, which is even more than total number of accounts in CF without even removing the fake accounts :D

      also looking at the difficulty of today's round and the number of points required to qualify to 2nd round I can say that one need to be div1 coder in CF to be able to qualify to 2nd round (or have equivalent skills). 3,000 coders will advance to 2nd round which is more than the number of div1 accounts in CF, again without removing fake accounts :D

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

    I think one of the main reasons is Googles brand (second place in Forbes rating after Apple). Every programming contest is positioning as a place for hiring of coders and about every coder wants to work at Google (of course the brand is not the only reason for that). So in GCJ are participating a lot of users who are not competing in other contests at all.

»
9 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

HOW to solve the 2nd question for large input.

»
9 лет назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

Very nice problems, as usual on GCJ.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Could someone upload a correct solution for the large practice data for task B? I've implemented mostly the same thing the analysis said, and the output does seem correct for the cases I can easily check by hand, but it's apparently incorrect for some. Probably a corner case...

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    You can download a solution of any participant in the scoreboard page: just set Solution Download checkbox.

»
9 лет назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится
vi find(int freqs[]){
	vi r;
	while(freqs['Z'-'A']-1 >= 0 && freqs['E'-'A']-1 >= 0 && freqs['R'-'A']-1 >= 0 && freqs['O'-'A']-1 >= 0){
		freqs['Z'-'A']--; freqs['E'-'A']--; freqs['R'-'A']--; freqs['O'-'A']--;
		r.PB(0);
	}
	while(freqs['O'-'A']-1 >= 0 && freqs['N'-'A']-1 >= 0 && freqs['E'-'A']-1 >= 0){
		freqs['O'-'A']--; freqs['N'-'A']--; freqs['E'-'A']--;
		r.PB(1);
	}
	while(freqs['T'-'A']-1 >= 0 && freqs['W'-'A']-1 >= 0 && freqs['O'-'A']-1 >= 0){
		freqs['T'-'A']--; freqs['W'-'A']--; freqs['O'-'A']--;
		r.PB(2);
	}
	while(freqs['T'-'A']-1 >= 0 && freqs['H'-'A']-1 >= 0 && freqs['R'-'A']-1 >= 0 && freqs['E'-'A']-2 >= 0){
		freqs['T'-'A']--; freqs['H'-'A']--; freqs['R'-'A']--; freqs['E'-'A']-=2;
		r.PB(3);
	}
	while(freqs['F'-'A']-1 >= 0 && freqs['O'-'A']-1 >= 0 && freqs['U'-'A']-1 >= 0 && freqs['R'-'A']-1 >= 0){
		freqs['F'-'A']--; freqs['O'-'A']--; freqs['U'-'A']--; freqs['R'-'A']--;
		r.PB(4);
	}
	while(freqs['F'-'A']-1 >= 0 && freqs['I'-'A']-1 >= 0 && freqs['V'-'A']-1 >= 0 && freqs['E'-'A']-1 >= 0){
		freqs['F'-'A']--; freqs['I'-'A']--; freqs['V'-'A']--; freqs['E'-'A']--;
		r.PB(5);
	}
	while(freqs['S'-'A']-1 >= 0 && freqs['I'-'A']-1 >= 0 && freqs['X'-'A']-1 >= 0){
		freqs['S'-'A']--; freqs['I'-'A']--; freqs['X'-'A']--;
		r.PB(6);
	}
	while(freqs['S'-'A']-1 >= 0 && freqs['E'-'A']-2 >= 0 && freqs['V'-'A']-1 >= 0  && freqs['N'-'A']-1 >= 0){
		freqs['S'-'A']--; freqs['E'-'A']-=2; freqs['V'-'A']--; freqs['N'-'A']--;
		r.PB(7);
	}
	while(freqs['E'-'A']-1 >= 0 && freqs['I'-'A']-1 >= 0 && freqs['G'-'A']-1 >= 0 && freqs['H'-'A']-1 >= 0 && freqs['T'-'A']-1 >= 0){
		freqs['E'-'A']--; freqs['I'-'A']--; freqs['G'-'A']--; freqs['H'-'A']--; freqs['T'-'A']--;
		r.PB(8);
	}
	while(freqs['N'-'A']-2 >= 0 && freqs['I'-'A']-1 >= 0 && freqs['E'-'A']-1 >= 0){
		freqs['N'-'A']-=2; freqs['I'-'A']--; freqs['E'-'A']--;
		r.PB(9);
	}
	return r;
}

Can somebody tell me what is wrong with this logic for problem A? (Besides the fact it is quite cumbersome), thanks

»
9 лет назад, # |
  Проголосовать: нравится +210 Проголосовать: не нравится

Who invented that stupid upper bound on number of friends which is 30 -_-? Do Google's employees have less than 30 friends?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +75 Проголосовать: не нравится

    that is why google could not compete with facebook.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +108 Проголосовать: не нравится

    This is a way for you to decide who are you your real buddies.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    Actually one page fits 30 people, so that's why.. :P

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

      Not actually correct. Back when one page of the full scoreboard contained only 25 entries, the number of friends was already 30.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    I also think it's a stupid restriction, but since I can't keep track of even 30 people's performances anyway, I don't mind all that much.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Having qualified in this round, is it still going to be possible to take part in round 1C out of competition in real time? Or will I be limited to submitting after it's over?

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Скажите, пожалуйста, фраза "Emails with official results will go out early next week." переводится на русский как: "официальных результатов вы не дождетесь"?