### Lain's blog

By Lain, history, 15 months ago,

The round is starting in around half an hour. Let's discuss the approaches here after it's done.

Good luck!

• +147

 » 15 months ago, # |   +11 Oh it was alright! How it went everybody?
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 It was fun! Half of my team had to drop out or half-participate due to class/sleep, but I really liked the problems! It was nice that uniform random did so well :PWe tried to write our own simulator and iteratively improve it by clearing bottlenecks, but couldn't get it done in time.
 » 15 months ago, # | ← Rev. 2 →   +35 A – An example = 2,002 points B – By the ocean = 4,566,699 points C – Checkmate = 1,299,017 points D – Daily commute = 1,118,984 points E – Etoile = 688,814 points F – Forever jammed = 1,353,181 points ------------------------------------- Total score = 9,028,697 points 
•  » » 15 months ago, # ^ |   +2 A – An example 2,002 points B – By the ocean 4,566,609 points C – Checkmate 1,298,727 points D – Daily commute 1,581,934 points E – Etoile 711,580 points F – Forever jammed 1,232,802 points Total score 9,393,654 points This was my teams score. We also tried one solution which implemented DP but it gave 0 score. Most of these scores were random guesses. This was our first try ,will try harder next time.
•  » » 15 months ago, # ^ |   -20 Can you plese share your approach here
 » 15 months ago, # |   +40 When I heard the topic in the stream, I wasn't very hopeful and motivated. However, the task was actually quite nice.We've got our 15 minutes of glory before ✷code overtook us. Our scores: A – 2002 B – 4568063 C – 1299353 D – 2486628 E – 713945 F – 1388768
•  » » 15 months ago, # ^ |   +102 How did you get such a high score in D?
•  » » » 15 months ago, # ^ |   +47 We had a dedicated strategy for D. Ignore the streets that noone traverses. First, set the period of each traffic light to be equal to the number of incoming streets. Each traffic light will be green for exactly 1 second.Then, we simulate the whole process. Whenever there is a car for which the traffic light isn't scheduled, use the earliest possible time for it. This gives around 2478000, the last 8000 come from shuffling the cars.
•  » » » » 15 months ago, # ^ |   -7 Could you please help me understand your solution further? From what I understand, initially you set the green-light time as 1 for each edge that is used in some path by a car. Then you simulate the process, but I did not understand what you mean by "Whenever there is a car for which the traffic light isn't scheduled, use the earliest possible time for it." Do you mean that you change the green-light time for some edge if there is a car waiting on it? If so, then to what value?
•  » » » » » 15 months ago, # ^ |   +47 For each intersection you do the following: You have a set of N incoming useful streets. You want the traffic lights for this intersection to have a period exactly N, with each street having the green light for 1 second. What remains is to determine which street will get which offset modulo N. When you start the simulation, this hasn't been determined yet — imagine that you only turn on and set each traffic light when you actually need it for the first time.For example, suppose you have an intersection with N = 5. If the first car reaches it at time 42, you will say that its street will have green light at timestamps of the form 5k+2, so this car can now cross without waiting. If the next car comes at 47 using a different street, the car would also want the offset 2 but that one is already taken, so you set this street to be green at 5k+3. The car will wait for one second and then cross.
•  » » » » » » 15 months ago, # ^ |   0 Thank you! I was able to increase our score on D by 550k (from 1.6M to 2.1M) because of this!
•  » » » » » » 15 months ago, # ^ |   0 This is a good solution.
•  » » 15 months ago, # ^ |   +30 majk majak krra D m?
•  » » » 15 months ago, # ^ |   0 lol
•  » » 15 months ago, # ^ |   +41 Your total score = 10458759
 » 15 months ago, # |   +1 Team: lolok123 geckods Lain adivasiA: 2002 pointsB: 4,567,081 pointsC: 1,299,458 pointsD: 1,572,420 pointsE: 710,736 pointsF: 1,410,594 pointsTotal score: 9,572,291 pointsWe just did a bunch of greedies. Unfortunately we couldn't find any patterns in the test cases.
 » 15 months ago, # | ← Rev. 2 →   +2 Our Score:A : 2,002B: 4,566,609C: 1,298,727D: 1,581,934E: 711,580F: 1,232,802Total : 9,393,654
 » 15 months ago, # | ← Rev. 3 →   +4 hot guys from clubhouse A: 2,000 points B: 4,567,648 points C: 1,305,195 points D: 1,720,427 points E: 757,968 points F: 1,429,850 points Total: 9,783,088 points But our local optimizations gave us another +19k on d now (5 minutes after)
