Tima's blog

By Tima, history, 7 years ago, In English

Code Jam Round 1A starts in under 6 hours.

Let's discuss the problems here after the contest.

GL & HF.

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

How to solve problem 2?

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

    Binary search the time T.

    To answer whether you can process B bits with R cashiers, just calculate for every cashier and take top R, if their sum is greater than or equal to B then you can process B bits in time T with R cashiers.

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

      I have done the same thing. I don't know what's wrong with my code.

      Code
      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 2   Vote: I like it +42 Vote: I do not like it

        your inf is too small, the max answer is 1018 + 109.

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

          Even in small cases?

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

            In small cases it should be ok.

            Maybe your binary search is not correct.

            E.g. say lo = 0, hi = 5 and the correct answer is 1.

            You do the following:

            1) m = (0 + 5) / 2 = 2; since 2 >= 1, ans = 2, hi = 1
            2) m = (0 + 1) / 2 = 0; since 0 <= 1, lo = 1
            3) exit, answer is 2 which *is not correct*
            
            

            The proper binary search is:

            ll lo = some value when lo is not the answer (check(lo) does not hold);
            ll hi = some value when `hi` is answer (check(hi) holds);
            
            while (lo + 1 < hi) {
              ll mid = (lo + hi) / 2; // note that this could overflow in certain tasks, you can google how to avoid this
            
              if (check(mid)) {
                hi = mid;
              } else {
                lo = mid;
              } 
            }
            
            ll answer = hi;
            
            • for function check such check(x) <= check(x + 1) (00000....1111111)
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              But his loop is while (lo <= hi)

              So it should continue when both are 1.

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

                good catch =) then my concern is not valid

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

            You're using ios::sync_with_stdio(false); but with printf and cout both called.

            I think that's the reason. (It fails sample test on my PC)

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

              Yes, you are right. It is giving answer in correct format on local compiler. But when i checked it on ideone, it is giving answer in unexpected format. This must be the reason. Thanks cmd and t1016d for your help. I learnt a lesson never use printf and cout together.

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

                Actually you can use them together but don't use the two together along with ios::sync_with_stdio(false);

      • »
        »
        »
        »
        7 years ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        EDIT: nevermind, I was wrong.

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

After the GCJ Round 1A, Square869120Contest #5 will be held at Atcoder.
Let's participate and enjoy!!!!!
Contest Page

»
7 years ago, # |
  Vote: I like it +19 Vote: I do not like it

How to test a code after the contest?

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

    You can't (at least presently the feature isn't there)

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

It feels strange to fail hidden tests of problems 1 and 2 but to pass the third's one.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem 1 ? I think I have understood the logic, but I just couldn't solve the problem. Can anyone please look into my code ?

https://ideone.com/Kz1GgQ

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What's wrong with my B??? Isn't B just binary search + greedy? I get shocked seeing this fail the large test.

My solution

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

    The upper bound for the binary search should be at least 1e18 + 1e9, that's why.

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

      This is painful...

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

        I know right, I failed for the same reason. :(

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

          I got place 1511 because of that reason :(

          Edit: Haha. 2 weeks after the contest I got an email saying I advanced (I'm now at 1495). I guess some cheaters must have been kicked out.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So apparently Google Code Jam won't even show the reason for Runtime error, which is quite unfortunate.

Oh well, in my case the issue was me using a different g++ version and not specifying explicitly -std=c++11 flag.

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

    GCJ is using c++14 now.

    You can check here.

    Upd: fix the link

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

      Oh, thanks!

      I was pretty sure they used -std=c++11 during this year's Practice round, since I've seen in the FAQ. I guess they keep on changing stuff all the time, and it's best to always re-check the FAQ before each round.

»
7 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

What is a solution for C (Edgy Baking)?

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

    If we know which ones we'll cut we can calculate the range [l, r] perimeter lies within. The dp[l] = max possible r, so it's just knapsack. If p lies within some [l, dp[l]] range then answer is p, else answer is maximum dp[l] where l <= p. It's about 100 * 250 * 6 for one test.

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

    For one rectangle that is cut perimeter lies within [(a + b) * 2 + min(a, b) * 2, (a + b) * 2 + hypot(a, b) * 2]

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

      can someone help me debug my C-large, I have no idea why this failed.

      EDIT: I figured my own bug.

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

    I solved problem C with DP.

    You can replace the problem with following problem:

    You are given N intervals: [Li, Ri]. You can choose any subset of intervals.
    You can choose number which included in each interval in subsets.
    The goal is to set total number you chose closer to P (not larger than P.)

    You can solve this problem with DP because Li is always an integer.
    Let dp[pos][minimum] be the maximum value of "sum of Ri in the subset" which looks from interval 1 to pos and "sum of Li in the subset" is minimum.

    The transition of DP is as follows:
    dp[pos + 1][minimum] = max(dp[pos + 1][minimum], dp[pos][minimum])
    dp[pos + 1][minimum + Lpos] = max(dp[pos + 1][minimum + Lpos], dp[pos][minimum + Rpos])

    The complexity is O(N * (H1 + H2 + ... + HN)).

    Code

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

    Can someone help me debug C large, I copied the dp solution written elsewhere here but I get the same answers on 10000+ random inputs. I got WA on the contest on the function "solve"

    https://hastebin.com/lovudorume.py

»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

How to see friend standings?

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

    This feature too isn't available in the new interface

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

    I have updated scoreboard with round 1a results here https://codejam.herokuapp.com/ you can filter by country and handle(s). Still under grace period of heroku database free plan overuse.

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

      Not all heroes wear capes :) Thanks!

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

      Is it working when the contest is running? or it's just the results after the contest.

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

        No, it is not working during the contest.

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

          @bula do you plan to add round 1B as well? it would be nice :)

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

            Round 1B is uploaded but the access is significantly slower since database is relocated so please be patient when browsing :)

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

            Round 1C uploaded.

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

              I got this message when loading the scoreboard.

              DataTables warning: table id=table_id - Ajax error. For more information about this error, please see http://datatables.net/tn/7

              Could you check it?

              Thanks for the well-compiled scoreboard!

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

                Just fixed, now it should be more responsive, also.

