eatmore's blog

By eatmore, history, 6 months ago, In English,

Google Code Jam 2020 has been announced. Here is the schedule:

The finals will be held in Munich, Germany ONLINE, the first Code Jam finals in mainland Europe.

The dates of other Google competitions, Hash Code and Kick Start, has been announced as well.

Unfortunately, there is no announcement regarding Distributed Code Jam, which probably means that the competition is dead. UPD: Google confirmed that there will be no DCJ in 2020.

UPD: Code Jam finals will be held online this year due to the COVID-19 pandemic.

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

»
6 months ago, # |
  Vote: I like it -54 Vote: I do not like it

Another trophy for tourist, congratulations!

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Thank you! Probably, it is a good idea to add the rounds into https://codeforces.com/calendar

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you!

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

No DCJ second time in a row.

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

what's the minimum score needed for advancing from qualification round ?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    AFAIR eps > 0

    As Swistakk noticed previous information was misleading. You actually NEED 30 POINTS TO CLASSIFY.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    "Unlike every other Code Jam Round, there is no limit on the number of potential advancers from the Qualification Round. You will advance to Round 1 if you earn at least 30 points, regardless of your penalty time. You may wish to review Visible Verdict Test Sets versus Hidden Verdict Test Sets and optimistic scoring; it doesn't hurt to score some extra points just in case!"

    You can read more at the Code Jam FAQ

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to see a new winner this time :D

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me how to prepare for Code Jam? I had qualified Round 1B in Code Jam 2019, yet could not do a single problem in Round 2 (not even the brute force partial test set) :(

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That tells you that you need to practice precise implementation.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      That's certainly true, but that wasn't what went wrong. I couldn't come up with any idea to determine if the permutation was correct in https://codingcompetitions.withgoogle.com/codejam/round/0000000000051679/0000000000146183 (which was the simplest problem in the round as per no. of submissions).

      This was a problem where I was completely unsure how to proceed. I am usually stuck in a scenario where I know the brute force but can't optimize it. Being able to try all 6! permutations and still having no idea, is another level of embarassing.

      I want to do more such questions, but maybe gradually increasing in difficulty.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it -27 Vote: I do not like it

        [Deleted]

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I hope you are joking, since it's pretty obvious (even if you don't open the link, just by looking at when I posted my comment) that the problem I mentioned in my comment is from last year's Code Jam (2019), not this year's.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +7 Vote: I do not like it

            lol sorry for that my bad, deleted.

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

the round will start in 2 mins

don't forget to take part if you can .

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The round has started and has really good questions. I definitely recommend you to join.

»
2 months ago, # |
  Vote: I like it +222 Vote: I do not like it

In case some of you also haven't noticed because of the amazing design (I write this because not only I didn't notice)

The round has 5 problems, not 4

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Ok so I modified the Codejam CSS I used last year, here you can find the new CSS code for use in Stylish this year: https://pastebin.com/jd3jGPmL.

    Improvements:

    • All problems are visible in the scoreboard.
    • Coding area takes 20% of space only (to make submissions by copy&paste possible).
    • Removes/shrinks a few unnecessary elements.

    Feel free to modify it.

    P.S. as far as I understand, they've deliberately hidden the last problem (.hideDesktop in CSS) on all devices wider than 1175px, it is not like it is not shown because there is no space.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used last year style of Mukundan Senthil (I don't remember where I got it) and had no problem with it. Now I modified it a bit and now it isn't so awful as it was

    22" screen examle
    1200px width screen
    Header is not at top of page all the time of course, it's scrolling down as usual
    It should have some bugs, feel free to comment

    Install with stylus/tampermonkey, you know it better than me. CSS

»
2 months ago, # |
Rev. 2   Vote: I like it +81 Vote: I do not like it

Is it just me or is the interactive runner still creating mental pain?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    I'd say it's also creating physical pain.

  • »
    »
    2 months ago, # ^ |
    Rev. 3   Vote: I like it +69 Vote: I do not like it

    for linux

    mkfifo pipe
    python2 local_testing_tool.py 0 < pipe | ./your_solution > pipe
    python2 local_testing_tool.py 1 < pipe | ./your_solution > pipe
    python2 local_testing_tool.py 2 < pipe | ./your_solution > pipe
    

    no output = AC

    if you want to see your output:

    python2 local_testing_tool.py 0 < pipe | ./your_solution | tee pipe
    
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    What the hell, guys?
    I don't like nor google neither codejam, but they provide testing tool for interactive problems (nice ones, IMHO) and it works perfectly and lets you to debug locally without ANY actions from your side. Nobody else provide interactors, you have to code it yourself. Usually it is easy, but takes time and has tedious implementation
    For running it simply download testing tool and then:

    mkfifo input output
    
    python testing_tool.py 2 > input < output  
    

    And in another console

    ./E < input > output
    

    To see any output just print it in stderr. As it was mentioned earlier no output of interactor means AC, otherwise it prints WA and message what went wrong. Just run several times it and submit it to gcj

    I think that windows also supports pipes, but has no ideas how to do it. Or just use wsl

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