•  » » 15 months ago, # ^ |   0 By local optimizations do you mean you took the answer you got from your solutions and further optimized it? I would be curious what kind of local optimizations can be done at the end since I couldn't think of anything meaningful as the scoring function is quite chaotic (i.e. small perturbations totally change how the cars move and congest).
•  » » » 15 months ago, # ^ |   +8 Two optimizations: Increase random showtime by $\pm1$. Repeat while it makes the score better. Random shuffle the order for a random traffic light. It's sad that we haven't come up with a good strategy in D (because we weren't set up to think) and that we haven't started simulating these particular optimizations earlier (which is actually not so important since we missed 700k in d anyway)
•  » » » » 15 months ago, # ^ |   +9 Do these optimizations really help at all? That's surprising, cause I did both of these and got negligible (2kish) improvements. Did you do the first with a simulated anneal type function or just when it improves?
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   +10 No annealing, just do it if improves, don't it otherwise. Maybe the key is that we obtained initial answers using some different strategies and they were well-optimizable
 » 15 months ago, # | ← Rev. 2 →   +8 A – An example = 2,002 pointsB – By the ocean = 4,566,672 pointsC – Checkmate = 1,300,867 pointsD – Daily commute = 1,587,681 pointsE – Etoile = 706,461 pointsF – Forever jammed = 1,418,790 pointsTotal score = 9,582,473 points
•  » » 15 months ago, # ^ |   0 Your teammate have 0 line of code contribution
 » 15 months ago, # | ← Rev. 2 →   +3 A – An example = 2,002 points B – By the ocean = 4,566,685 points C – Checkmate = 1,299,725 points D – Daily commute = 1,596,794 points E – Etoile = 711,693 points F – Forever jammed = 1,378,993 points ------------------------------------- Total score = 9,555,892 points 
 » 15 months ago, # |   0 A – An example = 2,000 points B – By the ocean = 4,565,642 points C – Checkmate = 1,231,878 points D – Daily commute = 971,397 points E – Etoile = 661,797 points F – Forever jammed = 455,765 points ------------------------------------- Total score = 7,888,479 points 
 » 15 months ago, # | ← Rev. 3 →   +3 A – An example = 2,002 points B – By the ocean = 4,566,688 points C – Checkmate = 1,299,288 points D – Daily commute = 1,572,159 points E – Etoile = 706,947 points F – Forever jammed = 1,410,063 points ------------------------------------- Total score = 9,557,147 points 
 » 15 months ago, # |   +3 A – An example = 2,000 points B – By the ocean = 4,566,260 points C – Checkmate = 1,298,822 points D – Daily commute = 1,504,327 points E – Etoile = 705,982 points F – Forever jammed = 1,271,902 points ------------------------------------- Total score = 9,349,293 points 
 » 15 months ago, # |   +43 Score: A – 2,002 points B – 4,566,845 points C – 1,299,387 points D – 1,586,296 points E – 715,548 points F – 1,409,417 points Total score 9,579,495 points
•  » » 15 months ago, # ^ |   +23 insane, Shahraaz you are soo orz!
 » 15 months ago, # |   0 Our team's score A – An example = 2,002 points B – By the ocean = 4,566,550 points C – Checkmate = 1,299,345 points D – Daily commute = 1,593,444 points E – Etoile = 684,900 points F – Forever jammed = 1,319,603 points_____________________________________Total score = 9,465,844 points
 » 15 months ago, # | ← Rev. 2 →   +138 team Warsaw Huskies: Errichto, kabuszki, Marcin_smu, Swistakk. A – An example = 2,002 points B – By the ocean = 4,568,556 points C – Checkmate = 1,305,908 points D – Daily commute = 2,498,918 points E – Etoile = 748,779 points F – Forever jammed = 1,448,253 points ------------------------------------- Total score = 10,572,416 points In D, first find all roads that are ever useful. Assume that each of them should be on for exactly 1 second. This gives you cycle size for each intersection and we are yet to fix the order of roads going in. Then simulate everything (from time 0 to D) and always do this: if a car is waiting at some intersection and this remainder modulo cycleSize isn't assigned yet, assign it now (which lets this car pass now).
