Google Code Jam Round 1A

6 years ago, # |

+12

How to solve problem 2?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+20

Binary search the time T.

To answer whether you can process B bits with R cashiers, just calculate $\text{[math]}$ 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.

→ Reply

gauravsharma

6 years ago, # ^ |

← Rev. 2 →

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

Code

#include <bits/stdc++.h>

using namespace std;
#define fast ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
#define pb push_back
#define sz(s) (int)s.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i,n) for(int i=0;i<(int)n;i++)
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define ford(i, b, a) for (int i = (int)(b); i >= a; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
const ll N = (ll)1e3+7;
const ll inf = (ll) 1e18+7;
const ll mod = (ll) 1e9+7;
const ld pi = acos(-1);

template<typename T> T gcd(T a,T b) { if(a==0) return b; return gcd(b%a,a); }
template<typename T> T pow(T a,T b, ll m){T ans=1; while(b>0){ if(b%2==1) ans=(ans*a)%m; b/=2; a=(a*a)%m; } return ans%m; }

ll n,k,r,b,c;
ll m[N],s[N],p[N];
vl v;

bool go(ll T) {
    n = 0;
    v.clear();
    for1(i, c) {
        v.push_back(min(m[i], max(0LL, T &mdash; p[i]) / s[i]));
    }
    sort(rall(v));
    forn(i, r) {
        n += v[i];
    }
    return n >= b;
}

void solve() {
    cin >> r >> b >> c;
    for1(i, c) {
        cin >> m[i] >> s[i] >> p[i];
    }

    ll lo = 0, hi = inf, ans = inf;
    while (lo <= hi) {
        ll m = (lo + hi) / 2;
        if (go(m)) {
            ans = min(ans, m);
            hi = m - 1;
        } else {
            lo = m + 1;
        }
    }
    cout << ans << '\n';
}

int main() {
    fast
//    freopen("/Users/gauravsharma/Downloads/B-large.in.txt", "r", stdin);
//    freopen("/Users/gauravsharma/Desktop/CJ/template/output.txt", "w", stdout);
    int t;
    cin >> t;
    for (int kase = 1; kase <= t; kase++) {
        printf("Case #%d: ", kase);
        solve();
    }
    return 0;
}

→ Reply

6 years ago, # ^ |

← Rev. 2 →

+42

your inf is too small, the max answer is 10¹⁸ + 10⁹.

→ Reply

gauravsharma

6 years ago, # ^ |

Even in small cases?

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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)

→ Reply

6 years ago, # ^ |

But his loop is while (lo <= hi)

So it should continue when both are 1.

→ Reply

6 years ago, # ^ |

good catch =) then my concern is not valid

→ Reply

6 years ago, # ^ |

+29

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)

→ Reply

gauravsharma

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

+27

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

→ Reply

Neil

6 years ago, # ^ |

← Rev. 3 →

EDIT: nevermind, I was wrong.

→ Reply

E869120

6 years ago, # |

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

→ Reply

Omar_Morsi

6 years ago, # |

+19

How to test a code after the contest?

→ Reply

6 years ago, # ^ |

+11

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

→ Reply

https://ideone.com/Kz1GgQ

6 years ago, # |

← Rev. 2 →

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

→ Reply

Mohinem

6 years ago, # |

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 ?

→ Reply

xuanquang1999

6 years ago, # |

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

My solution

→ Reply

noelnadal

6 years ago, # ^ |

+16

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

→ Reply

xuanquang1999

6 years ago, # ^ |

+26

This is painful...

→ Reply

noelnadal

6 years ago, # ^ |

+21

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

→ Reply

Chilli

6 years ago, # ^ |

← Rev. 2 →

+24

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.

→ Reply

Epiq

6 years ago, # |

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.

→ Reply

6 years ago, # ^ |

← Rev. 2 →

GCJ is using c++14 now.

You can check here.

Upd: fix the link

→ Reply

Epiq

6 years ago, # ^ |

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.

→ Reply

Epiq

6 years ago, # |

← Rev. 2 →

What is a solution for C (Edgy Baking)?

→ Reply

6 years ago, # ^ |

+10

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.

→ Reply

https://hastebin.com/lovudorume.py

6 years ago, # ^ |

+10

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

→ Reply

redocyz

6 years ago, # ^ |

← Rev. 2 →

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

EDIT: I figured my own bug.

→ Reply

E869120

6 years ago, # ^ |

+42

I solved problem C with DP.

You can replace the problem with following problem:

You are given N intervals: [L_i, R_i]. 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 L_i is always an integer.
Let dp[pos][minimum] be the maximum value of "sum of R_i in the subset" which looks from interval 1 to pos and "sum of L_i 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 + L_pos] = max(dp[pos + 1][minimum + L_pos], dp[pos][minimum + R_pos])

The complexity is O(N * (H₁ + H₂ + ... + H_N)).

Code

→ Reply

alexwice

6 years ago, # ^ |

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"

→ Reply

jcvb

6 years ago, # |

+11

How to see friend standings?

→ Reply

6 years ago, # ^ |

This feature too isn't available in the new interface

→ Reply

6 years ago, # ^ |

+65

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.

→ Reply

6 years ago, # ^ |

Not all heroes wear capes :) Thanks!

→ Reply

eagle93

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

No, it is not working during the contest.

→ Reply

gilcu3

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

Round 1C uploaded.

→ Reply

6 years ago, # ^ |

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!

→ Reply

6 years ago, # ^ |

+10

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

→ Reply

YANORMALNOSUPERGOOD

6 years ago, # |

← Rev. 2 →

+30

Problem A with a very little difference:

→ Reply

SureYeaah

6 years ago, # |

My $\text{[math]}$ solution received TLE. There are 100 test cases and time limit is 15 seconds so it should not happen, right?

→ Reply

6 years ago, # ^ |

6 * 10⁹ ops would probably be touching the limits if we assume 3 * 10⁸ ops per second

→ Reply

SureYeaah

6 years ago, # ^ |

Shit I assumed log is small -_-

→ Reply

P___

6 years ago, # |

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.

→ Reply

6 years ago, # ^ |

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.

→ Reply

Hepic_Antony_Skarlatos

6 years ago, # |

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 !

→ Reply

Mohinem

6 years ago, # ^ |

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.

→ Reply