10 mins to think of solution to Interactive problem. An hour of struggle to try submit it. I've given up. Hopefully can cross few of the future rounds too without touching the interactive problems.

»
2 months ago, # |
  Vote: I like it +82 Vote: I do not like it

"print Case #x: y"

why make us print the case number ? why...

  • »
    »
    2 months ago, # ^ |
      Vote: I like it -45 Vote: I do not like it

    They are influenced by codeforces recent rounds

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

    Likely to make it easier for newbies to analyze their output, and not to make them confuse between input and output when they paste a test with multiple test cases. (I'm against this though)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      A very good explanation.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +75 Vote: I do not like it

      AFAIK, they started consistently using the "Case #" part back when you still solved the test cases on your own machine and then submitted the outputs, and (one of) the main reason(s) was that newbies were submitting all kinds of junk instead (programs, binaries, arbitrary numbers). The absence of the case labels in the submitted file was a good heuristic they could use to tell the contestant that they are probably submitting the completely wrong file.

      As one of my favorite sayings goes, "tradition is when you keep doing something for so long that you forget why" :)

»
2 months ago, # |
  Vote: I like it +39 Vote: I do not like it

Is there any plans to support C++17/C++2a?

gcc 6.3.0 (packages: gcc, g++)
g++ Solution.cc -std=c++14 -pthread -O3 -o Solution
./Solution
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I think this is an OK place to ask: I am currently at score $$$42$$$. There is no possibility of the score displayed decreasing right? I am too tired and sleepy to continue and will look into the problems later if I am sure that my current score will clear the cutoff of $$$30$$$ points.

»
2 months ago, # |
  Vote: I like it -67 Vote: I do not like it

Can anyone help me with 3rd question. My sample test case is passed but it is showing wrong answer when I submit it.

»
2 months ago, # |
Rev. 2   Vote: I like it -113 Vote: I do not like it

sorry

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    What the hell are you doing? This is an ongoing contest. If it were up to me I'd instantly ban you for this.

    Edit: Apparently collaboration is allowed, but sharing codes is discouraged, so still don't paste codes.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's OK to do this for the qualification round.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        It's my bad

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +19 Vote: I do not like it

        Fair enough, apparently collaboration is allowed — my bad on that one. Rules still ask people not to publicly post codes, so still a good thing he removed it.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Any tip on 3rd one

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I passed TS-1 with brute force which gives TLE on TS-2. However, I think, you can solve it by sorting based on start time. 2+ hrs to go and hopefully I'm able to implement something that works.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I'm also going with the brite force but I'm getti g wrong answer but my sampe test case passed

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                Rev. 2   Vote: I like it 0 Vote: I do not like it

                Write a simple random number test case generator and test your brute force for simple tests that you think qualify as edge cases. You might be missing something small (probably the way you're finding for overlapping intervals is wrong or buggy).

                EDIT: If you haven't yet scored 30 (i.e. to qualify), try the interactive problem. It's simple and requires a few observations on how the state of bits change. TS-1 and TS-2 can be easily solved as B is only 10 and 20. For TS-3, I have implemented something that is probably right but will come to know only after a few hours...

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Think of a greedy, keeping in mind that both people are indistinguishable, i.e. they can both do all jobs.

»
2 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Approximately what CF rating should one have to advance to Round 2?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Round 2 would probably require a good knowledge of algorithms and fast implementation as only 4.5k participants get selected. So, maybe 1600-1800+

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      4.5k? Do top 1.5k people from round 1a not get counted for subsequent round 1s?

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Top 1.5k selected from each round 1A, 1B and 1C. That's 4.5k for Round 2. Top 1k from Round 2 selected for Round 3. Top 25 from Round 3 selected for WF.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          No, I mean suppose the top 100 people from round 1A , again participate and get into top 100 again, will they be not counted in 1.5k for round 1B?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            AFAIK you cannot participate in the further round 1s after you advance in one of them.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Oh, I didn't know this. Thanks for informing.

»
2 months ago, # |
Rev. 2   Vote: I like it -17 Vote: I do not like it

I couldn't solve the last question. Can anyone tell how to solve it after the round is over?

»
2 months ago, # |
  Vote: I like it +124 Vote: I do not like it

Wow, they haven't changed anything since last year. Competing on that system is so painful. :(

»
2 months ago, # |
  Vote: I like it +38 Vote: I do not like it

What are your constructions for E?

I got accepted with a merge of 4 cases:

1) The obvious cyclic shift construction for $$$k = n * p$$$ for some $$$p$$$.