•  » » 15 months ago, # ^ |   +17 Within ~15 minutes after the contest I improved F to 1462172 (by ~14k), looks significant.Turned out to be almost exactly the difference between us and 1st place xd
•  » » 15 months ago, # ^ |   +16 We have similar scores to you but D is about .9M instead :PI'm curious as to how your team discovered that D could be improved significantly and decided to focus on it, and also why you decided on the algorithm you eventually ended up with. To me it is quite surprising that what you described would help improve the score by much, let alone more than double it.
•  » » » 15 months ago, # ^ |   +35 how your team discovered that D could be improved significantly For every test, it's quite easy to calculate the theoretical score upper bound (if no car ever waits for lights). We were 200-300k short in E & F, but more than 2kk in D. The leaderboard confirmed that it's indeed possible to improve the score by around 1 million so we knew that D is crucial. Also, we actually worked in parallel on D/E/F. why you decided on the algorithm you eventually ended up with It's about trying various ideas, and sometimes analyzing tests to see that something makes sense.
•  » » » » 15 months ago, # ^ |   -8 Hey, thanks for sharing your approach for D. what was your approach for other dataset?
•  » » » 15 months ago, # ^ |   +21 By inspecting tests a little you see that in D you have many big degree vertices where each road is used really small number of times (usually 1, not more than 5 almost ever) and that your current score is far away from the hypothetical upper bound and it is not because you complete small number of cars — it is just because they wait a lot. Why do you wait on intersections like this? It's not about balancing capacities, it's about arriving there when it's just your turn on the cycle — that's why the order here was so important.
•  » » 15 months ago, # ^ |   0 Congratulations! Funny fact that if we had got the same of your score in D, we’d be the 12th worldwide :V
•  » » 15 months ago, # ^ |   0 Can you upload your stream for this year's hashcode with commnetary or do a livestream on the extended round going on? It would we great help for everyone!
•  » » 15 months ago, # ^ |   +3 Congrats and thank you loads, Errichto. Your stream on Youtube for the practice problem was super helpful in understanding the approach for optimization problems. It was my first time in hashcode, our team couldn't do well but we got a decent score(8,960,792 points). ^_^
•  » » 15 months ago, # ^ |   0 I watched your videos before the HashCode and I got 9,579,637 points, big thanks to you.
 » 15 months ago, # | ← Rev. 2 →   +17 A – 2,002 B – 4,568,231 C – 1,305,017 D – 2,405,226 E – 708,005 F – 1,294,160 = 10,282,641 points EDIT: 16th, yay :-)
 » 15 months ago, # |   +29 A – 2,002 B – 4,568,673 C – 1,305,761 D – 2,483,087 E – 734,237 F – 1,104,818 pointsTotal score – 10,198,578 points
 » 15 months ago, # | ← Rev. 2 →   +3 We had - A — 2002 - B — 4,566,907 - C — 1,301,039 - D — 1,584,063 - E — 750,602 - F — 1,362,165 - Total Score — 9,566,778Orz kclee2172 for improving our score on E so much, but we ultimately lost out on D and F. We spent way too long correcting the bugs in our checker (which we should have abandoned before 2 hours into the contest, lmao) and realized easy improvements on D and F too late (250k improvement on F in the last 10 minutes, couldn't do it for the rest).
 » 15 months ago, # |   0 our team @Astartes :D A – An example 2,002 pointsB – By the ocean 4,566,575 pointsC – Checkmate 1,300,037 pointsD – Daily commute 1,578,893 pointsE – Etoile 717,493 pointsF – Forever jammed 1,342,436 pointsTotal score 9,507,436 points
 » 15 months ago, # |   0 When will the final scoreboard be available? Also, when will the live stream start?
 » 15 months ago, # |   +2 A: 2,002 points B: 4,566,646 points C: 1,299,518 points D: 1,588,191 points E: 705,392 points F: 1,343,697 pointsTotal: 9,505,446 points
 » 15 months ago, # | ← Rev. 2 →   +6 A – An example 2,000 points B – By the ocean 4,566,918 points C – Checkmate 1,299,800 points D – Daily commute 1,578,942 points E – Etoile 717,052 points F – Forever jammed1 1,459,392 points Total score 9,624,104 points 
 » 15 months ago, # | ← Rev. 2 →   0 A – An example = 1,002 points B – By the ocean = 4,566,610 points C – Checkmate = 1,298,292 points D – Daily commute = 1,529,881 points E – Etoile = 699,374 points F – Forever jammed = 808,948 points ------------------------------------- Total score = 8,904,107 points
