Google Hashcode 2021 Qualifiers Discussion

4 года назад, # ^ |

+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!

→ Ответить

kwangg

4 года назад, # |

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

→ Ответить

AhmadEbtihal

4 года назад, # |

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.

→ Ответить

znirzej

4 года назад, # |

+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

→ Ответить

Rook_Lift

4 года назад, # |

-24

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

→ Ответить

rananjay23

4 года назад, # |

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.

→ Ответить

misof

4 года назад, # ^ |

← Rev. 2 →

+12

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.

→ Ответить

minty99

4 года назад, # |

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

→ Ответить

pranayreddy1024

4 года назад, # ^ |

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

→ Ответить

minty99

4 года назад, # ^ |

← Rev. 3 →

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 года назад, # ^ |

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.

→ Ответить

minty99

4 года назад, # ^ |

Please see the comment I wrote above (http://mirror.codeforces.com/blog/entry/88188?#comment-766186) :)

→ Ответить

4 года назад, # ^ |

Thanks! I will look into it and get back to you!

→ Ответить

Qg3

4 года назад, # |

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

→ Ответить

svince

4 года назад, # |

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

→ Ответить

Priyansh31dec

4 года назад, # |

Ended up with 9.5 million (Rank: 879)

Some Mistake that we made

→ Ответить

mon0pole

4 года назад, # |

← Rev. 3 →

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.

→ Ответить

NightRage

4 года назад, # |

← Rev. 2 →

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.

→ Ответить

shashankk

4 года назад, # |

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 года назад, # ^ |

Give the most used streets more than 1 second.

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

huikang

4 года назад, # |

+62

Score Distribution this year

Code to plot — https://gist.github.com/tonghuikang/65ec83e270b3d8a68432b2d2382ada5e

→ Ответить

lukasz_strong_wsm

4 года назад, # ^ |

Where did you get the data from?

→ Ответить

https://curiouscoding.nl/hashcode-2021/

4 года назад, # |

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

→ Ответить

Philae

4 года назад, # |

← Rev. 2 →

+36

I did a write-up of all the bugs and mistakes (and also some good ideas) we made during the contest:

→ Ответить

coconut_

4 года назад, # |

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.

→ Ответить

TimonKnigge

4 года назад, # ^ |

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

→ Ответить

coconut_

4 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Philae

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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

→ Ответить

coconut_

4 года назад, # ^ |

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 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

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.

→ Ответить

Philae

4 года назад, # ^ |

← Rev. 2 →

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 года назад, # |

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

My Score: 9200000

My rank: 2k

verdict: not selected.

→ Ответить

Egor

4 года назад, # ^ |

+23

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

→ Ответить

4 года назад, # ^ |

← Rev. 3 →

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

→ Ответить

Egor

4 года назад, # ^ |

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

→ Ответить

4 года назад, # ^ |

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.

→ Ответить

Egor

4 года назад, # ^ |

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 года назад, # ^ |

Ok. Wish you good luck!

→ Ответить

Blobo2_Blobo2

4 года назад, # |

Team memebers Ahmadsm2005, ahmedfouadnew, Blobo2_Blobo2

→ Ответить

4 года назад, # |

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

→ Ответить

noovd

4 года назад, # ^ |

← 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 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 года назад, # ^ |

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

→ Ответить

codingwithfun

4 года назад, # ^ |

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.

→ Ответить