pinely's blog

Pinely Treasure Hunt Contest
By pinely, 3 years ago, In English

Hello, codeforces!

Pinely is a high-frequency trading company. We trade at the exchanges all over the world. This year we are the sponsors of the online PTZ competitive programming camp. We have prepared a fun contest for camp participants and invite everybody to join it on CodeForces!

Pinely Treasure Hunt Contest will be held on Saturday, Feb/05/2022 13:00 (Moscow time).

The participants will be offered to solve an interactive optimization problem with open tests and will have 3.5 hours to work on it. You can join individually or in teams of up to 3 people. The contest will be unrated. Winners among camp participants as well as the 3 best teams in overall standings will be awarded with pinely t-shirts.

Since the contest is targeted for participants of the PTZ training camp, it'll be most interesting for participants with codeforces rating 2000+.

We are grateful to MikeMirzayanov for the opportunity to host the contest on codeforces.

A couple of words about pinely: we conduct algorithmic trading on various exchanges. Our offices are located in Amsterdam, Singapore and Cyprus. Our colleagues face various challenges, such as: coming up with trading strategies and implementing them, optimizing trading systems to achieve the fastest reaction to the market events, storage and processing of high volumes of historical data. Ability to write effective C++ code, algorithmic thinking and mathematical intuition are all useful in our day-to-day work, so a significant part of our team participates in various programming and math competitions.

To learn more about pinely you can visit pinely.com or you can find our colleagues on CF in pinely organization. You can send us your CV to [email protected], even if you are not participating in the contest.

Good luck and have fun!

UPD Congratulations to the winners!

Winners of the joint contest:

  1. itmo.algo.teaching: tourist, pashka, budalnik

  2. SPb NRU ITMO 3: VArtem, antonkov, qwerty787788

  3. xyr and his friends: wygzgyw, frame233, wasa855

Winners among the participant of PTZ training camp:

  1. Never Give Up: Valera_Grinenko, ivanz, 353cerega

  2. Saratov SU Daegons: awoo, Neon, vovuh

  3. A-SOUL_Unofficial: Pub, pigstd, dXqwq

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

Comments Comments (58)
| Write comment?
»
3 years ago, # |
  Vote: I like it -54 Vote: I do not like it

rated?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -66 Vote: I do not like it

.

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

    no, it's unrated, will add this information in the post

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -78 Vote: I do not like it

it is rated ?

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

On the same day as the Quora contest just before it, we will have an interesting day

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

This contest is a great rehearsal for Hash Code!

Also thanks for avoiding a time conflict with Quora's contest.

→ Reply
»
3 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Is this contest rated?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to register for this contest as a team , like the leader must individually register and then we can enter , or what's the process ?

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

    After you click on register contest, you have 2 options.

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

      But it shows nothing when I click box of choose team (after selecting as a team member option). How to proceed?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it
        1. Go to you profile page and select "TEAM" tab.
        2. Here you can see a "Create new team", click it, enter team name, and a new team will be built.
        3. You will see "invite user" at the main page of the team. Click it and invite your teammates.
        4. Wait for you teammates to accept.
        5. Go to contest page, there you can select your team to participate. That's it!
        → Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Is this problem about algorithm, or about puzzle, scenario simulation or machine learning?

→ Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it -33 Vote: I do not like it

Pinely

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ? is it rated ?

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

    Why you guys are always after rating ? There is also a world beyond that.

    → Reply
»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is it rated?

Third paragraph 2nd line:- The contest will be unrated.

Thank you!

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

    just FYI they edited the post after some hours and added that the contest is unrated, so most of this comments are not trying to be funny but the answer was just not there

    → Reply
»
3 years ago, # |
  Vote: I like it -32 Vote: I do not like it

Why the contest is not rated? :( Rated contest gives more feel

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

。。。

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i think difficulty of the problem will be 3500.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will AI register? [doge]

→ Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Will terminators participate in this contest

→ Reply
»
3 years ago, # |
  Vote: I like it +94 Vote: I do not like it

Please share your thoughts about the contest :)

Some ideas of our approaches to different tests:

1) Leaves are easy to traverse: just go there and return immediately

2) If there is an unvisited adjacent vertex, we can go there. Which one to choose? Firstly leaves, than for example with smallest/largest degree or, if the graph has a specific repeatable structure — based on a custom function from set of degrees to degree that should be chosen

3) If all the adjacent vertices has been visited, where should we go? Maybe at random

4) Or we can try to simulate depth first search, let's try to go to parent: choose some vertex having the degree of the parent. If we are unlucky — let's try to get to parent twice then. This works if there are not many close vertices with the same neighbourhood descriptions.

5) Alternatively, we can agree to end up in some indirect ancestor of the path. Let's find a matching description then and pop the suffix of the path. In both approaches 4) and 5) if something goes wrong we can stick to 2) — probably there'll be few vertices left to traverse.

6) Another alternative is to write beam search: we can maintain some bounded number of states (vertex, bitset of visited vertices), possibly with their probabilities. Then use some heuristics to pick the best next vertex degree for each state and then choose the degree from a discrete distribution. The option could be "go along the shortest path to some unvisited vertex" or something different that makes sense.

7) One can also add a simple path to the state and the vertex will "vote" to go to its parent, thus simulating a "beam depth first search". There will be more states, but probably not many on some graphs.