•  » » 15 months ago, # ^ |   +15 It was my First Hashcode Competition.
 » 15 months ago, # |   +16 This is our score A – 1,002 points B – 4,566,342 points C – 1,298,282 points D – 1,594,442 points E – 701,224 points F – 1,349,535 points Total - 9,510,827 This is an upper bound we calculated (assuming no waiting time at all intersections). A – 2,002 points B – 4,576,202 points C – 1,328,389 points D – 3,986,591 points E – 921,203 points F – 1,765,068 points Total - 12,579,455 
 » 15 months ago, # |   +8 Team : ShivY08 Nitin_ksh Axay10A – 2,000 pointsB – 4,566,474 pointsC – 1,299,016 pointsD – 1,586,579 pointsE – 704,383 pointsF – 1,448,862 points Total score — 9,607,314 points
 » 15 months ago, # |   +1 A – An example 2,002 pointsB – By the ocean 4,568,675 pointsC – Checkmate 1,313,852 pointsD – Daily commute 2,244,613 pointsE – Etoile 733,035 pointsF – Forever jammed 1,434,909 pointsTotal score 10,297,086 points
 » 15 months ago, # |   +26 Looking at all these ~9.5mil point solutions makes me kinda sad. I did pretty okay, especially for my first time ever. I got kinda discouraged while reading the topic, it took me about 10-15 minutes to understand it.Then it took me nearly an hour to get a working greedy solution (the one that gives a score of 7,885,740).But eventually my solution was to make the times that the lights were on for each road coming in proportional to the amount of cars that came in through each road, and I added a few more things to squeeze some more points out of it. I wanted to make some algorithm to simulate the process so I could try a lot more things, but I didn't get any idea on how to do that. A – An example - 2,002 B – By the ocean - 4,565,969 C – Checkmate - 1,252,726 D – Daily commute - 973,143 E – Etoile - 663,598 F – Forever jammed - 1,237,036 Total - 8,694,474 (If you're wondering why I say 'I' and not 'we', it's because my teammates dropped out on me :/ )
•  » » 15 months ago, # ^ |   +35 I wouldn't be discouraged, effectively having 4 times the time makes all the difference. You should compare yourself against scores people had after 1 hour (when a team of 4 spent 4 total hours). For us -- we had not submitted anything at that point :-)
•  » » » 15 months ago, # ^ |   +13 You should compare yourself against scores people had after 1 hourAh yes, and a team of nine mothers can give birth to a child in one month, right? :)I would say that there is no good && simple way to compare a single person to a four-person team in this competition. Some approaches need some time for thinking and implementation, so even if you had a 100-person team, they still wouldn't have them done one hour into the contest.The best comparison they can make is simply to other single-person teams.
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   +11 Yeah, I agree. I'm still proud of myself for getting ~3000th place in my first ever Hashcode, all by myself!Also, many of the higher-scoring teams have participants who are better, and most likely are on Codeforces, so the top people posted their scores here.Interesting that you put && for and, like a true programmer :P
 » 15 months ago, # |   0 A – An example = 2,002 points B – By the ocean = 4,566,614 points C – Checkmate = 1,300,138 points D – Daily commute = 1,580,783 points E – Etoile = 715,157 points F – Forever jammed = 1,377,233 points Total score = 9,541,927 points
 » 15 months ago, # | ← Rev. 2 →   +8 A- 2000 pointsB- 4565642 pointsC- 1300091 pointsD- 969685 pointsE- 682950 pointsF- 1016710 points --------------------Total- 8537078 points
 » 15 months ago, # |   0 A – An example 2,000 pointsB – By the ocean 4,566,668 pointsC – Checkmate 1,298,808 pointsD – Daily commute 1,581,124 pointsE – Etoile 708,233 pointsF – Forever jammed 1,267,127 pointsTotal score 9,423,960 pointsjust removing all roads thet have no cars and all cars thst take more than d time. then putting 1s for all routes. and somtimes 2 to 5.
 » 15 months ago, # |   +228 me, maroonrk, chokudai, wata A: 2,002 B: 4,569,036 C: 1,310,645 D: 2,487,443 E: 745,455 F: 1,471,554 Overall, 10,586,135
•  » » 15 months ago, # ^ |   +66 Congratulations!
 » 15 months ago, # |   0 A – An example = 2,000 points B – By the ocean = 4,566,679 points C – Checkmate = 1,299,783 points D – Daily commute = 1,596,140 points E – Etoile = 695,539 points F – Forever jammed = 1,073,656 points ------------------------------------- Total score = 9,233,797 points It was quite fun, and time-consuming, considering we spent a lot of time on input/output and trying to write a scorer ourselves ( which we eventually gave up on ). Interesting approaches by everyone, so far as I can see. Our main approach was quite simple, we distributed the periods over streets based on the number of cars that would travel on that street. And additionally, randomly decided the ordering of the schedule per intersection.
