Lain's blog

By Lain, history, 4 years ago, In English

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

Good luck!

  • Vote: I like it
  • +147
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Oh it was alright! How it went everybody?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it
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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    Can you plese share your approach here

»
4 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +102 Vote: I do not like it

    How did you get such a high score in D?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +47 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank you! I was able to increase our score on D by 550k (from 1.6M to 2.1M) because of this!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    majk majak krra D m?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    Your total score = 10458759

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

»
4 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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

»
4 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

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)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Two optimizations:

      1. Increase random showtime by $$$\pm1$$$. Repeat while it makes the score better.

      2. 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)

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it +10 Vote: I do not like it

          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

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your teammate have 0 line of code contribution

»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Team: armyalpaca, davi_bart, rocks03, TheScrasse


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
»
4 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it
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
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it
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
»
4 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Team: sharath101 munghatekartik Shahraaz __sharma__

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
4 years ago, # |
Rev. 2   Vote: I like it +138 Vote: I do not like it

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).

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Congratulations! Funny fact that if we had got the same of your score in D, we’d be the 12th worldwide :V

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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). ^_^

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I watched your videos before the HashCode and I got 9,579,637 points, big thanks to you.

»
4 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it
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 :-)

»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it
  • A – 2,002
  • B – 4,568,673
  • C – 1,305,761
  • D – 2,483,087
  • E – 734,237
  • F – 1,104,818 points
    Total score – 10,198,578 points
»
4 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Harshu2608 manpreet.singh

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
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • 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
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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 :/ )

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    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 :-)

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it +11 Vote: I do not like it

        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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • 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
»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Team: 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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +228 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
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

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +184 Vote: I do not like it

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!

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    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!

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I know people have used constraint solvers in the past for hashcode -- did anyone do that this time?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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
»
4 years ago, # |
  Vote: I like it -24 Vote: I do not like it

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

  • 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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    Here's a simple version of what I wrote during the contest: simulator

    Main 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.

»
4 years ago, # |
Rev. 9   Vote: I like it +12 Vote: I do not like it
  • 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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
4 years ago, # |
Rev. 4   Vote: I like it +16 Vote: I do not like it
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 :)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Blue: Gaurav1 | abhigyan10 | crimsonred | svince

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$$$.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Ended up with 9.5 million (Rank: 879)

Some Mistake that we made
»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Team : deep_gajjar123, mon0pole, sahil903

   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.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
  • 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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Give the most used streets more than 1 second.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

»
4 years ago, # |
  Vote: I like it +62 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 years ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

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/

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Are those cars in front of the line? They might be queueing behind other cars on the same street.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe you can try to see what happens if you submit a solution with only that one intersection?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        @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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I wrote to google team too :) And got a similar response.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Do anybody know how many teams are selected for Final round?

My Score: 9200000

My rank: 2k

verdict: not selected.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Where can you see if you were selected or not? Results link on hashcode website seems to be broken

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      Well, they said those who are selected will be notified by 2nd March, and I haven't. Can I ask what was your rank?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        25th. Apparently, they are still not finalized results, according to answer to my email

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
4 years ago, # |
Rev. 7   Vote: I like it +13 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

    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

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          You can't ask questions for a running contest.