MiptLited's blog

By MiptLited, 4 weeks ago, translation, In English,

The Moscow Institute of Physics and Technology welcomes high school students to take part in the programming boot camp Moscow Workshops Juniors! The boot camp will be held from February, 25 to March, 6.

The educational program includes daily studying contests, thematic lectures and practice. In a free time participants could join the popular science lectures, do sports, play the intellectual games and be involved in other activities. According to the results of the introductory contest the participants are divided into divisions depending on their skill level. Participants can choose the most interesting topics and make an appropriate training program. If a participant finds the curriculum too simple or difficult, he can change division.

To take part in the camp, you have to pass qualifying online tours, its format is close to the Olympiad in Informatics. You can participate in several rounds or only in one tour, the ranking of the participants is made according to the results of four rounds. The selection rules can be found by the link.

There are four qualifying rounds:

October, 27 at 16:00 pm UTC+03

November, 18 at 12:00 pm UTC+03

December, 16 at 12:00 pm UTC+03

January, 20 at 12:00 pm UTC+03

Moscow Workshops Juniors suggests awarded high school students several opportunities of participation. If you are a prize-winner of national Olympiads in informatics 2017-2018, you are invited to take part in the Workshops free of charge! For participants of national Olympiads in informatics 2017-2018 the Workshops cost $400, for another participants – $700

REGISTRATION

Have questions still? Write to organizing committee email: zksh-team@phystech.edu

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

»
3 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

There is a limit for character count in the application page. For example, I can't paste my codeforces account link or my school name.

»
3 weeks ago, # |
Rev. 2   Vote: I like it -23 Vote: I do not like it

MIPT is the best university!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Your code here...
Ngu Loz
»
3 weeks ago, # |
  Vote: I like it +42 Vote: I do not like it

So the Octomber one is just the trial round or an actual qualification round? (the first qual. round is "temporarily unavailable")

»
3 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

Is there a tutorial for the first round? and can we discuss problems now?

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How about the accomodation ? How much is it and where ?

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Can anyone describe the solution for problem D: Presents?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    You need to find n smallest linear combinations of presents. For this, I used set<pair<int,int>> to store price and linear combination hash. Hash was just sum of random weights assigned for each present. Initially set was with {{0,0}}. I just removed a minimal element (x,y) from set n + 1 times and added elements (x + p[i], y + w[i]) to the set and added x to the answer. w[i] is just a random value assigned to each present.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      isn't there a high probability that there would be a hash-collision as it is just a linear combination of random weights. I feel like a collision would be frequent.

      Maybe it can be reduced by storing a triplet in the set and for each present have two different random weights.

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

        Yes, you could store multiple hashes, but as I have seen, random weights are expected to work almost all of the times. It is quite unpredictable. I don't know if any anti hash anti-hash tests exist. Thinking about the ways to check collisions I came up with a trie-ish idea. You could store those linear combinations in a trie (moving down one node means adding some present) and you would only need to store O(1) data to be able to recover a full linear combination. It would be harder to implement and probably a lot slower. And we need to store only up to 1000 best linear combinations at a time if the hash is a random 64-bit integer collision should not occur.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Assuming that the both the numbers in the tuple randomly and uniformly vary between 1 to 1e9, then there are 1e18 total combinations. Probability of a collision for n numbers would be about n^2*(1e-18) which is basically 0. However, I am not sure how good the assumption is.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            You should use birthday paradox to find the exact probability.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes. In my calculation I assumed there would be n^2 comparisons(although there are actually nC2 comparisons). Each comparison has 1e-18 probability of collision. Hence I multiplied n^2*1e-18.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

If someone needs the solutions for the problems from the first qualification, here are mine:
Problem A
Problem B
Problem C
Problem D
Problem E
Problem F

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there public standings available somewhere? (Past contests and an ongoing one)

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

    Do you mean ongoing icpc workshop standings? This is a topic for school students.

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

      Oops, the wrong topic indeed :) Supposed to ask in a different one :) Yep I meant the ongoing icpc workshop.

      UPD found them, now there're links from the main webpage of the workshop