The round is starting in around half an hour. Let's discuss the approaches here after it's done.
Good luck!
The round is starting in around half an hour. Let's discuss the approaches here after it's done.
Good luck!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
Oh it was alright! How it went everybody?
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 :P
We tried to write our own simulator and iteratively improve it by clearing bottlenecks, but couldn't get it done in time.
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.
Can you plese share your approach here
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:
How did you get such a high score in D?
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.
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?
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.
Thank you! I was able to increase our score on D by 550k (from 1.6M to 2.1M) because of this!
majk majak krra D m?
lol
Your total score = 10458759
Team: lolok123 geckods Lain adivasi
A: 2002 points
B: 4,567,081 points
C: 1,299,458 points
D: 1,572,420 points
E: 710,736 points
F: 1,410,594 points
Total score: 9,572,291 points
We just did a bunch of greedies. Unfortunately we couldn't find any patterns in the test cases.
Our Score:
A : 2,002
B: 4,566,609
C: 1,298,727
D: 1,581,934
E: 711,580
F: 1,232,802
Total : 9,393,654
hot guys from clubhouse
But our local optimizations gave us another +19k on d now (5 minutes after)
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).
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)
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?
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
A – An example = 2,002 points
B – By the ocean = 4,566,672 points
C – Checkmate = 1,300,867 points
D – Daily commute = 1,587,681 points
E – Etoile = 706,461 points
F – Forever jammed = 1,418,790 points
Total score = 9,582,473 points
Your teammate have 0 line of code contribution
Team: armyalpaca, davi_bart, rocks03, TheScrasse
Team: sharath101 munghatekartik Shahraaz __sharma__
Score:
Total score 9,579,495 points
insane, Shahraaz you are soo orz!
Our team's score
_____________________________________
Total score = 9,465,844 points
team Warsaw Huskies: Errichto, kabuszki, Marcin_smu, Swistakk.
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).
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
We have similar scores to you but D is about .9M instead :P
I'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.
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.
It's about trying various ideas, and sometimes analyzing tests to see that something makes sense.
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.
Congratulations! Funny fact that if we had got the same of your score in D, we’d be the 12th worldwide :V
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). ^_^
I watched your videos before the HashCode and I got 9,579,637 points, big thanks to you.
EDIT: 16th, yay :-)
Total score – 10,198,578 points
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,778
Orz 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).
our team @Astartes :D A – An example 2,002 points
B – By the ocean 4,566,575 points
C – Checkmate 1,300,037 points
D – Daily commute 1,578,893 points
E – Etoile 717,493 points
F – Forever jammed 1,342,436 points
Total score 9,507,436 points
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 points
Total: 9,505,446 points
Harshu2608 manpreet.singh
It was my First Hashcode Competition.
This is our score
This is an upper bound we calculated (assuming no waiting time at all intersections).
Team : ShivY08 Nitin_ksh Axay10
A – 2,000 points
B – 4,566,474 points
C – 1,299,016 points
D – 1,586,579 points
E – 704,383 points
F – 1,448,862 points
Total score — 9,607,314 points
A – An example 2,002 points
B – By the ocean 4,568,675 points
C – Checkmate 1,313,852 points
D – Daily commute 2,244,613 points
E – Etoile 733,035 points
F – Forever jammed 1,434,909 points
Total score 10,297,086 points
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.
(If you're wondering why I say 'I' and not 'we', it's because my teammates dropped out on me :/ )
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 :-)
You should compare yourself against scores people had after 1 hour
Ah 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.
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
&&forand, like a true programmer :PTeam: Pankaj_Kumar1 quantumbinary typewriter999 Sorrow_boy
A- 2000 points
B- 4565642 points
C- 1300091 points
D- 969685 points
E- 682950 points
F- 1016710 points
--------------------
Total- 8537078 points
A – An example 2,000 points
B – By the ocean 4,566,668 points
C – Checkmate 1,298,808 points
D – Daily commute 1,581,124 points
E – Etoile 708,233 points
F – Forever jammed 1,267,127 points
Total score 9,423,960 points
just 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.
me, maroonrk, chokudai, wata
Overall, 10,586,135
Congratulations!
Team: rushabh7 madhur817 karan_noob
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.
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.
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!
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!
I know people have used constraint solvers in the past for hashcode -- did anyone do that this time?
Our very first participating in HashCode, team We hate Gabi: Ahmad-Magdy, maghrabyJr_ and me.
D was a real challenge, yet we enjoyed the contest. Looking forward to participating next year with better results insha’Allah.
Rethinkers — Radewoosh, znirzej, shadowatyy, xman1024
1st in our hub Motilal Ke coders(MNNIT) //thats also ranked 31 out of 490 total worldwide
142 in India ,944 Globally
Team- is_it_rated
Rook_Lift ,Electron ,Invincible06,Anurock007
It was a fantastic experience waking up till 4am and improvising the PS....thanks Hashcode
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.
Here's a simple version of what I wrote during the contest: simulator
Main ideas:
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.
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.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
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,
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)
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
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.
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.
Please see the comment I wrote above (http://codeforces.com/blog/entry/88188?#comment-766186) :)
Thanks! I will look into it and get back to you!
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 :)
Blue: Gaurav1 | abhigyan10 | crimsonred | svince
India $$$#49$$$, World $$$#344$$$.
Ended up with 9.5 million (Rank: 879)
1) 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.
Team : deep_gajjar123, mon0pole, sahil903
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.
Egypt #3, World #204.
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.
Give the most used streets more than 1 second.
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.
Score Distribution this year
Code to plot — https://gist.github.com/tonghuikang/65ec83e270b3d8a68432b2d2382ada5e
Where did you get the data from?
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
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/
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.
Are those cars in front of the line? They might be queueing behind other cars on the same street.
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:
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.
Maybe you can try to see what happens if you submit a solution with only that one intersection?
@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.
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.
I wrote to google team too :) And got a similar response.
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/yf2z41h
If for some reason the picture still doesn't work, PMme and I will send you the pictures.
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.
Do anybody know how many teams are selected for Final round?
My Score: 9200000
My rank: 2k
verdict: not selected.
Where can you see if you were selected or not? Results link on hashcode website seems to be broken
Well, they said those who are selected will be notified by 2nd March, and I haven't. Can I ask what was your rank?
25th. Apparently, they are still not finalized results, according to answer to my email
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.
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.
Ok. Wish you good luck!
Team memebers Ahmadsm2005, ahmedfouadnew, Blobo2_Blobo2
Team UVIGO Bruteforcers (in Extended Round):
We did poorly during the round itself, so we worked hard afterwards: We ranked 2nd on the scoreboard of the Extended Round.
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 points
B – By the ocean 4,569,814 points
C – Checkmate 1,315,372 points
D – Daily commute 2,495,884 points
E – Etoile 779,279 points
F – Forever jammed 1,478,004 points
Total score 10,640,355 points
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.
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.
You can't ask questions for a running contest.