Code Jam Round 1A starts in under 6 hours.
Let's discuss the problems here after the contest.
GL & HF.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
How to solve problem 2?
Binary search the time
T
.To answer whether you can process
B
bits withR
cashiers, just calculate for every cashier and take topR
, if their sum is greater than or equal toB
then you can processB
bits in timeT
withR
cashiers.I have done the same thing. I don't know what's wrong with my code.
your
inf
is too small, the max answer is 1018 + 109.Even in small cases?
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 is1
.You do the following:
The proper binary search is:
check
suchcheck(x) <= check(x + 1)
(00000....1111111
)But his loop is
while (lo <= hi)
So it should continue when both are 1.
good catch =) then my concern is not valid
You're using
ios::sync_with_stdio(false);
but withprintf
andcout
both called.I think that's the reason. (It fails sample test on my PC)
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.
Actually you can use them together but don't use the two together along with ios::sync_with_stdio(false);
EDIT: nevermind, I was wrong.
After the GCJ Round 1A, Square869120Contest #5 will be held at Atcoder.
Let's participate and enjoy!!!!!
Contest Page
How to test a code after the contest?
You can't (at least presently the feature isn't there)
It feels strange to fail hidden tests of problems 1 and 2 but to pass the third's one.
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
What's wrong with my B??? Isn't B just binary search + greedy? I get shocked seeing this fail the large test.
My solution
The upper bound for the binary search should be at least 1e18 + 1e9, that's why.
This is painful...
I know right, I failed for the same reason. :(
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.
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.GCJ is using c++14 now.
You can check here.
Upd: fix the link
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.What is a solution for C (Edgy Baking)?
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.
For one rectangle that is cut perimeter lies within [(a + b) * 2 + min(a, b) * 2, (a + b) * 2 + hypot(a, b) * 2]
can someone help me debug my C-large, I have no idea why this failed.
EDIT: I figured my own bug.
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
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
How to see friend standings?
This feature too isn't available in the new interface
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.
Not all heroes wear capes :) Thanks!
Is it working when the contest is running? or it's just the results after the contest.
No, it is not working during the contest.
@bula do you plan to add round 1B as well? it would be nice :)
Round 1B is uploaded but the access is significantly slower since database is relocated so please be patient when browsing :)
Round 1C uploaded.
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!
Just fixed, now it should be more responsive, also.
Problem A with a very little difference:
My solution received TLE. There are 100 test cases and time limit is 15 seconds so it should not happen, right?
6 * 109 ops would probably be touching the limits if we assume 3 * 108 ops per second
Shit I assumed log is small -_-
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.
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.
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 !
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.
It should be possible — from next Thursday according to this post:
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 ?
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).
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?
https://codejam.withgoogle.com/2018/challenges
Thank you.
Can someone help me with problem 2? I thought O(60 * R * C) was good enough to pass but turned out TLE.
My solution
You need to find the sum of the R maximum numbers in the array items. This can be done faster than R * C.
Thank you for your reply, I know I can do it, but my main point is, why R * C solution got TLE
There are 100 test cases. So you do ~6 * 109 operations.
How to submit after contest?
ojuz, any progress on uploading the problems?