•  » » 15 months ago, # ^ |   0 Yeah, I thought for about 15-20 minutes on how a scorer could be built, thought of a possible naive one, but that would've taken about O(10^10), so it was kinda useless. I wonder if anyone actually got a scorer working.
 » 15 months ago, # |   +184 I hope you all enjoyed solving this year's Qualification Round! After many years of competing on HC, now (as Alphabet employee) I proposed this year's problem, and built two datasets: B -- which is based on real streets of Lisbon, and D -- which is a challenging-to-navigate network from the Barabási-Albert distribution. Unleashing random walks on such a graph forces many paths to go through a small amount of hub nodes, causing more challenging scheduling scenarios. It's been great to read about all the heuristics you've come up with!
•  » » 15 months ago, # ^ |   +49 Would it be possible for the google hashcode team to create a submit button which automatically takes all the files or the specified ones on a single click on the submit button. It was extremely painful to do each file submission manually(along with source code). Or at least someway through which we can submit all files in one go. Our hands become tired pretty quickly clicking again and again on the mouse(since we doing a lot of trial and error)!Some suggestions from the community on how do they deal with this issue are welcome on this!
 » 15 months ago, # |   +8 I know people have used constraint solvers in the past for hashcode -- did anyone do that this time?
 » 15 months ago, # | ← Rev. 2 →   0 Team: Losers! bansal_naman Gautam A – An example = 2,002 points B – By the ocean = 4,560,692 points C – Checkmate = 1,225,279 points D – Daily commute = 0 points E – Etoile = 666,538 points F – Forever jammed = 765,534 points -------------------------------------- Total score = 7,220,045 points It was our first HashCode. We couldn't score on D, ran out of time while trying to improve on our greedy approach. We had a lot of fun though.
 » 15 months ago, # |   0 Our very first participating in HashCode, team We hate Gabi: Ahmad-Magdy, maghrabyJr_ and me. A – An example = 2,002 points B – By the ocean = 4,566,682 points C – Checkmate = 1,300,924 points D – Daily commute = 1,572,848 points E – Etoile = 680,987 points F – Forever jammed = 1,380,767 points ------------------------------------- Total score = 9,504,210 points D was a real challenge, yet we enjoyed the contest. Looking forward to participating next year with better results insha’Allah.
 » 15 months ago, # |   +21 Rethinkers — Radewoosh, znirzej, shadowatyy, xman1024 A – An example = 2,002 points B – By the ocean = 4,570,013 points C – Checkmate = 1,310,185 points D – Daily commute = 1,775,764 points E – Etoile = 769,115 points F – Forever jammed = 1,415,565 points ------------------------------------- Total score = 9,842,644 points 
 » 15 months ago, # |   -11 A – An example = 2,000 points B – By the ocean = 4,565,642 points C – Checkmate = 1,231,878 points D – Daily commute = 969,685 points E – Etoile = 661,797 points F – Forever jammed = 455,737 points ------------------------------------- Total score = 7,886,739 points 
 » 15 months ago, # |   -24 1st in our hub Motilal Ke coders(MNNIT) //thats also ranked 31 out of 490 total worldwide 142 in India ,944 GloballyTeam- is_it_rated A- An example 1,002 points B – By the ocean 4,566,695 points C – Checkmate 1,299,322 points D – Daily commute 1,582,103 points E – Etoile 704,844 points F – Forever jammed 1,346,352 points TOTAL----- 9,500,318 points It was a fantastic experience waking up till 4am and improvising the PS....thanks Hashcode
 » 15 months ago, # |   0 How to implement the simulation for calculating our score ? I thought of few AI algorithms but to move on better state it is required to calculate the score of current and new state.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +12 Here's a simple version of what I wrote during the contest: simulatorMain ideas: for each street maintain a queue of cars waiting at its end have one global data structure for future events (I use a set), and whenever a car passes through an intersection, add an event for the time when it should next reach an end of a street for each second of the simulation, first process the events that happen (enqueue or score each car that just traversed a street) and then for each nonempty street check whether its light is green and if yes, send the first car Of course, if you want to run some local optimizations on top of this (which is what we also did), you want to wrap the simulation code into a function and make sure you are correctly initializing everything each time you call it.
 » 15 months ago, # | ← Rev. 9 →   +12 A – An example: 2,002 points B – By the ocean: 4,568,086 points C – Checkmate: 1,304,774 points D – Daily commute: 2,396,389 points E – Etoile: 710,811 points F – Forever jammed: 811,954 points Total 9,794,016 points (40th)We fixed the duration of all signals to 1 second and tried to find optimal order of streets by simulation — which was good for D, but not for F.4 hours were too short to implement two different strategies for us. Congraturations for everyone, and I hope num_of_finalists >= 40.