2) It's easy to prove that for $$$k = n + 1$$$ and $$$k = n^2 - 1$$$ we have no solution.

3) A construction for $$$k \in [n+3; n^2-3]$$$ based on picking three numbers that will appear on the diagonal $$$x$$$, $$$1$$$ and $$$n-x-1$$$ times.

4) Weird Monte Carlo (e.g. rejection sampling like approach) with random matchings for $$$k = n+2, n^2-2$$$.

As I'm pretty sure that's not intended I would love if someone can share a clean solution.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    By Hall's, if there is a diagonal where no number appears exactly N-1 times, then you can construct a grid with it.

    Therefore, I generate the lexicographically smallest valid diagonal with recursive backtracking. After that, I forcibly place every number if some instance of that number appears on the diagonal with bipartite matching. After that, I place the remaining numbers in increasing order.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      By Hall's, if there is a diagonal where no number appears exactly N-1 times, then you can construct a grid with it.

      After that, I forcibly place every number if some instance of that number appears on the diagonal with bipartite matching.

      Can you explain these parts? I must be not seeing something as at least from my perspective, different values on diagonal should be treated as various commodities types, so I don't get how you can apply Hall here.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        I think seeing this problem should help motivate what I'm trying to do here, except instead of filling the grid one row at a time, you fill the grid one number at a time. The application of Hall's on that problem should hopefully be more obvious.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it +11 Vote: I do not like it

          Also see this problem.

          I did some casework to fill up the diagonal with at most 3 distinct numbers and then used flow to generate the positions of the other numbers.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Heh, that is problem that I gave my students yesterday as a homework on a course that I teach xD (or to be more precise — its mathematical version). So you can assume I knew that one xD. But since you say that is similar, I will just think about it by myself tomorrow, cause it's 5AM here and my mind is not that clear.

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            If it helps, the editorial that is released for that problem contains a proof for why Hall's applies here.

            The claim I'm asserting consequently is that inserting the numbers row by row as opposed to number by number are isomorphic operations.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Nice! Thanks :)

              Although I feel like they left out how they treat the already initial values. This seem to prove only the case for empty rows, but in this case we have rows already filled...

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +21 Vote: I do not like it

      Hey, can you maybe explain how you can prove this by Hall? I don't get the why for every subset of numbers there is at-least this much matching cells in a specific row, after filling each row behind it.

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    I think that is close to intended except for the case with $$$n+2$$$ and $$$n^2-2$$$ that you clearly messed up. I have something similar, but a bit different construction for three numbers (frequencies in my code are n-2, 1, 1) and I have also a case when there are two numbers appearing $$$c$$$ and $$$n-c$$$ times for any $$$2 \le c \le n-2$$$ (but $$$c=2$$$ will serve your purpose) which is significantly easier than the case with three numbers.

    EDIT: OK, seeing the explanation of xiaowuc1 I don't think that caseology was intended solution :P.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I had the same construction for cases 1-3. I couldn't figure out 4. Also, another thing to note is you can't represent all numbers in $$$[n+3, n^2-3]$$$ by picking three numbers that appear $$$x$$$, $$$1$$$ and $$$n-x-1$$$ times.

    For eg. there is no such representation for $$$n = 4, k = 10$$$.

    Good news is all these numbers can be represented by picking $$$2$$$ numbers, one appearing $$$2$$$ times and other appearing $$$n-2$$$ times. So, you can use the square obtained from case 4 here.

    I think your code is automatically doing this, so it should be fine.

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      6+2+1+1=10? UPD:sorry, I may be blind

      • »
        »
        »
        »
        13 days ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Oh you are right. I might have written my brute force wrong then. My bad.

        Edit: Oh no, my code is correct. 6+2+1+1 is wrong because if n = 4 you can't use 6.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    For me randomized greedy swaps worked well for almost all cases. I started with a random cyclic shift matrix with 1s on the diagonal if $$$k < n^2/2$$$ or with $$$n$$$s if $$$k > n^2/2$$$ and swapped greedily, minimizing the difference of the trace with $$$k$$$.

    Surprisingly, it did not work for $$$k \in {n+2,n^2-2}$$$ when $$$n$$$ is odd. Had to come up with a construction for that. Also the impossible case is $$$n=3 k=5$$$.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we use $$$T$$$ distinct values on the diagonal and each of these values has multiplicity at least $$$T$$$, then each square determined by a segment of identical values on the diagonal can accommodate the remaining matching for all the other $$$T - 1$$$ values, by a simple construction (basically each time we start out with a square of side at least $$$T$$$ with only one diagonal filled and we add $$$T - 1$$$ more diagonals in cyclical fashion).

    It turns out that the values of $$$K$$$ that cannot be represented in this manner exist only for $$$N <= 8$$$ $$$(*)$$$ and those can be brute-forced $$$(**)$$$.

    This solution has no pen-on-paper caseology, but $$$(*)$$$ and $$$(**)$$$, although intuitive to me, were leaps of faith and had to be tested, so the code is probably significantly longer.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I figured out a solution that uses no matching at all, just some Modular Arithmetic and a manageable case-by-case breakdown. Here is a link to the explanation of the solution and working code ($$$O(n^2)$$$ algorithm).

    Link : https://drive.google.com/open?id=1FUW3SovjVZMNHbo_I-zA0RZtcirwyA2d

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Even though I got more than 30 points(68 points).It shows a cross in front of Round 1A in the schedule in the qualified section.Is this a bug?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh thank God ! I freaked out thinking it's just me

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No It will be updated within a day. Last time it happened for me in Round 2 and got updated within a day.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I see on my page that I did not qualify for next round, even tho after finalized rank list. I have a score of 75. Why is this happening?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think they are updating. I also got the "not qualified" notification and also got the participation certificate but now both are gone and its showing "We are Reviewing".

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

