Round 1B of the Google CodeJam contest just finished. What are your thoughts/comments on this round? I found the problems to be a bit unbalanced in difficulty which resulted in a lot of ties.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Round 1B of the Google CodeJam contest just finished. What are your thoughts/comments on this round? I found the problems to be a bit unbalanced in difficulty which resulted in a lot of ties.
Name |
---|
Read the first problem wrong 3 times which resulted in 3 penalty attempts and a solve time of 29 mins. I also had a '<' instead of '>' in problem B which took me another 20 mins to find. Guess I shouldn't have stayed up till 5 AM to participate in the Kickstart round. Fortunately, I did qualify, albeit ranking 1500th.
Same situation here but the first problem statement costed me the whole contest and I failed to qualify.
In 2nd task, Why 1e9 dp solutions(n*p*p) are passing ?
P is only 100 so it's not 1e9 it's 1e3*1e2*1e2 = 1e7
t*n*p*p ~ 1e9
I used dp to solve it in t * n * p. but their t * n * p * p passed because I think all of the test cases don't have optimal n and p. Or maybe just the TL was a bit high.
That would be roughly 1e9 operations for all the test cases which should pass given the 5sec TL.
You do not need to maintain all 100 possible ending spots, only the largest and smallest one. You can prove that ending a customer on an item that is not the largest or the smallest is never optimal, hence make the dp noticeably faster.
P-100, N=1000 and T=100, which makes it 1e5*1e2*1e2 = 1e7 as input. I have seen rarely people giving 1e7 numbers as input. Input can be at max 1e6 numbers in standard situation. Which makes in 1e6*1e2=1e8... which will easily pass under 5sec.
Input can be at max 1e6 numbers in standard situation.
Shouldn't this be specified?
I have seen rarely people giving 1e7 numbers as input.
That does not mean a test case with 1e7 numbers violates the constraints.
TBH this situation is not very simple. Yes, as a participant it is my fault that I did not ask for clarifications (not sure if it would have been provided), but such an ambiguity should not exist in the first place itself.
IMO, Code Jam team should either update their test cases and rejudge solutions, or consider all AC solutions and take the earliest attempt with highest sum instead of last one. They can also choose to consider ones being affected as a smaller fraction and thus ignore them, but that would be exercising authority more than delivering justice.
I don't know if it was actually $$$10^9$$$ or not, but in some cases, using $$$dp$$$ with arrays can pass $$$2s$$$ time limit easily. This could be due to small constant factor of arrays.
Has anyone solved Problem C using any Probabilistic methods ? I tried using "00000001" with set bit uniformly distributed over all the 8 indices , I observed this operation would either increase the count of set bits or decrease .. ( Tried but figured that It won't work , as when we had very few bits in judges hidden input , it is very low probability to get a hit)
I just queried
00000000
and then kept querying for strings with the first $$$N_i$$$ bits being1
unless we get $$$0$$$ or $$$8$$$ as a response. Did not prove it but it felt like a good strategy. :PI just spammed guesses. Whenever you get $$$d$$$ digits as the answer of the previous query, send in a random $$$8$$$-bit guess with $$$d$$$ ones.
How to solve C1. Can anyone provide the solution with short explanation.
if Ni > 4 you can reduce it to Ni <= 4 by choosing V = 11111111.
And for any case where Ni < 4 I keep choose a random V with Ni set bits until Ni = 0
I did something similar , But How were you handling cases when Ni got equal to small values like maybe 1 or 2?
here is my solution
I handled the case where Ni equal to 2 in function case_2(), the logic is easy to understand. I'm just generating a random string with 2 set bits until Ni is something different than 2 [1,3 or 4]. this is working because r is chosen uniformly at random.
can you please provide your solution too.
While the input is d != 0, output a random bitset with d ones, and hope that: 1. it's the same bitset up to rotations 2. the correct rotation will be chosen
The chances of the first one being correct are pretty high (More than 1/12 I think) The chances of the second one being correct are not less than 1/8
So overall pretty good probabilistic algorithm
Here's an inefficient example for such algorithm:
I was outputting not a random bitset, but the one starting with d ones, and then (8-d) zeroes. Thought no need to make it random, since there will be a shift anyways. Still passed C1.
Yep you are right! Implementing excessive / uneeded solutions was today's theme for me ;) (LIS at A)
It was like DIV3 contest up until C2. While I managed to get top 150, it wasn't fun round for me...
I think the second problem has bad restrictions, N * P^2 solutions pass and it was quite risky to submit such solutions given the time limit. Also, the editorial does not mention this solution so I suppose it wasn't intended to pass.
Where is the editorial solution can you please share ?
Open problem -> Analysis (under Submissions section)
I have a tech question for someone way more familiar than me with C++.
I was using variable name
data
for a long time. However today I got compilation error which was fixed after I renamed variabledata
tod
.I cannot reproduce this locally using C++17. Removing either first or second line makes it compile. Can anyone explain what exactly is failing and why I might not be able to reproduce this locally? Thanks!
I think it's because of your compiler version being different. However, I haven't been able to not reproduce this error on any common compiler on godbolt (including recent enough versions of GCC, i.e., >= 8.1). Are you sure you're compiling with flags like
-std=c++17
or--std=c++17
or--std=gnu++17
, since it compiles fine with C++14 and earlier. The reason is C++17 has a function in the standard library calledstd::data
and C++14 doesn't, so there is an ambiguity when you usedata
while doingusing namespace std;
.I'll blame my particular compiler (
g++.EXE (tdm64-1) 5.1.0
) which is an old version of tdm-gcc, which does compile successfully while specifying--std=c++17
.If I test g++ in Windows Subsystem for Linux (
g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
) it indeed errors out.I guess I expected the compiler to either compile error or complain about
--std=c++17
, but maybe in my old compiler version C++17 was experimental and not yet feature complete.Anyway, thanks a lot for looking into this!
My experience-
Solve A, B, and C1 and somehow manage to clear cutoff.
Look at the constraints of B and overthink a lot. "T*N*P*P=10^9, will never pass under 5sec in java"
Resubmit B after modifying solution.
Realize after contest that the first solution passes as well.
Get kicked out. :)
I enjoyed the problems.
Problem 1 analysis: I think the section labelled "Test Set 2" should be labelled "Test Set 3": https://codingcompetitions.withgoogle.com/codejam/round/000000000087711b/0000000000acd59d#analysis
(I can't find where to report this to the Google folks)
Regarding the alternative solution in problem C analysis, in the step of using V as the $$$i^{th}$$$ instruction in P[K-1] appended with $$$2^{k-1}$$$ zeros (when the assumption of the left half being equal to the second half turns to be invalid), what is the proof that this will definitely make the 2 halves equal at some point in time?
If we have a sequence P[k-1] which we know will take 2^(k-1) bits and have it reach 0 at some point (no matter how you rotate each item in the sequence), we can append 0's to each element of that sequence to make the both halves equal at some point. This is true because if we take the xor of both halves, we can treat this as an imaginary smaller record. Each step of our sequence (with appended 0's) affects this smaller record the same way it would affect a normal record of that size. (Cyclic rotations don't matter the same way they don't matter for P[k-1])
If the xor of both halves reaches 0 at some point (which it must as described above), then that means both halves will eventually be equal.
NVM, just got it, thanks!
I got it now, thanks a lot tbuzzelli!
So the solution description can be rephrased as follows:
For an initial value $$$IV$$$ with $$$2^k$$$ bits ($$$k>0$$$). Assuming $$$IV[2^k-1:2^{k-1}]$$$ is $$$L$$$, $$$IV[2^{k-1}-1:0]$$$ is $$$R$$$, $$$L$$$ $$$xor$$$ $$$R$$$ is $$$LR$$$, and a sequence $$$P[k-1]$$$ that will reset any $$$(k-1)$$$-bits initial value at some step regardless of the rotations. Some observations regarding the $$$I^{th}$$$ instruction $$$INS_i$$$ in $$$P[k-1]$$$:
When $$$L=R$$$, $$$LR$$$ will be $$$0$$$, and applying $$$INS_i+INS_i$$$ one by one will make $$$L=0$$$ and $$$R=0$$$ at the same time. $$$L=R$$$ should hold (and applying $$$INS_i+INS_i$$$ one by one will make $$$IV=0$$$ accordingly) either before applying $$$INS_1+0's$$$, or after $$$INS_1+0's$$$, or after $$$INS_2+0's$$$, ..., or after $$$INS_i+0's$$$.
The first problem statement cost me a lot, and I was getting frustrated why I was getting WA, and total submission was increasing at a fast rate. Then to qualify, I had to do all questions (At least till 3A), which I couldn't. Hence now it all goes to final round 1C, hoping for the best.
An amazing fact: Problem C can be solved within just $$$16$$$ operations!
And my sad story: I insisted on working on this strategy but I failed to finish before the end of contest :( I thought the "300 operations" is just a red herring (or for the ease of first subtask) and missed the regular $$$(2^8-1)$$$-operation solution.
I want to share this solution to the community because I found it by mainly case work. I don't know if:
First check the total number of set bits by a $$$00000000$$$. If there are odd number of set bits, additionally use a $$$10000000$$$ to make the total set bits even.
The cases worthy of attention are $$$N = 2, 4, 6$$$. Consider the odd and even bits separately. Below I'll use $$$a + b$$$ as the notation of "$$$a$$$ set bits in one group and $$$b$$$ set bits in another group". Due to the uncertainty of rotation, we cannot distinguish odd bits from even bits. Similarly, an operation $$$x + y$$$ means "operate with a bitmask in which $$$x$$$ set bits in one group and $$$y$$$ set bits in another group". For example, operation $$$0 + 4$$$ means $$$10101010$$$ (or $$$01010101$$$).
In a few operations I'll make $$$a$$$ and $$$b$$$ both even.
If $$$N = 4$$$, sending a $$$0 + 4$$$ can make $$$a = b$$$. So if it results in $$$N = 2, 6$$$, we know it's $$$1 + 1$$$ or $$$3 + 3$$$, sending any $$$1 + 1$$$ (like $$$11000000$$$) to make $$$a$$$ and $$$b$$$ both even.
If $$$N = 2, 6$$$, we know it is $$$0 + 2$$$, $$$1 + 1$$$, $$$3 + 3$$$ or $$$2 + 4$$$. sending a $$$0 + 4$$$ results in $$$0 + 2$$$, $$$1 + 3$$$ or $$$2 + 4$$$. So if we get $$$N = 4$$$ as the result, just similarly send any $$$1 + 1$$$.
Now if still $$$N = 2, 4, 6$$$, there are even number of set bits in both odd and even bits. That means only $$$0 + 2$$$, $$$0 + 4$$$, $$$2 + 2$$$, $$$2 + 4$$$ are possible. If now $$$N = 4$$$, send a $$$0 + 4$$$ to distinguish $$$0 + 4$$$ and $$$2 + 2$$$, because $$$0 + 4$$$ will be changed to $$$0 + 0$$$ or $$$4 + 4$$$, while $$$2 + 2$$$ will remain $$$2 + 2$$$.
Then we are going to deal with the $$$2$$$'s. There are two possible positions for an $$$2$$$ in four bits: adjacent or opposite. I'll denote them $$$2a$$$ and $$$2o$$$ separately. Our next target is to change any $$$2$$$ to $$$2o$$$.
Notice that for $$$0$$$, $$$2a$$$, $$$2o$$$, $$$4$$$, an operation $$$2o$$$ will make them $$$2o$$$, $$$2a$$$, ($$$0$$$ or $$$4$$$), $$$2o$$$ respectively, and an operation $$$2a$$$ will make then $$$2a$$$, ($$$0$$$, $$$2o$$$, $$$4$$$), $$$2a$$$, $$$2a$$$ respectively.
For $$$N = 2, 4, 6$$$, we are now having $$$2 + 0$$$, $$$2 + 2$$$ and $$$2 + 4$$$ separately.
If $$$N = 4$$$, the cases are $$$2a + 2a$$$, $$$2a + 2o$$$ and $$$2o + 2o$$$. Sending a $$$2o + 2o$$$ (like $$$11001100$$$) results in $$$2a + 2a$$$, $$$2a + 0$$$, $$$2a + 4$$$, $$$0 + 0$$$, $$$0 + 4$$$ and $$$4 + 4$$$. If the result is $$$N = 2, 6$$$, send a $$$0 + 2a$$$ to make it $$$0 + 0$$$, $$$0 + 4$$$, $$$4 + 4$$$, $$$2o + 0$$$, $$$2o + 4$$$ or $$$2a + 2a$$$.
If $$$N = 2, 6$$$, the cases are $$$2a + 0$$$, $$$2o + 0$$$, $$$2a + 4$$$ and $$$2o + 4$$$. Sending $$$2o + 2o$$$ results in $$$2o + 2a$$$, $$$2o + 0$$$ or $$$2o + 4$$$. For now $$$N = 4$$$, it must be $$$2o + 2a$$$, so send another $$$0 + 2a$$$ and we will have $$$2a + 2a$$$, $$$2o + 0$$$ or $$$2o + 4$$$.
After the above operations, if now $$$N = 4$$$, send a $$$0 + 4$$$ to eliminate $$$0 + 4$$$, so if still $$$N = 4$$$ then it remains $$$2a + 2a$$$, send $$$2a + 2a$$$ to make it $$$0 + 0$$$, $$$0 + 4$$$, $$$4 + 4$$$, $$$2o + 0$$$, $$$2o + 4$$$ or $$$2o + 2o$$$. Similarly if now $$$N = 4$$$ send a $$$0 + 4$$$ to remove $$$0 + 4$$$.
Now for $$$N = 2, 4, 6$$$, we only have $$$2o + 0$$$, $$$2o + 2o$$$ and $$$2o + 4$$$. If $$$N = 2, 6$$$, send a $$$0 + 2o$$$ to make them $$$0 + 0$$$, $$$0 + 4$$$, $$$4 + 4$$$ or $$$2o + 2o$$$.
After sending another $$$0 + 4$$$ to eliminate $$$0 + 4$$$, finally for $$$N \neq 0, 8$$$ we only have $$$2o + 2o$$$ to deal with. A $$$2o + 2o$$$ makes it $$$0 + 0$$$, $$$0 + 4$$$ or $$$4 + 4$$$. Then $$$0 + 4$$$ to make the last $$$N = 4$$$ results to $$$0 + 0$$$ and $$$4 + 4$$$.
In the end, if we got $$$N = 8$$$ in previous operations, send a $$$4 + 4$$$. This makes all the cases to $$$N = 0$$$.
This process will cost at most $$$16$$$ operations.
Your solution is probably the same as the 2^8-1 operation solution with optimization. Many of the operations in the 2^8-1 solutions can be skipped if you know the number of 1s in the record.
Wow the living problem author! Thank you for your painful problem! :(
I think enabling skipping operations may lead to a completely different solution, because the results of operations are cumulative. It is difficult to say whether skipping some operations can still enumerate all potential target states. Moreover this may break the induction hypothesis. I'd rather consider this strategy as a heuristic modification of the first "state search + pruning" solution.
Well, when there is a complete $$$(2^8-1)$$$-operation sequence, it is easy to guess any simpler strategy is trying to form a subsequence of the $$$(2^8-1)$$$-operation sequence. I'm interested in whether there is any better way to achieve or explain this strategy, but now it mostly seems like some special case work.
You are right. It is very hard to tell which operations can be skipped without breaking the induction hypothesis.
What I originally meant is, the instructions your solution would output, is likely a sub-sequence of the (2^8-1)-operation sequence (with rotation), with the same intention to force the record to some known good state.
For example, in the (2^8-1)-operation sequence, there is one instruction with odd number of 1s in it. i.e. 10000000
This is same as your first instruction if you know the number of 1s in the record is odd initially. And the purpose of this instruction is force the number of 1s to be even. You can tell the instructions before and after this instruction is completely the same.
This way, you can remove half of the (2^8-1)-operation sequence.
It's a good point. I checked the operation sequence and find the $$$128$$$-th term is $$$10000000$$$. Checking the number of set bits in advance can indeed save half operations.
Then I guess if there are good operations at $$$64$$$-th and $$$128$$$-th, and I find $$$11000000$$$. As in my solution, this operation is used to make even set bits in odd and even bits, and I use it when there are both odd set bits in odd and even bits. This information may not be deduced by just the total number of 1's.
So now it looks like an enumeration strategy: if before $$$11000000$$$ there are even set bits in odd and even bits, then after it there are odd set bits, and vice versa.
In my solution I spend a $$$10101010$$$ and tell if it needs $$$11000000$$$ from the result. So it may be like my solution use extra instructions and tell from the total number of bits whether we need to use the "core" instruction to toggle the difference between some sets of bits.
If for any $$$(2^k-1)$$$-operation sequence the middle operation is a core operation, then my solution is indeed follow the above strategy: it successively checks if the instructions $$$10000000$$$, $$$11000000$$$, $$$10100000$$$, $$$11110000$$$, $$$10001000$$$, $$$11001100$$$, $$$10101010$$$ and $$$11111111$$$ should be applied. If this is true, then my solution looks like a binary search strategy, comparing to the $$$(2^8-1)$$$-operation complete search strategy.
Then a few more questions:
I also had a sad story on this problem :)
My BFS-like solution (basically what is described in the problem analysis) uses $$$13$$$ operations.
Most states end up being redundant, they can be handled in the same way as some other state that contains them. Removing these redundant states and printing the distances, I get this nice little chart. With some work maybe this could even be turned into a human-understandable algorithm...
The states furthest from the zero state are $$$12$$$ operations away, plus $$$1$$$ more operation to get the initial value of $$$n$$$ gives $$$13$$$ operations.
I was able to solve 2 questions A and B but still got a rank of 4k
Finished debugging full solution to C one minute after contest ended, which meant a rank below top 2500 instead of one in top 150...Guess I just have bad luck or something.
Agree that the difficulty was quite unbalanced. Other than the (very hard) last subtask of C, all the problems are quite easy. If you can't solve that very last subtask, you have to get everything else AND be fast enough to qualify.
I managed to qualify, but I am very impressed you actually solved C by yourself. It took me more than an hour after reading the official solution to C2 to understand the problem and was convinced only people that had seen it before could solve it.
"But 99.3% isn't so bad, and if we see an unlucky failure with this method, we can easily get another independent try by changing our code's random seed, since we have control over that source of randomness."
the above paragraph is from problem c1 analysis ,can someone explain it ,I can't understand it?