•  » » 15 months ago, # ^ |   0 Hey, how did you find the optimal approach? Can you elaborate...I mean all I did was iterate over intersections at put 1s for all streets. And then optimised for only streets with cars and then optimised by deleting cars that take long time than duration of whole simulation. Can you explain your approach? I'm curious...I never ran a loop from 0 to Duration seconds lol
•  » » » 15 months ago, # ^ | ← Rev. 3 →   0 Note that our algorithm for D fixes all durations of all signals to 1 second. If the cars are similariy distributed into various incoming streets, this strategy works great because the average waiting time of cars is minimized.Let's suppose there are four cars(c1, c2, c3, c4) and four streets(s1, s2, s3, s4). The cars will arrive to an (same) intersection.From the point of view of the intersection, c1 arrives at 0 second by s1. c2 arrives at 2 second by s2. c3 arrives at 4 second by s3. c4 arrives at 7 second by s4. We used priority queue for sorting the "arrival actions" by arrival time. We will make a "schedule" for each intersections like this way. Let schedule[i] = the name of street signal turned on at i, 4+i, 8+i, ... seconds. (Why 4? because the number of incoming streets is four for this intersection) [1] (c1, 0sec, s1): schedule[0] = s1. [2] (c2, 2sec, s2): schedule[2] = s2. [3] (c3, 4sec, s3): schedule[4%4 = 0] = ..? This is collision. Like open addressing method (used to solve hash collision), we will allocate s3 to schedule[1]. so schedule[1] = s3. [4] (c4, 7sec, s4): schedule[8%4 = 0] = ..? collision! scheudle[3] = s4. Note that the open addressing method will always success because length_of_schedule == num_of_incoming_streets.So, the schedule for this intersection will be s1 (1 sec) s3 (1 sec) s2 (1 sec) s4 (1 sec) We ran this algorithm for all intersections by simulating all actions.This is not exactly optimal, but will be good strategy for datasets B, C, D, E. However, for dataset F, this solution will fail because cars are "jammed" in F. To solve F, we should give longer signal duration for jammed streets.
•  » » 15 months ago, # ^ |   0 Can you throw some light on how exactly did you find "the optimal order of streets by simulation". We found it pretty difficult to convert the data into output format even though we could store the streets that were used by the cars during a particular second(in some array from 1 to D seconds). But no idea after that.
•  » » » 15 months ago, # ^ |   0 Please see the comment I wrote above (http://codeforces.com/blog/entry/88188?#comment-766186) :)
•  » » » » 15 months ago, # ^ |   +1 Thanks! I will look into it and get back to you!
 » 15 months ago, # | ← Rev. 4 →   +16 1. A – An example 2,002 points 2. B – By the ocean 4,566,742 points 3. C – Checkmate 1,298,536 points 4. D – Daily commute 1,579,275 points 5. E – Etoile 714,983 points 6. F – Forever jammed 1,406,448 points ===> Total score 9,567,986 points Our team The_Lord_Himself, VP19. We picked greedily based on the frequency of cars and special thanks to Errichto because of his warm-up stream for practice problem we learned a lot about hash code :)
 » 15 months ago, # |   0 A – An example = 2,002 points B – By the ocean = 4,566,807 points C – Checkmate = 1,299,201 points D – Daily commute = 1,568,896 points E – Etoile = 681,852 points F – Forever jammed = 1,441,316 points ------------------------------------- Total score = 9,560,074 points India $#49$, World $#344$.
 » 15 months ago, # |   +8 Ended up with 9.5 million (Rank: 879) Some Mistake that we made1) Not making a local simulator to get the exact score. (THE BIGGEST MISTAKE in any optimization Contest)2) Not trying out randomization.3) Not making submissions on time.... we increased our score from 9.2 million to 9.5 million in the last 2 minutes when we realised that we forgot to submit one of the output files (:4) Not analysing the test cases well.5) Writing the same code for all the input files.6) Not thinking... Just doing any random thing that came to mind.
 » 15 months ago, # |   0 Excuse me guys, I tried to solve the problem but I did not came up with nothing and I will like to solve it and learn about this topic, What should I study? What should I look for?
 » 15 months ago, # | ← Rev. 3 →   0   1. A – An example = 1,002 points 2. B – By the ocean = 4,566,384 points 3. C – Checkmate = 1,298,723 points 4. D – Daily commute = 969,685 points 5. E – Etoile = 680,987 points 6. F – Forever jammed = 806,897 points---------------------------------------- Total Score = 8,323,678 points   We ranked 3458 Globally and 949 in India :-) Our code was little slow as it had a lot of iterations over intersections so we were unable to score good in D dataset. But it was our first ever hashcode so we learned many things and willing to improve in next time.
 » 15 months ago, # | ← Rev. 2 →   0 A – An example 2,002 points B – By the ocean 4,566,925 points C – Checkmate 1,300,773 points D – Daily commute 1,584,872 points E – Etoile 706,270 points F – Forever jammed 1,418,795 points Total score 9,579,637 points Egypt #3, World #204.
 » 15 months ago, # |   0 What is the optimal approach for case F ? ( I got only 808k points in F) I removed all the useless streets(0 occurence) and useless vehicles(time taken greater than simulation time), and then sorted the incoming streets at each intersection in descending order of their total no. of occurrences in the whole simulation. Finally, each incoming street will be given a green light for 1 second.
