Google Code Jam Round 1A

→ Обратите внимание

До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	nor	152

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Google Code Jam Round 1A

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

Code Jam Round 1A starts in under 6 hours.

Let's discuss the problems here after the contest.

GL & HF.

+116

Tima
7 лет назад
64

Комментарии (62)

Показать архивные | Написать комментарий?

madn

7 лет назад, # |

+12

How to solve problem 2?

→ Ответить

cmd

7 лет назад, # ^ |

← 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.

→ Ответить

gauravsharma

7 лет назад, # ^ |

← 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;
}

→ Ответить

cmd

7 лет назад, # ^ |

← Rev. 2 →

+42

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

→ Ответить

gauravsharma

7 лет назад, # ^ |

Even in small cases?

→ Ответить

cmd

7 лет назад, # ^ |

← 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)

→ Ответить

t1016d

7 лет назад, # ^ |

But his loop is while (lo <= hi)

So it should continue when both are 1.

→ Ответить

cmd

7 лет назад, # ^ |

good catch =) then my concern is not valid

→ Ответить

t1016d

7 лет назад, # ^ |

+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)

→ Ответить

gauravsharma

7 лет назад, # ^ |

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.

→ Ответить

pleasant

7 лет назад, # ^ |

+27

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

→ Ответить

Neil

7 лет назад, # ^ |

← Rev. 3 →

EDIT: nevermind, I was wrong.

→ Ответить

E869120

7 лет назад, # |

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

→ Ответить

Omar_Morsi

7 лет назад, # |

+19

How to test a code after the contest?

→ Ответить

pleasant

7 лет назад, # ^ |

+11

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

→ Ответить

madn

7 лет назад, # |

← Rev. 2 →

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

→ Ответить

Mohinem

7 лет назад, # |

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

→ Ответить

xuanquang1999

7 лет назад, # |

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

My solution

→ Ответить

noelnadal

7 лет назад, # ^ |

+16

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

→ Ответить

xuanquang1999

7 лет назад, # ^ |

+26

This is painful...

→ Ответить

noelnadal

7 лет назад, # ^ |

+21

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

→ Ответить

Chilli

7 лет назад, # ^ |

← 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.

→ Ответить

Epiq

7 лет назад, # |

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.

→ Ответить

t1016d

7 лет назад, # ^ |

← Rev. 2 →

GCJ is using c++14 now.

You can check here.

Upd: fix the link

→ Ответить

Epiq

7 лет назад, # ^ |

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.

→ Ответить

Epiq

7 лет назад, # |

← Rev. 2 →

What is a solution for C (Edgy Baking)?

→ Ответить

madn

7 лет назад, # ^ |

+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.

→ Ответить

madn

7 лет назад, # ^ |

+10

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

→ Ответить

redocyz

7 лет назад, # ^ |

← Rev. 2 →

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

EDIT: I figured my own bug.

→ Ответить

E869120

7 лет назад, # ^ |

+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

→ Ответить

alexwice

7 лет назад, # ^ |

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

→ Ответить

jcvb

7 лет назад, # |

+11

How to see friend standings?

→ Ответить

pleasant

7 лет назад, # ^ |

This feature too isn't available in the new interface

→ Ответить

bula

7 лет назад, # ^ |

+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.

→ Ответить

pleasant

7 лет назад, # ^ |

Not all heroes wear capes :) Thanks!

→ Ответить

eagle93

7 лет назад, # ^ |

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

→ Ответить

bula

7 лет назад, # ^ |

No, it is not working during the contest.

→ Ответить

gilcu3

7 лет назад, # ^ |

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

→ Ответить

bula

7 лет назад, # ^ |

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

→ Ответить

bula

7 лет назад, # ^ |

Round 1C uploaded.

→ Ответить

t1016d

7 лет назад, # ^ |

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!

→ Ответить

bula

7 лет назад, # ^ |

+10

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

→ Ответить

YANORMALNOSUPERGOOD

7 лет назад, # |

← Rev. 2 →

+30

Problem A with a very little difference:

→ Ответить

SureYeaah

7 лет назад, # |

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

→ Ответить

pleasant

7 лет назад, # ^ |

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

→ Ответить

SureYeaah

7 лет назад, # ^ |

Shit I assumed log is small -_-

→ Ответить

P___

7 лет назад, # |

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.

→ Ответить

t1016d

7 лет назад, # ^ |

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.

→ Ответить

Hepic_Antony_Skarlatos

7 лет назад, # |

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 !

→ Ответить

Mohinem

7 лет назад, # ^ |

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.

→ Ответить

bula

7 лет назад, # ^ |

← Rev. 2 →

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!

→ Ответить

Hepic_Antony_Skarlatos

7 лет назад, # ^ |

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 ?

→ Ответить

tmwilliamlin168

7 лет назад, # |

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

public class Solution {
	public static void main(String[] args) {
		int tt=in.nextInt();
		for(int ti=1; ti<=tt; ++ti) {
			out.print("Case #"+ti+": ");
			int n=in.nextInt(), p=in.nextInt(), bp=0;
			Pair[] ps = new Pair[n];
			for(int i=0; i<n; ++i) {
				ps[i] = new Pair(in.nextInt(), in.nextInt());
				bp+=2*(ps[i].a+ps[i].b);
			}
			double ans=bp;
			Arrays.sort(ps);
			double[] ps2 = new double[n+1];
			for(int i=0; i<n; ++i)
				ps2[i+1]=ps2[i]+hypot(ps[i].a, ps[i].b)*2;
			for(int i=0; i<n; ++i) {
				if(bp+ps[i].a*2<=p)
					ans=max(min(bp+hypot(ps[i].a, ps[i].b)*2, p), ans);
				else
					break;
				for(int j=i+1; j<n; ++j) {
					if(bp+(ps[i].a+ps[j].a)*2<=p)
						ans=max(min(bp+(hypot(ps[i].a, ps[i].b)+hypot(ps[j].a, ps[j].b))*2, p), ans);
					else
						break;
					for(int k=j+1; k<n; ++k) {
						if(bp+(ps[i].a+ps[j].a+ps[k].a)*2<=p)
							ans=max(min(bp+(hypot(ps[i].a, ps[i].b)+hypot(ps[j].a, ps[j].b)+hypot(ps[k].a, ps[k].b))*2+ps2[i], p), ans);
						else
							break;
					}
				}
			}
			out.println(ans);
		}
	}
	static class Pair implements Comparable<Pair> {
		int a, b;
		Pair(int a, int b) {
			this.a=min(a, b);
			this.b=max(a, b);
		}
		public int compareTo(Pair o) {
			return a-o.a;
		}
	}
}

→ Ответить