Previous challenges

Hi, it's been very long time from last Programming Challenge, and I'd like to revive the tradition.

The point of programming challenge is to create your own solution, and if you're bored, even program it in your favourite programming language. Today's challenge isn't mine. It was created by ČVUT FIKS (year 5, season 2, challenge #4).

You need to transport plans for your quantum computer through Totalitatia. The problem is, that Totalitatia's government would love to have the plans. And they know you're going to transport the computer through the country. You'll receive number N, which denotes number of cities on the map. Then, you'll get M paths, each going from one city to another. Each path has k traffic controls. They're not that much effective, but the less of them you have to pass, the better. Find path from city A to city B, so the maximum number of traffic controls between any two cities is minimal. City A is always the first one (0) and city B is always the last one (N-1).

Input format:

N
M
A1 B1 K1
A2 B2 K2
...

On the first two lines, you'll get numbers N (number of cities) and M (number of paths). Than, on next M lines, you'll get definition of a path. The definition looks like 1 2 6, where 1 is id of first city and 2 is id of second city (delimited by a space). You can go from city 1 to city 2, or from city 2 to city 1. The third number (6) is number of traffic controls.

Output format:

Single number, which denotes maximum number of traffic controls encountered on one path.

Hint: This means, that path that goes via roads with numbers of traffic controls 4 4 4 is better than path via roads with numbers of traffic controls 1 5 1. First example would have output 4, the second one would have output 5.

Example:

IN:

4
5
0 1 3
0 2 2
1 2 1
1 3 4
2 3 5

OUT:

4

Solution: The optimal path is either 0 2 1 3 or 0 1 3.

Bonus

• Describe time complexity of your algorithm.
• If multiple optimal paths exist, find the shortest one.
• Does your algorithm work without changing the core logic, if the source city and the target city is not known beforehand (it changes on each input)?
• Do you use special collection to speed up minimum value search?

Hints

Special collection to speed up algorithm

Hi everyone, it's been 12 days since last programming challenge. So here's another one. The task is to make an algorithm that'll count how long would it take to fill system of lakes with water.

It's raining in the forest. The forest is full of lakes, which are close to each other. Every lake is below the previous one (so 1st lake is higher than 2nd lake, which is higher than 3rd lake). Lakes are empty at the beginning, and they're filling at rate of 1l/h. Once a lake is full, all water that'd normally fall into the lake will flow to the next lake.

For example, you have lakes A, B, and C. Lake A can hold 1 l of water, lake B can hold 3 l of water and lake C can hold 5 l of water. How long would it take to fill all the lakes?
After one hour, the lakes would be: A (1/1), B (1/3), C(1/5). After two hours, the lakes would be: A(1/1), B(3/3), C(2/5) (because this hour, B received 2l/h - 1l/h from the rain and 1l/h from lake A). After three hours, the lakes would be: A(1/1), B(3/3), C(5/5). So the answer is 3. Please note, that the answer can be any rational number. For example if lake C could hold only 4l instead of 5, the answer would be 2.66666....

Hour 0:

\            /
  ----(A)----
                       \                /
                        \              /
                         \            /
                          ----(B)----
                                             \           /
                                              \         /
                                               \       /
                                               |       |
                                               |       |
                                                --(C)--

Hour 1:

\============/
  ----(A)----
                       \                /
                        \              /
                         \============/
                          ----(B)----
                                             \           /
                                              \         /
                                               \       /
                                               |       |
                                               |=======|
                                                --(C)--

Hour 2:

            ==============
\============/           |
  ----(A)----            |
                       \================/
                        \==============/
                         \============/
                          ----(B)----
                                             \           /
                                              \         /
                                               \       /
                                               |=======|
                                               |=======|
                                                --(C)--

Hour 3:

            ==============
\============/           |
  ----(A)----            |             ========
                       \================/       |
                        \==============/        |
                         \============/         |
                          ----(B)----           |
                                             \===========/
                                              \=========/
                                               \=======/
                                               |=======|
                                               |=======|
                                                --(C)--

Good luck everyone! Tell me if you need clarification or a hint. I already have a solution, but it sometimes doesn't work, so I'm really interested in seeing yours :-)

I'm running out of ideas, if you have any, please make your own programming challenge.

This challenge is about designing algorithm to solve this problem.

Let's have game field of size x, y (like in chess). There are two wizards, that are standing at [ 0, 0 ] and are teleporting themselves using spells. The goal is to not be the one who teleports them outside of the map. Each spell teleports wizard by at least +1 tile. Given map size and collection of spells, who wins (they do not make any mistakes)?

Here are few examples:

Example 1

x:4,y:5

Spells: { 0, 2 }

Output: false

Description: Wizard A starts, teleporting both of them to 0, 2. Wizard B teleports them to 0, 4. Wizard A has to teleport them to 0,6, which overflows from the map, so he loses the game. Because starting wizard (wizard A) loses, output is false.

Example 2

x:4,y:4

Spells: { 1,1 }

Output: true

Example 3

x:4,y:5

Spells: { 1,1 },{ 3,2 },{ 1,4 },{ 0,2 },{ 6,5 },{ 3,1 }

Output: true

Example 4

x:400,y:400

Spells: {9,2},{15,1},{1,4},{7,20},{3,100},{6,4},{9,0},{7,0},{8,3},{8,44}

Ouput: true

Good luck! I'll comment here my solution in about a day.

Note: This challenge comes from fiks, programming competition by Czech college ČVUT (CTU).

I've been trying to tame tracking from services like Facebook. I installed many ad blockers and tracker blockers on all of my browser, I don't install FB app on my phone, but I still install Instagram app and WhatsApp.

Something creepy (but totally expected) just happened to me. I haven't really been in contact with a friend of mine for quite some time, and we finally chatted again using WhatsApp. Not long after that I opened Instagram, and her photo was the first one I saw haha. It's funny because I don't think I've seen any photos from her in quite some time before this on my IG feed.

Might just be a coincidence, but with all discussion about how creepy they're trying to make their platform as sticky as possible, I wouldn't be surprised if IG's feed algorithm do take into account your correspondence on WhatsApp as well (I live in a country where everyone uses WhatsApp).