Hi all!
Since nobody has posted about the round yet, I thought I'd open up a page to discuss GCJ Round 1A, which happened earlier this evening.
The scoreboard, problems, and editorials are available at this link. Practice mode should be open now--I'd recommend trying the problems if you didn't compete, since I thought they were generally pretty nice.
It looks like everyone with a score greater than 63 or with a score of 63 and a penalty time no greater than 2:14:05 qualifies for Round 2, assuming that nobody gets removed from the scoreboard later on. Everyone else can attempt to qualify through Rounds 1B and 1C, even if they participated in this contest but failed to qualify.
If nobody posts solutions here within the nearish future, I'll write up and share mine, but as far as I can tell, my ideas were pretty much identical to the ones explained in the official editorials.
Regretting for not getting selected within top 1500 . I solved first one fully and 2nd one for 2 test cases. My approach for 1st was fairly simple.
what was your approach?
Step 1:- Select the prefix of all strings just before first *
Step 2:- Select the suffix of all strings after last * an d store both these values in 2 new vectors
Step 3:- Ok and store the string leaving prefix and suffix in the main part known as stem Cool…
Step:- 4Now one thing only you need to check is that among the selected prefixes select the maximum length prefix and maximum length suffix answer it yourself why?
Step:- 5Then after selecting maximum length prefix then match it with all other prefixes if all prefixes are a prefix of this selected string then Ok otherwise there doesn’t exist any word satisfying above strings
Step 6:- And after maximum suffix check that all other suffixes are a part of the suffix of this string
cool…
Step 7:- And than after that for the main part(leaving prefix and suffix of any string ) append main part of all the strings after the maximum length prefix in the answer(ans string) and after appending maximum length prefix append all main parts and after that append maximum length suffix
Step 8:- And output the answer string By substituting each * with any letter between A to Z as * can be anything so I assumed it common for all the strings
Hope it makes it clear Submit and get the AC.
nice approach
Am I the only one that misread problem C statement as if dancer X get removed if there is any compass dancer that has higher number than dancer X's power? I realized that I solved the wrong problem after testing the 4th sample and after a 30 minutes implementation and felt really bad the moment I realized it.
Here's the substance of my code for each of the problems:
Task A
Task B
Task C
All of these felt reasonably concise to me, but the ideas, of course, may be somewhat difficult to interpret from the code alone. If people still have questions about the problems after taking a look through these and the editorials, I can write up my solution ideas at some point later on.
you have used highly efficient way of accessing simple data structures. it would be great if you can explain it to us.
Which parts of the code are you referring to, exactly?
please explain how you solved b and c
you have used highly efficient way of accessing simple data structures.
B doesn't even use data structures (unless u count array) and C just uses std set lmao.
For both problems he is doing same as official editorial except C editorial uses array to store next for each element instead of binary search set.
can you provide link to the official editorial?
It is on the same page as the problems -_-...
Just go on the problem and click the analysis tab.
Okay thanks
I think this was a fairly easier 1A compared to previous years (?), with all 3 of the problems being somewhat ad-hoc. In problem 2, the binary expansion observation was cute.
I don't think "implement what you read" really counts as ad-hoc :p
It was more observation based i think.
Really? I don't recall making any observations except the binary thing mentioned above.
Any way to filter rankings ,countrywise??
Google Code Jam Stats
https://clist.by/standings/code-jam-round-1a-16820932/?country=
How to prepare for round 2? Is topcoder good for it?
solve old codejam problems
I just notice At least one character of Pi is an asterisk (*), for all i.
Because that I write unused and messy code for special case..
Hi, can anyone help me explaining why am I getting MLE in this solution for B with final constraint ( N<= 1e+9):
https://ideone.com/N7miy1
Thanks in advance!
Paths of the form $$$1\rightarrow 2\rightarrow 3 \rightarrow ... ->r$$$ won't work for the test case $$$n=10^9$$$ since it has length $$$\sim \sqrt{n} > 500$$$
can you explain why sqrt(n) needs to be <= 500 more specifically?
You are only allowed to output a sequence upto length 500.
In pascal triangle, I found triangle[500][80](500th row, 80th column) is 990716243 so why can't we reach 10^9 assuming that reaching that triangle[500][80] will increase it to 10^9?
I'm not sure if this question was really meant as a reply to me, but anyway 500C80 is wayyy bigger than 1e9.
oh sorry my bad.500c80 is much bigger. I understand that the 1e9 takes 31 bits in total and the sum of first 31 rows will cover 1e9 but no. of cells in first 31 rows is 512 cells so we can't cover 1e9 by covering all the cells in the first 31 rows. But, can't we cover this by traversing downwards intially and taking more and more numbers as we go down and moving downwards will also provide us greater elements to add up to make 1e9.
How can I be sure that moving downwards still won't given me 1e9? can you help me understanding that??
can you answer that?
How to solve First Problem ?
Go from left to right until you find the first * for all strings. Find a string which satisfy all strings from left to right until the first *. Let that be head of the resultant string. Do the same from right to left until you encounter first *. Find such a string which satisfy all the strings. Let that be the tail of the resultant string. You have head and tail, now take the leftover characters except * from left to right in any order after the first * and before the last *, and add them to your resultant string in between the head and tail.
My Accepted Code: https://ideone.com/6Mn8b6
SMH...I did the same thing but was still getting WA :(. Thanks for your reply though !
your handle is so cool.....
zor zor se bol ke sabko scheme bata de
What I did was store all the substrings before the first '*' in pref[n] and all the substrings after the last '*' in suff[n]. Also store all characters between first star and last star(if exists) for all strings in a single string "mid".
sort pref[n] and suff[n] in decreasing order of length . Then check if all strings in pref is a prefix of pref[0] (largest string). Similarily all string in suff should be suffix of suff[0]. A bool variable stores if its true or false.
If its false print '*' and if its true print "pref[0] + mid + suff[0]".
There probably is an easier way to do this, if anyone finds their solution easier, please do share
Is there any way to give past GCJ rounds as a virtual participant?
no, there is no virtual participation. you can submit the problems as many times as you want, but it will not be virtually
you can set a timer on your own and keep track of progress.
Please tell whether my approach was correct or wrong
I splitted a string with m '*' into m+1 parts let each part be p1,p2,.. pm and kept all the parts with same index among all strings into one set [implemented using vector<set > ] now in each set I determined the strings which contain all the rest of strings like and concantanted them like for ["abcd","abc","a","def","d"] in a particular set I selected ["abcd","def"] and added them into answer string. after completing all the indices we will have the answer. I figured out 2 corner cases 1) when index was 0 for that we should have one string which contains rest all strings as prefix and for last index we should have one string which contain rest all strings as suffix. if for these indices the case not happens than answer is not possible.
Please tell me If I am wrong somewhere. I got Runtime error and passed first 2 test sets Thanks and regards
I think the logic is correct because I did it with the similar idea, there might be some implementation issues,
here's my code : Pastebin
Thanks for replying. atleast I was closer.
I totally missed both approaches the editorial mentioned for Pascal Walk, and spent 45 minutes just flailing around. But in the end I actually came up with a different solution that is very efficient (and has a neat twist):
Start with the path going SW, SE, SW, SE, SW, SE, ... until you're just about to exceed N. Now, you can also easily add the numbers to the E, W, E, W of your choices to the path (the ones fitting into the crooks of the diagonal path). You now have a set of "optional" numbers 1, 1, 3, 4, 10, 15, 35, 56, ... (these are a path of knight's moves down Pascal's Triangle). Now you can probably fill in the rest of N by picking the correct set of these optional numbers — ie, you could solve the rest as a knapsack problem. But here's the surprise: the first 2k of these numbers always sums to exactly 1 less than the (2k+1)th number. So these numbers are just close enough for knapsack to work, and furthermore you can just solve it greedily, always choosing the largest value less than the remaining count!
These generated paths end up very short, using fewer than 64 steps for any N <= 10^9 (well below the limit of 500).
Another approach for B which might be interesting.
Let's consider only paths that go south (down) at least once in every two steps. Now for every cell let's denote by $$$a$$$ and $$$b$$$ the minimum and maximum value of a path of this type that end in that cell. The main observation is that for all $$$a$$$ $$$\leq$$$ $$$c$$$ $$$\leq$$$ $$$b$$$ there exists a path (again of this type) with value $$$c$$$ that ends in that cell.
Well then we can simply find these min and max values with DP and then get some random cell with $$$a$$$ $$$\leq$$$ $$$N$$$ $$$\leq$$$ $$$b$$$. Recovering the actual path is also trivial by adding the cells in reverse.
I had a similar approach. I assumed path will be as follows: going through the horizontal row, then going down, then going through the horizontal row in opposite direction and so on. I also allowed each cell to have previous path cell from the left or right, and from the above row.
In this approach each cell represents not a continuous range of values that could be achieved there, but rather a union of several continuous ranges. I maintained these unions for 30 rows of triangle, and checked that they all together cover all numbers from $$$1$$$ to $$$10^9$$$. Then similar style recovering of the answer.
I tried to code Task C. But not able to find where it is wrong... can anyone help with testcase...... https://ideone.com/3qyGdY
Can anyone see why I get TLE on C ? https://ideone.com/3ayUAK
I tried many random cases, non of them failed .. Thanks ..
I'm not sure, but one possible issue is that you didn't set $$$a[i][j]:= 0$$$ when you do the eliminations; another is that you might be adding eliminated cells to "next_look", for instance in $$$[2,1,1,2]$$$, you will add both $$$1$$$s to next_look even though both will be 0 next round. This is fine, but when you iterate through "look" you should make sure that $$$a[i][j]\neq 0$$$ before proceeding.
many thanks for the help ! I got it in the end :)
Just found it. Here is the version with the bug fixed. https://ideone.com/A2Trcw
Basically the part where the next nodes to look at and the update of neighbors must be in two separate loops..
I got MLE error in final test case of problem 2. I used the sum of numbers from 1 to n and then adding 1 for the remaining sum to make it n. Please tell me what is wrong in this approach.
This takes $$$O(\sqrt{N})$$$ operations, which is too many. We can see that the sum of $$$1$$$ through $$$500$$$ is $$$125250$$$, so this approach cannot reach numbers as high as $$$10^9$$$.
Concerning problem B, I've got a rather ad-hoc solution:
Let's define a parameter z for our Pascal walk. That corresponds to the following:
The first z positions are of the form (1, 1), (2, 1), ..., (z, 1)
We move diagonally right (that is, increasing both r and k by 1, as long as we don't overstep n)
If we cannot make an additional move, increase only k (our subsequent diagonal will have smaller values then), and return to step 2.
Smaller values of z correspond to smaller values in the Pascal triangle (and so more suitable for small inputs), and larger values of z — to larger values of our walk. However, this is not a linear dependence, so I check all values of z from 1 to 16 (I'm sure there is a lower limit for the given constraints, but it isn't that important).
There is a small detail — we must check somehow that we haven't overstepped the limit of queries during our algorithm. For example, if the input is large and z = 1, the algorithm will continuously walk along the rightmost diagonal, which might or might not cause RE (out-of-bounds access). When I tested locally, the values outside of the array were large garbage numbers, and so everything was okay. But when run on the GCJ system, I got RE on the hidden test set and so didn't pass on to Round 2 yet :P
(It is also possible to loop backwards, from 16 to 1, that also gets AC).
Code: https://pastebin.com/G0zSvQ4r
Anyone tried Problem 1 using dp pattern matching? After I made the function that return the string that is gets matched with 2 strings, how to find such string that satisfied all the input string?
ok why downvotes? Did i ask something wrong
Hey guys, anyone can help checking my code for Square Dance here? Getting WA for both test set, working fine on Sample and my own random cases.
https://ideone.com/yDdiMS
Is it possible to get the WA test case from the judge in practice mode btw?
I think 32-bit int might not be enough to fit the final answer. Even for the small case the rough upper bound is 100*100*10^6 = 10^10.
Resolved.
interesting that problem C hard was worth 28 points... it seems so straightforward.
How you solved ?
I actually didn't solve it during the contest LOL. partly because I saw that it was worth 28 points and Pascal Walk hard was 21 points, so I thought I would have a better chance thinking about Pascal Walk than C. But I read the solution for C and it's literally just "implement the contest with an efficient way to update neighbors of each dancer per iteration"... honestly I feel like 10 points would be a more accurate value. but I guess it's silly of me to say that when I didn't even solve it. (you can see the editorials on the contest site: https://codingcompetitions.withgoogle.com/codejam/round/000000000019fd74/00000000002b1355 )
My approach for problem 1C Square Dance:
Link to my approach
I am getting TLE on 2nd test set. Someone please help me as I had spent around 3 hrs on this question. Time complexity seems fine to me. If any clarification in my code is needed then please comment.
Thanks in advance!!