can someone share solution for 4th or 5th problem if it is different from Analysis .Analysis solution is good but i want to know more approaches .It's fine if that is for partial points.

»
2 months ago, # |
  Vote: I like it -54 Vote: I do not like it

Can anybody please tell me where I went wrong for 3rd problem? I got a WA everytime. The sample test cases are working fine. Thanks in advance. //package main;

import java.util.ArrayList; import java.util.List; import java.util.Scanner;

public class Solution {

public long getStart() { return start; }

public void setStart(long start) { this.start = start; }

public long getEnd() { return end; }

public void setEnd(long end) { this.end = end; }

private long start; private long end;

public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); long test = sc.nextLong(); for (long t = 1; t <= test; t++) { long N = sc.nextLong(); List setJ = new ArrayList<>(); List setC = new ArrayList<>(); String ss = ""; boolean isImpossible = false;

for (long i = 0; i < N; i++) { Solution sol = new Solution(); sol.setStart(sc.nextLong()); sol.setEnd(sc.nextLong()); boolean J = setJ.stream().anyMatch(item -> { if (sol.getStart() >= item.getEnd()) { return false; } if (sol.getEnd() <= item.getStart()) { return false; } return true; }); if (!J) { setJ.add(sol); if (!isImpossible) { ss += "J"; } } else { boolean C = setC.stream().anyMatch(item -> {

if (sol.getStart() >= item.getEnd()) { return false; } if (sol.getEnd() <= item.getStart()) { return false; } return true;

}); if (!C) { setC.add(sol); if (!isImpossible) { ss += "C"; } } else { ss = "IMPOSSIBLE"; isImpossible = true; }

}

} System.out.println("Case #" + t + ": " + ss);

} sc.close(); }

}

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it -28 Vote: I do not like it

    Rather than down voting my comment is there any one who can really help out. Please?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      I don't think anyone would want to read that code. At least put it in pastebin or something

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the idea to solve the 4th problem (the interactive one)?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    I scan through symmetric pairs $$$(i, N + 1 - i)$$$. Note that if the two values are different, they stay different after any allowed transformation, and if they are equal — they stay equal. So I simply query the pairs and save the rsut, and then at 11th, 21th, ... queries I recheck one of the "equal" pairs if it has changed (1 query), and if it has, I update all the known "equal" pairs. Similarly is done for "different" pairs.

»
2 months ago, # |
  Vote: I like it +81 Vote: I do not like it

I am sure many of you must have noticed this but for those who didn't:

The name ESAb ATAd is Data Base after reversing the letters and taking "complement". (If we take complement to mean switching cases).

This is similar to how a similar problem last year was named "Dat Bae" which is "Data Base" missing two lettets a and s. And that problem was about losing bits in data!

»
2 months ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

Need help in the last problem,

It turned out for me that there are only 3 types of matrices needed. Where in the diagonal : 1) x appearing n times. 2) y and z appearing 1 time and x appearing n-2 times. 3) y appearing 2 times and x appearing n-2 times.

1) is simply shifted identity permutations.