»
7 years ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

Problem A with a very little difference:

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution received TLE. There are 100 test cases and time limit is 15 seconds so it should not happen, right?

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

    6 * 109 ops would probably be touching the limits if we assume 3 * 108 ops per second

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder if somebody had similar feeling that B easy was harder than B hard. I already encountered this situation 2 years ago in 1C problem.

I was trying to check every mask of R cashiers out of C and then what? How to optimally assign B bits to given set of R cashiers?

I think that if the problem was given with smaller constraints it would be much harder/trickier to solve, as it would be much more difficult to get BS idea.

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

    How to optimally assign B bits to given set of R cashiers?

    No, you don't.

    Simply enumerate all the possible assignment if you're solving only small task.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Its really bad that we can't upsolve problems after the contest. Its really important for us as you already know. We can't even download sources of people who got full score and create our own testcases and after test our source with these testcases (not the best solution but from nothing its better). So please if anyone who got full score in any problem and wants to help, could share his/her sources ? Thank you !

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

    Exactly. I immediately need to upsolve Problem A, and there seems to be no option. I can't even know the Test Case where I failed.

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

    It should be possible — from next Thursday according to this post:

    We'll be holding a one-week optional practice session between Thursday, April 19th at 18:00 UTC and Thursday, April 26th at 18:00 UTC, so contestants can test solutions and continue to practice on problems from the Qualification Round and Round 1A. Anyone can join, so mark your calendars and we'll send out more details next week!

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

      I sent them email at least to provide testcases as they did last year. From the message you sent I understand that we will be able to practice in old contests only in the week they say, or whenever we want ?

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have an interesting solution for problem C that works in O(n^3) which was inspired by IOI 2016 Molecules.

WLOG, all widths<=heights and the optimal solution requires cutting at least 3 cookies. Let's iterate over all unordered triples of cookies (A, B, C) and let A, B, and C have the greatest widths among the cookies that will be cut.

WLOG, let C have the smallest width among the triple. The length of the range of possible perimeters when A, B, and C are cut is at least 3*2*(sqrt2-1)*C.width (the smallest cut is C.width and the largest is sqrt2*C.width).

If an additional cookie is cut (remember that the widths of additional cookies <= C.width), the lower bound of the range will increase by at most 2*C.width. Because 3*2*(sqrt2-1)*C.width > 2*C.width, the new lower bound must be smaller than the previous upper bound, and no values will be skipped if we cut an additional cookie. Thus, we can just cut all cookies with widths <= C.width and the answer for a triple is min(upper bound, maximum perimeter).

AC solution without template
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Unfortunately I could not wake up for the round and now I can't find the problemset. Anybody knows where can I see the problems?

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

Can someone help me with problem 2? I thought O(60 * R * C) was good enough to pass but turned out TLE.

My solution

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

    You need to find the sum of the R maximum numbers in the array items. This can be done faster than R * C.

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

      Thank you for your reply, I know I can do it, but my main point is, why R * C solution got TLE

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

        There are 100 test cases. So you do ~6 * 109 operations.

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to submit after contest?