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, 05.02.2022 13:00 (Московское время).
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:
Winners among the participant of PTZ training camp:
rated?
No
.
no, it's unrated, will add this information in the post
How many problems?
One
Is it right?
Yes, it'll be one problem, but quite a few tests
Thanks a million. You are so kindness.
it is rated ?
no
On the same day as the Quora contest just before it, we will have an interesting day
А что подразумевается под "интерактивная оптимизационная задача с открытыми тестами"?
Нужно будет решать тесты локально, а отправлять только ответы? Или посылать код, который решает задачу на сервере?
Предполагается, что в итоге команда отправляет одно решение, которое написано на одном языке программирования, или будет можно, например, написать разные решения для разных тестов?
Отправлять нужно будет решение, которое будет коммуницировать с интерактором на структуре, которая известна для каждого теста. Формально разные тесты будут выделены в отдельные задачи, поэтому можно будет отправлять разные решения для разных тестов.
This contest is a great rehearsal for Hash Code!
Also thanks for avoiding a time conflict with Quora's contest.
Is this contest rated?
So the answer is NO
NO
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 ?
After you click on register contest, you have 2 options.
But it shows nothing when I click box of choose team (after selecting as a team member option). How to proceed?
Is this problem about algorithm, or about puzzle, scenario simulation or machine learning?
About algorithms
Pinely
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 ?Why you guys are always after rating ? There is also a world beyond that.
Is it rated?
Third paragraph 2nd line:- The contest will be unrated.
Thank you!
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
Why the contest is not rated? :( Rated contest gives more feel
。。。
i think difficulty of the problem will be 3500.
Will AI register? [doge]
Will terminators participate in this contest
I like your choice of using plurals :P
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.
Simple randomize can get 2100 points...
Can you please share code of your solution? I would be very happy to check how you implemented 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 (･∀･)
Thank you
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"
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.
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.
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.
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 :)
Will there be editorial?
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.
Thank You
rank 97 for lucky.
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
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
Would be nice if contests like this would provide an interactor for the problem, like how IOI or GCJ does.
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.
Would post-contest submissions be allowed after a while?
they are allowed now
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
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.
Автокомментарий: текст был обновлен пользователем pinely (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by pinely (previous revision, new revision, compare).
Unrated, right?
Very bad contest for me