2) is just swapping first row and second row,then we can swap 2 digits to get intended diagonal.

3) I did not found any direct solution. (btw we can easily do it when n is even.)

Does anyone know a constructive approach to build the matrix of type 3 ?? Thanks.

Edit : By constructive approach I mean a direct pattern based solution which we can perform by hand. I am not good with flows.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    I found such a construction for type 3 (assuming n is odd). It works as follows when n is odd and k=n+2:

    1. First create the diagonal: n-2 first values are 1's and 2 last values are 2's.
    2. In the upper-left (n-2)x(n-2) subgrid add 2 after every 1 and then add a diagonal pattern 3,4,...,n starting from rows 1,2,3,...
    3. In the upper-right 2*(n-2) subgrid add two vertical patterns 3,4,...,n starting from the two last rows.
    4. In the lower-left (n-2)*2 subgrid add two horizontal patterns 3,4,...,n starting from the first column and second last column.
    5. In the lower-right 2*2 subgrid add two 1's.

    In all steps the subgrid is circular, i.e., after the last row/column comes the first row/column. For example, the construction for n=7 and k=9 is here:

    1237654
    7124365
    4312576
    6541237
    2765143
    3456721
    5673412
    
    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      This was brilliant !! How did you come up with this approach ??

      Thank you.

      And thank you for your wonderful book Guide to CP. I started my journey from that.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        Great, thanks! I assumed that there has to be a construction where the main diagonal has n-2 1's and two 2's, and then tried many things using pen and paper until I found this.

»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Please Help! i have done a lot but unable to figure out :'(

I am trying to solve for D just for TestCase1 — only 10 bits are there (B=10) so we should just query each and output that. But why i am getting TLE even if i am exiting the code when i receive a 'N' from stream.

My code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i did this too but still TLE.

    code
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Leave it! I resolved by my own... Ahhh!

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What was the problem?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          If you look at the 3rd last line of solve function of my code... I have written -

          out.write(sb.toString());   // wrong earlier
          out.write(sb.toString()+"\n");  // correct Now
          

          Here was the problem. I was writing the correct output but was not going to the next line and hence it was unable to read "Y" or "N" even if I was reading it so waiting for it and results in TLE. So I must go to next line in order to read "Y" or "N".

          Here is the correct one

          Spoiler
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ohh, won't work for me(

            Ok, thanks

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have the same problem, only attempting to solve testcase 1. If i play the judge manually, it works. Why do I get TLE?

    import sys
    
    def solve(b):
        sol = [None] * b
        for i in range(b):
            print(i)
            sys.stdout.flush()
            sol[i] = input()
        print("".join(sol))
        sys.stdout.flush()
        judge_respons = input()
        if judge_respons == "N":
            sys.exit()
    
    T ,B = [int(x) for x in (input().split())]
    for _ in range(T):
        solve(B)
    
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      range(b) gives 0 to b-1 if I am not wrong. But you have to query 1 to b so you are not even demanding for 10th char and so judge response will never be N and hence leading to TLE.

»
2 months ago, # |
Rev. 2   Vote: I like it -51 Vote: I do not like it

Problem : Parenting Partnering

Verdict : WA

can anyone tell me what's wrong? If i calculate whether jaime or cameron are not free, results in an "IMPOSSIBLE" or Otherwise assign activity to whosoever is free.