•  » » 15 months ago, # ^ |   0 Give the most used streets more than 1 second.
•  » » 15 months ago, # ^ |   +8 Keep a count of the cars on each street and allocate a time = count()/40. The number 40 isn't specific. Just experimental. You might try dividing by 10,20,... etc and see how do the results vary.
 » 15 months ago, # |   +62 Score Distribution this year
•  » » 15 months ago, # ^ |   0 Where did you get the data from?
 » 15 months ago, # |   0 Did anyone notice the earliest car Insight? And can explain me what it means.I thought the meaning was, the first car to reach its destination, and the time it took that car. But, in a few inputs that was not the case. Does anyone know what the meaning is and can explain me?P.S I competed with team YarpoPo and finished 8 in Israel with 9,538,401 points
 » 14 months ago, # | ← Rev. 2 →   +36 I did a write-up of all the bugs and mistakes (and also some good ideas) we made during the contest:https://curiouscoding.nl/hashcode-2021/
 » 14 months ago, # |   0 I have a question for everyone who simulated the driving process: Did your calculation match the Judge System one? There are several car routes in set C, with the total path length of only 2, and the second street having the length of 1. For example: 2 fihe-fiaa fiaa-fghi.So with the traffic lights set to green for the first street at the beginning of the simulation, such cars can reach the destination after just 1 second.However, the Judge System shows me that the earliest car arrives after 6 seconds.
•  » » 14 months ago, # ^ |   0 Are those cars in front of the line? They might be queueing behind other cars on the same street.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 Sorry, I forgot to mention it. The first streets in such paths are only used once by these cars, and no other cars ever pass or start on them.For example: We have a car with the path "2 bejd-bejc bejc-bfii" (it is car number 147, counting from 0 in the car list in set C).So the car is standing at the street "bejd-bejc", which goes into intersection 1492. There are no other cars ever starting or passing through this street.The second street "bejc-bfii" has a length of 1, so the car has only total distance 1 to drive.Then I simulate the process and set the schedule for this intersection to be: 1492 2 bejd-bejc 1 beca-bejc 1 So at time 0 there is a green light at the street "bejd-bejc" and the car can start driving immediately, and after 1 second the car is reaching the end and should score 100 bonus points + 1640 totaltime — 1 second = 1739 points.There are at least two other similar cases in dataset C but the Judge System insight shows the earliest car comes to the destination at 6 seconds.
•  » » » » 14 months ago, # ^ |   0 Maybe you can try to see what happens if you submit a solution with only that one intersection?
•  » » » » » 14 months ago, # ^ |   0 So with just this one intersection in schedule the first car arrives after 1 second as expected. But I don't know why it can differ from the full schedule, because as written in the task description "the submission file must describe the intersection schedules, in any order".
•  » » » » 14 months ago, # ^ |   0 @coconut_ This is what I tried to say in my post before. I had the same problem in C. In my simulation I had a car that arrived after one second, but the insight said the earliest car was after 6 seconds. I looked at the visualization part, And there I could see that there is a car that finished after 1 second.I took 3 pictures of the visualization section on time 0, 1, 2. Where it is easy to see, that there is a car that finishes after 1 second.I would show the pictures here, but I dont know how to upload pictures into this forum.
•  » » » » » 14 months ago, # ^ |   0 I yesterday wrote an email about that to Hashcode, trying to ask if there is maybe a bug in how the earliest car insight is shown, but got a reply that they don't have the bandwidth to help with individual submissions.
•  » » » » » » 14 months ago, # ^ |   0 I wrote to google team too :) And got a similar response.
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 I will also add, that I have a working simulator and my score point is equal to the judge system ones. the problem seems to be only on the earliest car part. You can see the pictures here: if the pictures doesn't work try this: https://ibb.co/KrLC6Kh https://ibb.co/25FJY5D https://ibb.co/tHFRG1v https://ibb.co/yf2z41hIf for some reason the picture still doesn't work, PMme and I will send you the pictures.
•  » » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 Sounds like it's a bug just for reporting this earliest arrival time — the score function must be correct or people would have noticed.Maybe don't put your email in public like this btw. PM is better for these things.
•  » » » » » » » 14 months ago, # ^ |   0 According to screenshots it does look like a car should finish at second 1. So it is probably indeed a bug for reporting the earliest time.
 » 14 months ago, # |   +1 Do anybody know how many teams are selected for Final round?My Score: 9200000My rank: 2kverdict: not selected.