8) If you are traversing a tree maintaining states, there's no need to add states for all isomorphic subtrees if there are many such options. Let's assume we're traversing them one by one.

9) Try to research the graph structure: it it has some regularity, probably you can traverse it optimally, using hardcoded functions from set of degrees of neighbors to the desired degree. This can give improvement which even reaches the optimal TSP solution.

10) If you have time, you can try to automate the approach from 9).

11) One can divide the graph into 2-connected components, traverse them and articulation points optimally and use some greedy approach inside the components.

12) If you run out of ideas how to significantly improve your algorithm on interesting tests, then you can take your time to abuse randomness: for example, bruteforcing your seed.

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

    Simple randomize can get 2100 points...

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

      Can you please share code of your solution? I would be very happy to check how you implemented it.

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

        Here's my code: https://paste.ubuntu.com/p/5yJHHfQTrG/

        I only use the information of degrees and flags. For each step, try to visit unflaged vertexes firstly, then flaged vertex. I tried some strategies like sorting by degrees (increase/decrease) or picking them randomly (for prob C, just go to the biggest degree vertex). Theres' another special case: if degree = 1 and flag = 1, never visit this vertex again. Then just submit these codes and see how lucky I am (･∀･)

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

    For future rounds: it would be more convenient if you names the problems by tests. I tried to hover my cursor over the problem index in the scoreboard to find out where I lose so much, just to see "treasure hunt"

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

      We agree, it was a brand new format for codeforces, probably for next such round (if any) this feature could be implemented. You've also noticed that the archive with tests was attached 11 times :) The alternative was to copy the problem 10 times in polygon, which doesn't look like a safe and convenient solution.

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

    An example of approach 9) is the test J3. There you have a clique of size 40 sharing 6 different vertices with 6 cliques of size 11 and also a vertex with a path of length 200. To optimally traverse this graph you need firstly to traverse all small cliques, then traverse remaining vertices of the large clique (or vice versa) and only then go along the path. If you enter the path earlier, you might get stuck there for quite a long time. Since the vertices are very easily distinguishable based on their degree, it's quite simple to traverse that graph deterministically.

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

    Thanks a lot for the contest! It was fun, even though pretty random (but maybe "random" actually contributed to "fun").

    Our initial approach was going to the unvisited neighbor with the smallest degree or, if all neighbors are visited, choose one at random with weights proportional to their degrees. This approach actually lived till the very end, resulting in the best scores for some test cases.

    Another useful approach implemented by budalnik was similar to beam search you described in 6), I believe.

    We also solved H1-H3, J1-J3, and K3 perfectly, and I wonder what other test cases were solvable perfectly. It was interesting to figure out the structures of the graphs and the algorithms to traverse them. On the other hand, test cases like D1 seem kind of unsolvable — after you end up at the end of the chain, it seems the only way to go back is to keep trying (?), and the only meaningful way to increase your score is to make more submissions with different random seeds.

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

      Thanks for the kind feedback! It seems that your G1, G2 are also optimal: these are trees on which dfs from 4) should work perfectly and so do some other approaches. We don't know if other tests are solvable perfectly if perfectly means "deterministically use number of moves equal to tsp problem output". It's great that your team got all the perfect scores which were intended, congratulations on that and the victory! :)

      Indeed it seems there was too much randomness, probably having more tests like H and J would make the contest more fun.

      Your initial approach makes sense, somehow we haven't tested a version with discrete distribution proportional to degrees of the vertices (though we've applied such distribution in "beam search-like" solutions, which helped to avoid infinite loops). Kudos on making the simple (on a first sight) approach to successfully solve many tests :)

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be editorial?

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

    Since the problem is marathon-style, we don't see how the classical editorial would look like. Instead we've posted several ideas how to approach the problem in the comment. One can implement some approaches and run them on the tests. If you have specific questions to this description — feel free to ask in the thread.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

rank 97 for lucky.

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

My main approach was something like "go to a random unvisited vertex with the smallest degree among such ones, if we cannot, then go to a random vertex with degree > 1".

How to solve Kneser-2? I can achieve 89.2309 on Kneser-1 and 84.8935 on Kneser-3, but I have no idea how to distinguish vertices in Kneser-2

→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I just applied various combinations of randomization of vertices which can be visited and which cant be visited and submitted. It got me 1600 score. I didn't use a single fact which is related to graph to optimize. lmao

→ Reply
»
3 years ago, # |
  Vote: I like it +60 Vote: I do not like it

Would be nice if contests like this would provide an interactor for the problem, like how IOI or GCJ does.

→ Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Contest of LUCK! That's such a funny contest, especially when we submitted one code for many many times just for tiny changes of scores.

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Would post-contest submissions be allowed after a while?

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

There should have been a cap on number of submissions. My team got to 1900+ points just by selecting a random unvisited (or visited if there are no unvisited adj nodes) node out of the available ones, and then spamming submissions lol

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

    Yes, we underestimated the power of random abuse in the problem, sorry for that. We thought that most participants would try to study the structure of specific tests and make tailor-made solutions for them, but it turned out seed brute force often was more advantageous.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pinely (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it -27 Vote: I do not like it

Unrated, right?

→ Reply
»
3 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Very bad contest for me

→ Reply