Spoiler
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Analysis for the last problem says that there is a solution for all $$$k$$$ except $$$n + 1$$$ and $$$n^2 - 1$$$, but if we take $$$n = 3$$$ and $$$k = 5$$$ then only possible diagonal values are 1 2 2 and 1 1 3 which clearly does not work. Am I missing something here?

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    From the analysis:

    • show that all values for K between N and N^2 are possible with these constraints. (Note: you have to be a little careful with N = 3).

    In N=3 I think there are some exceptions you need to handle(like K=5, which is like you said only possible with 1 1 3 / 2 2 1), otherwise if (n-2) > 1 (which is True for any N>3, you can prove it.

»
2 months ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

Hi there,

I have a question about "Indicium". Is the following part of the editorial correct?

Now that we know what the diagonal looks like, how do we actually find a Latin square that has this diagonal? To do that, we will fill in the unfilled cells row by row. We will use bipartite matching to find a valid row. In one bipartition, we have N vertices for the N cells in that row. In the other bipartition, we have N vertices for the N numbers that can be placed into the cell. Make an edge between the cell vertex on the diagonal and the number vertex that was decided on. For every other cell, make an edge between a cell vertex and a number vertex if that number can be put into that cell without breaking the Latin square properties.

For example, N = 6, K = 8. This is my initial matrix.

12____
_12___
__12__
2__1__
____21
____12

Then, as the editorial mentioned, I used bipartite matching between N numbers and N cells row by row. However, I ran into the following case.

125634
612345
461253
2__1**
____21
____12 

I can only fill 6 into * but these * are in the same row.

In the end, I used bipartite matching between x and y with edges which were made by empty positions (x,y). Then I put a number into matched positions. It worked but I guess it would be a different idea...

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    If I understand correctly, they're fixing only(!) the values on the main diagonal. But you are fixing some additional values which are clearly not on the diagonal.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      Hi Vladyslav, thanks so much for your advice.

      I fixed numbers on the diagonal. However, a similar issue occurred.

      N=5 K=23

      5____
      _5___
      __5__
      ___4_
      ____4
      
      54321
      45132
      **5**
      ___4_
      ____4
      

      It is already impossible to put 4 into *'s row.

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 5   Vote: I like it +45 Vote: I do not like it

        From what I understand, Hall's Theorem guarantees that you will always succeed if you fill the square in one of these ways: a) complete row by complete row, or b) entering all instances of a single number at a time. (These are actually isomorphic methods, different views of the same mathematical objects.) However, you can't necessarily mix and match these approaches, and you can't do it row by row with some numbers fixed ahead of time.

        So if you start with:

        54___
        _54__
        4_5__
        ___45
        ___54
        

        You can then place all the 1s, then all the 2s, then all the 3s, and it will work.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Oh, well, I misunderstood the editorial. But now it makes sense. Thanks a lot!

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you elaborate on why Hall guarantees that?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              But this only shows it for completing it row by row (which is not what they're doing in the editorial since the diagonal elements are already fixed).

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                It's isomorphic. ie, instead of choosing N values to place into row 1, you're choosing N heights at which to place each of the 1s.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thanks! although this lack the last couple of slides in which he explain where it is true for a already filled matrix :P

              Also he left the title אלגוריתמים, which is Algorithms in Hebrew. Apparently some Israely guy is giving this course and he forgot to change the title for Cal-tech student Haha

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 2   Vote: I like it +21 Vote: I do not like it

            I mean, it's not like I had any clue about this during the contest. I only learned about it from reading the editorial. :)

            But I think the idea is: suppose you've already placed numbers 1..k, so each row/column has N-k slots free. Take any set of i rows, and suppose there are j total columns that have free slots in those rows (the union of column choices, which is what Hall's theorem cares about). Then, counting by rows, we must have exactly i*(N-k) free slots in that i x j submatrix. But counting by columns, there can be at most j*(N-k) free slots in that submatrix. So j >= i, and Hall's theorem is satisfied. Thus there's always a perfect matching that allows you to place all the "k+1"s.

            Just to help visualize this, suppose N=8, k=6, and you try to construct a case where i=4, j=3. You can try to fill in the rows thusly (# is a filled slot, — is an empty slot):

            #####-#-
            #####--#
            ######--
            #####-#-
            ????????
            ????????
            ????????
            ????????
            

            This looks fine if you're only considering the rows, but when you look at the columns, you can see that the j=3 rightmost columns have i*(N-k)=8 empty slots, more than the j*(N-k)=6 they're allowed.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Thank you so much! I get now why Halls applies here at last <3

              Single question that still bothers me, is that while what you explain is true in the general case, in our case when filling the numbers we have another constraints on where in the diagonal they are supposed to be.

              So after filling the first K=2 element of the diagonal in the matrix, we get something along this:

              1__2__
              _21___
              2_3__1
              _1_42_
              ___152
              __2_16
              

              Now the first row have 4 empty locations, but the forth has 3. So when conducting Hall for 3, the rows available are {0,1,3,4,5} and the columns available are the same, but some columns appear on edges N-K times, and some N-K-1. The same for rows.

              This means that when selecting a set of rows you get between (N-K-1)*I to (N-K)*I, and then there is at most (N-K)*J. So there might be a situation in which I > J.

              What am I missing?

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          But how do you get the initial matrix? The editorial shows how to get the numbers on the diagonal but how do you fill in the 4s and 5s (in this case) that are off-diagonal before you start the "entering all intances of a single number at a time" method? You cannot prove that bipartite matching is going to work for those since the 4s and 5s are already partially filled, right? Can you use backtracking, is it guaranteed to be fast enough assuming we have at most 3 distinct diagonal elements as they do in the editorial?

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 2   Vote: I like it +14 Vote: I do not like it

            Right, Hall's Theorem doesn't guarantee that you can place the rest of the 4s and 5s after fixing them on the main diagonal (and in some cases you actually need to place three distinct numbers). But it's not nearly as hard to place these initial numbers as it is to fill in the rest of the square. Like you said, you can run a backtracking search and observe that (except on obviously impossible cases like 5,5,5,5,4) it always runs quickly — even though you haven't proven it. Or you can figure out a general construction by hand.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it +3 Vote: I do not like it

              Thanks, that makes sense. And also thanks for the screencast, I didn't think I was "just wasting my time" ;)

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it +20 Vote: I do not like it

                I looked at xiaowuc1's AC solution, and his idea is to only consider the lexico-smallest valid diagonal (except those with one number appearing exactly $$$n-1$$$ times) and try to fill the rest of the grid number by number, first taking care of the numbers that appear on the diagonal. If I understood the above discussion correctly, this should not always work right (or at least it needs some more proving)?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it +10 Vote: I do not like it

                  In stress-testing, my solution RTEs on the case N=7, K=32.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me to find the bug of Problem C?

Code
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    You do not keep track of the initial ordering (after sorting, the order of events may differ from the order in the input). In your code, you store the index i of every pair, so instead of concat, you can write ss[ind] = 'J' or ss[ind] = 'C' respectively, where ind = v[i].second.second.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Qualifying Round:

Problem C- Parenting Partnering Returns

I wrote a solution to this problem which gave correct answers for the sample cases. And I later tested it with all sorts of corner cases that can come to my imagination, and found all of them right. Still, the verdict I received was nothing short of an WA. I would be ever thankful if anyone can help me out by finding the possible bug in my solution!

Here is my solution

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I don't know if this is the right place to post those but I couldn't find any better place where I will find so many relevent people.

As we all know Google Code Jam 2020 Qualification Round Ended. This is my first ever Google Code Jam and I don't have much information about that also. Currently Its showing 42points but I am confussed that its the finalised scoreboard or not. I have uploaded screenshoots of Code Jam Website and it seems like they haven't finalise the scoreboard but on the other hand I have seen so many posts on all social media platform people are saying that they are through to the next round.

Can Anyone please clearify this?

Thank You

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey! For Problem C, I had implemented a brute force solution that passed only TS-1 and TLE'ed on TS-2 yesterday. So, I started implementing something else this morning and submitted it (after contest was over). I get WA on TS-1 and so TS-2 gets skipped. However, for all hand made test cases that I've made, it seems to work. I also wrote a random test case generator and checker earlier today to verify and it seems to be working. Could anyone tell me what I'm doing wrong? Thanks in advance!

Idea
Code
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wasn't able to write qualification round because of some personal reason. Will i be able to give round 1A of codejam

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hi I wrote a solution for problem C,But I keep getting WA.It works fine on test inputs provided by them. It seems you can't get testSet of google code jam even after the competition is over.Can anybody see that what is the issue,for what edge cases it is failing,

Thanks, Best Regards

My Code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    is it really that hard to hide the code in spoilers and not eat up a tonne of scrolling space?

»
2 months ago, # |
  Vote: I like it -13 Vote: I do not like it

I just missed the qualification round and i'm so mad.is there another qualification round?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, can someone explain for me why just querying once could find the answer? It makes no sense at all since after the first query, the array already changes.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    the array changes just before you get answer to the first query so you can assume that the first change is after 10-th query.

»
2 months ago, # |
Rev. 2   Vote: I like it -31 Vote: I do not like it

Hi,

For problem D my idea was after every fluctuation (except the first) we have 4 times more possible answers. Then I eliminate them when the next bit that is queried is different and also different from -1 (initial value). Then when I had only 1 solution and all bits are different from -1, then it would be the answer.

But it didn't work ... The code is here, if someone can help me: https://pastebin.com/wmf1vSRN

Thank you.

[edit: add code here also]

import java.util.*;
import java.io.*;
import static java.lang.System.out;

/**
 * 
 * ESAb ATAd
 * 
 * 
 */
public class Solution {

	private static Scanner sc;

	public static void main(String[] args) throws Exception {

		sc = new Scanner(System.in);

		String[] tb = sc.nextLine().split(" ");
		int T = Integer.parseInt(tb[0]);
		int B = Integer.parseInt(tb[1]);
		System.err.println(T + " " + B);

		for (int t = 1; t <= T; ++t) {
			solve(t, B);
		}

		sc.close();

		// tests();
	}

	private static void solve(int t, int B) {

		List<int[]> list = new ArrayList<int[]>();
		int[] tmp1 = new int[B];
		Arrays.fill(tmp1, -1);
		list.add(tmp1);

		for (int i = 0; i <= 150;) {
			for (int b = 0; b < B && i <= 150; ++b) {
				if (list.size() == 1) {
					boolean isComplete = true;
					int[] l = list.get(0);
					for (int j = 0; j < B; j++) {
						if (l[j] == -1) {
							isComplete = false;
							break;
						}
					}
					if (isComplete) {
						StringBuilder answer = new StringBuilder();
						for (int j = 0; j < B; j++) {
							answer.append(l[j]);
						}
						out.println(answer.toString());
						String reply = sc.nextLine();
						System.err.println("Reply: " + reply);
						if ("Y".equals(reply)) return;
						else System.exit(-1);
					}
				}

				++i; out.println(b+1);
				int bit = Integer.parseInt(sc.nextLine());
				System.err.println(bit);
				final int idx = b;
				if (i % 10 != 1) {
					list.removeIf(l -> l[idx] != -1 && l[idx] != bit);
				}

				int size = list.size();
				for (int j = 0; j < size; j++) {
					int[] l = list.get(j);

					l[b] = bit;

					if (i > 1 && i % 10 == 1) {
						int[] inverted = invert(l, b);
						list.add(inverted);
						int[] tmp = reverse(l);
						list.add(tmp);
						tmp = reverse(inverted);
						list.add(tmp);
					}
				}
			}
		}
	}

	private static int[] invert(int[] array, int b) {
		int[] inverted = new int[array.length];

		for (int i = 0; i < inverted.length; i++) {
			if (i == b) {
				inverted[i] = array[i];
			} else if (array[i] == -1) {
				inverted[i] = -1;	
			} else {
				inverted[i] = array[i] == 0 ? 1 : 0;
			}
		}

		return inverted;
	}

	private static int[] reverse(int[] array) {
		int[] reversed = new int[array.length];

		for (int i = 0, j = array.length - 1; i < array.length/2; i++, j--) {
			reversed[i] = array[j];
			reversed[j] = array[i];
		}

		return reversed;
	}
}
»
7 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Gentle Reminder: Round 1A starts in 12 hours.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can I participate in Round 1B if I did not participate in qualification round and 1A?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      If you haven't participated in qualification round then you are not qualified to Round1. However, for those who qualified in Round1 and they did not take part on Round1A, they are allowed to take part in Round1B.

»
4 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Please check my solution for GCJ Round 1C Overexcited fan: https://youtu.be/lzPFSqe3_g4

»
2 weeks ago, # |
Rev. 2   Vote: I like it +65 Vote: I do not like it

I just received the following mail: (TL;DR: Codejam World Finals will be online)

"Hello, We wanted to provide an update regarding the Code Jam World Finals. We‘ve been closely monitoring the coronavirus (COVID-19) situation and after very careful consideration, we’ve decided the Code Jam World Finals will be entirely virtual this year taking place on Aug 8 at 13:00 UTC.

While we’re disappointed that we won’t be able to connect in-person in Munich, the health and safety of all finalists and volunteers is our top priority. We're still working out the details, but we'll be in touch again soon.

Please note that Round 2 and Round 3 will proceed as planned during their scheduled dates/times.

We will keep our Code Jam website updated with additional information. If you have any questions please contact codejam@google.com.

See you in Round 2, and best of luck! - The Code Jam Team"

I hope that this means that they can consider slightly increasing the number of finalists, to maybe say 50 like before!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    "I hope that this means that they can consider slightly increasing the number of finalists, to maybe say 50 like before!" — that would certainly be an interesting idea

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Or let's go back to 2008, where 100 finalists took part in the onsite contest!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    So that now I will be outside top-50 instead of top-25? No thanks, being outside top-25 is embarassing enough.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +94 Vote: I do not like it

      There's also a possibility to invite top (x-1), where x will be your position in round 3.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it +39 Vote: I do not like it

    But to be honest, I believe that the number of finalists won't be changed, because the rules for this year were already established.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      If you try real hard, I believe that you can think of another established rule of the competition that was broken because of covid-19.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        True, but there is a difference in changing the rules that in current circumstances are impossible to hold.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +12 Vote: I do not like it

      Maybe that is true. But I see value in changing the number of finalists, considering that Google invites top 100 contestants to onsite even for Codejam to I/O for women, and that field is definitely weaker than the open Codejam. Now they don't even have cost constraints, which should make it much easier for them to have more people participate. (If there are issues with cheating, rules such as in the Magnus Carlsen Invitational in chess can be established — webcam all around the coding arena keeping everything clearly visible, etc)

      I think it will also make for a much more interesting Round 3 — last year, I see that 500 people had non-zero scores, with only 598 people participating out of 1000. That means that many people like me probably scheduled something else on their weekend which was more worthwhile than a long shot at top 25.