•  » » 14 months ago, # ^ |   +23 Where can you see if you were selected or not? Results link on hashcode website seems to be broken
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +1 Well, they said those who are selected will be notified by 2nd March, and I haven't. Can I ask what was your rank?
•  » » » » 14 months ago, # ^ |   0 25th. Apparently, they are still not finalized results, according to answer to my email
•  » » » » » 14 months ago, # ^ |   0 Oh! thanks for clarification. Do you have any idea many teams generally get selected in qualification round? And yeah, if you don't know code jam registration has been started.
•  » » » » » » 14 months ago, # ^ |   +3 According to the rules: The Jury will select between thirty (30) and fifty (50) of the highest--scoring Teams, constituting no more than one hundred fifty (150) finalists, to advance to the virtual World Finals.
•  » » » » » » » 14 months ago, # ^ |   0 Ok. Wish you good luck!
 » 14 months ago, # |   0 Team memebers Ahmadsm2005, ahmedfouadnew, Blobo2_Blobo2
 » 14 months ago, # | ← Rev. 7 →   +13 Team UVIGO Bruteforcers (in Extended Round): A – An example = 2,002 points B – By the ocean = 4,570,431 points C – Checkmate = 1,315,077 points D – Daily commute = 2,601,362 points E – Etoile = 768,066 points F – Forever jammed = 1,472,822 points ------------------------------------- Total score = 10,729,760 points We did poorly during the round itself, so we worked hard afterwards: We ranked 2nd on the scoreboard of the Extended Round.
•  » » 14 months ago, # ^ | ← Rev. 3 →   +10 Amazing job guys, congratulations for 2nd place and showing the potential in dataset D!We got 5th on the extended round and our downfall pretty much was dataset D, we couldn't figure it out. What was your approach there?A – An example 2,002 pointsB – By the ocean 4,569,814 pointsC – Checkmate 1,315,372 pointsD – Daily commute 2,495,884 pointsE – Etoile 779,279 pointsF – Forever jammed 1,478,004 pointsTotal score 10,640,355 points
•  » » » 14 months ago, # ^ |   +10 Thanks and congrats also on you 5th place!Our approach for D was nothing different to the approaches described in this blog. In detail: 1. The greedy previously described in this blog (remove unused streets, fix semaphore durations to 1 and run the simulation to assigning green lights to streets with waiting cars). This scores about 2.49 million. 2. Starting from that assignment, run a simple local search (hill climbing swapping two semaphores if the result does not decrease the score) for as long as we could. Indeed, the result in D is still improving right now.
•  » » » » 14 months ago, # ^ |   0 Hello, are you participating in Reply Code Challenges, how do you take large input and generate output for given inputs.For my code in Dev-C++ compiler it generates output for input files 1,2,3,4 but not for 5,6,My code is correct but still output is not generating any idea. I am struggling with large input data. I just want to know why Dev-C++ is not generating output for large input.
•  » » » » » 14 months ago, # ^ |   0 You can't ask questions for a running contest.
•  » » » » » » 14 months ago, # ^ |   0 I am not asking the logic or code, I am just asking why does compiler does not produce output for large input files (5000 Kb) if it produces for small input files upto 1000 Kb. Is it problem with compiler or code, I also tried to use jdoodle.