MiptLited's blog

By MiptLited, 5 years ago, translation, In English

UPD2: Standings: http://opentrains.mipt.ru/~ejudge/showres.cgi?data=resExt

http://opentrains.mipt.ru/~ejudge/showres.cgi?data=resExt2

UPD: registration deadline extended to April 25 23:59 (Moscow).

On April 26, 2020 at 10 AM (Moscow) join the international competitive programming e-championship RuCode Festival.

Rucode Festival is a great opportunity to prove yourself and get experience in programming competitions. The Championship will be held in two different levels of complexity: for A/B divisions and for C/D divisions. The tasks will be in English and in Russian.

To take part please register until April 22, 23:59 (Moscow)

The Championship Schedule:

Opening: 10:00 — 10:30

Trial round: 10:30 — 11:00

Contest: 11:00 — 16:00

Contest analysis: 17:00 — 19:00

The tasks are made by the leading Russian universities professors, champions of international competitions and coaches of Moscow Workshopssnarknews, 300iq, veschii_nevstrui, DPR-pavlin, I_love_myself.

RuCode Festival is held by MIPT, Yandex, MegaFon and supported by Phystech Schools Development Fund, Presidential Grants Fund и Analytical Center for the Government of the Russian Federation.

See you at the RuCode e-Championship!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Yuppi! It will be good for quarantine.

»
5 years ago, # |
  Vote: I like it +42 Vote: I do not like it

The web site is not fully translated and it gives me anxiety

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

    we are working on it, thx

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

    Select Language as Russian and then in google chrome you get notify automatically to convert into English, Click On Always Convert Russian and then you get whole site converted into English. Enjoy Buddy, Happy Coding :)

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

can everyone register?

»
5 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Could you provide some more details about the contest? Will it be individual contest? Will problems be of ACM-type (full feedback and AC/no AC)? How many problems will be there? Are there some prizes? What are these weird letters A/B/C/D denoting divisions?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -47 Vote: I do not like it

    This is what you need: https://rucode.net/?lang=en

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

      I read through that page and I didn't see the answer to any of Swistakk's questions...

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

    Division A/B will be an ICPC contest from me, same as GP of Moscow on 26th of April.

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

      So, it means that it's a team competition, right? At least I hope so.

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

      Ahh, ok, I planned participating in that GP anyway :)

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

    Will it be individual contest?

    it will be team contest (3 people), but in current situation there is possible individual participation or 2 persons in one team

    Will problems be of ACM-type (full feedback and AC/no AC)?

    it will be classical ACM-type contest

    How many problems will be there?

    8-13 as usual :)

    Are there some prizes?

    announcement will follow

    What are these weird letters A/B/C/D denoting divisions?

    Division A is designed to prepare students to participate and win medals in the ICPC World Finals. Division B is designed to help teams prepare for regional and international competitions. Division C/D is for beginners in competitive programming. The list of the topics in each division will be posted on the web-site a bit later.

    Difficulty of the contest matches level of the division.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      когда должно прийти письмо, по добавлению команды?

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

But real question is

Spoiler
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I don't have a middle name , what to fill while registration (Its mandatory) ??

»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Why don't you add more contests for this quarantine? like daily or in alternate days.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone not from Russia participate in this contest?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great opportunity for great people

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will it be held on Codeforces?

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

    Wondering the same

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

    As of now it is not going to be on codeforces, but it will be a part of Opencup.

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

      That should've been mentioned right at the start of the announcement, it would answer a lot of questions.

»
5 years ago, # |
Rev. 2   Vote: I like it +81 Vote: I do not like it

You're announcing a team competition without even saying that it's for teams? Come on... Just say next time that this is a public opencup contest.

On the bright side, I appreciate the detailed description of "the team" on your website. I never know if I should participate in a contest if I don't know the exact title of author's PhD thesis.

[...] Moscow Programming Contest PhD dissertation: "Outer billiards outside regular polygons: sets of full measure, aperiodic points and sets of periods", defended successfully in 2019.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

During the contest, the website is taking a hell of a time. And sometimes a contest is not running yet website won't open

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

How can I register my team and connect opencup account with RuCode?

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Will editorials be published after contest?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will it be rated?

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

Should every team be limited to a single computer?

Edit: detailed answer.

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

    no, each team can have 3 computers, but log in with one team-account

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

      I believe each team is supposed to use only one computer in every moment.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any language restrictions?

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

Will i be able to indicate my team after 22 April if every member of my team registered?

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The contest website and some comments below indicate that this a team contest(Team of 3). But I can't find any option to form/register as a team? I've already registered on the site individually. What steps should I further follow?

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

I have a few questions:

  • Must every team member have an account on the website, or only one for the whole team?
  • What do we have to do after we have completed the form from the website?
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Must every team member have an account on the website, or only one for the whole team?

    Each should have an account

    What do we have to do after we have completed the form from the website?

    Wait until you get the email (April 22), there you will enter the name of the team and team members

»
5 years ago, # |
  Vote: I like it +52 Vote: I do not like it

To be honest, I am deeply confused about this whole announcement. We already learnt that this competition is just another OpenCup even though it is not indicated in any way in original announcement which doesn't even say that it is team competition (that alone is kinda asburd to me). Why is it given some different name in that case? Why do you tell people to register on that site even though, as far as I understand, we should compete in it as in any other OpenCup through our dedicated Yandex account? What is that website for in that case? OpenCup accounts are not easily created. Does that site let you compete in that particular OpenCup through it for people that are not usual OpenCup competitors? And one more very important question — why do you say here: https://codeforces.net/blog/entry/76187?#comment-607605 that we are allowed to use 3 computers even though on OpenCup people are allowed to use only one?

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

    It is not only the Opencup tour — people can win prizes in Rucode, get diplomas, join stream (in Russian). A team can join only Opencup, but then the results will not be counted in Rucode.

    Not everybody is able to participate in Opencup. There were thousands of new students involved in educational part of Rucode — for them this competition is a part of Rucode.

    Regarding 3 computers — the rules are standard; a team is allowed to use 3 computers (which is more than ok regarding the pandemic situation), but at most one participant should be coding, compiling, testing or submitting a solution simultaneously. This is exactly the same as for OpenCup. We believe that everybody will follow these rules :)

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

      We were planning to participate in OpenCup only, so we didn't register for RuCode. Currently entering through the OpenCup website only gets us "Not Found". So is it not possible to participate via OpenCup after all? Is there any way for us to submit our solutions?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the Ejudge testing system where the contest will be held?

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

Like, till when we would get the Mail for Team Registration?

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

Div A and B are different or same.coders selecting A/B will be given same set of problems or it is like div 1/2 on codeforces.

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

    Yes, Div A/B are the same. They don't match with codeforces div 1/2.

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      So. what is the difference between A and B? Different scoreboards or what?

»
5 years ago, # |
  Vote: I like it +29 Vote: I do not like it

This time the statements of my problems will be short!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to give the trial contest. When I log in, I can't see any problems right now!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My team is participating in Div C/D. In the contest it was written that tomorrow's contest is a qualifying round for attending interactive courses on AI and cp. Can you specify how many teams will be shortlisted to attend those courses from all the divisions?

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

My team are experiencing lag and slow connection during trial contest, sometimes we can't connect to the webpage at all. Are we the only one who experience this? And will it get better when the round starts?

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Unable to submit. It shows clients suspended.

»
5 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

Why is it showing "CLIENTS SUSPENDED" in submit and other options ?? We are unable to submit the code..

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Programme is compiling for about 20 minutes, that is unbelievable...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You guys took more than one hour to update team status on dashboard ..We(My team) decided to participate individually because there was no sign of team or team name anywhere ...And after 1 hour (+ 30 min trail round) team status got updated with this message "Client Suspended"

»
5 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Compiling since half an hour. I expected the platform to be better than this :(

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

I think now we should appreciate the Codeforces platform. It works perfectly. Thanks to Mike.

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

    They could have used CF platform instead. It would have been much better.

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

How to solve G?

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

    For each vertex choose some 14-bit hash. For each edge $$$(v, u)$$$ if there is a bit $$$i$$$ that is $$$0$$$ in $$$hash(v)$$$ and $$$1$$$ in $$$hash(u)$$$, color it in the $$$i$$$-th color. It doesn't work when you have some $$$v$$$ and $$$u$$$ such that $$$hash(v) | hash(u) = hash(v)$$$. If you choose as hashes numbers with popcount equal to $$$7$$$, this will never happen. Luckily $$${14}\choose{7}$$$ is greater than $$$3000$$$.

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

      Do you randomize which vertex gets which hash? And what if an edge has multiple bits that have this condition? Do you choose the smallest i?

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

        No, no random required. And you can choose any $$$i$$$. It's correct because if vertex $$$v$$$ has outgoing edge of color $$$i$$$, then its $$$i$$$-th bit has to be $$$0$$$, and if it has incoming edge of color $$$i$$$, then $$$i$$$-th bit has to be $$$1$$$.

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

    I was thinking about this problem for some time and once I rephrased the condition in the following way, it took me zero seconds to complete the solution. Condition means that set of colors ingoing to vertex must be disjoint from set of colors outgoing from vertex, so we can think one is the complement of the other and choose appropriate subsets. Easy to verify we can put all of them to be different 7-elements subsets.

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

      Nice! I think you might be underestimating the difficulty after looking at the inset and outset. We thought of that as well for a while but nothing clicked. I guess it might be one of those problems that is hard for me to visualize in my head.

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

        In hindsight, you're right. This solution might be broken down into these two pieces and it is indeed true that rephrasing that condition took me something like 20 minutes and then it was immediate to me, but in hindsight this sounds weird, first part is kind of obvious and natural and second one is kinda tricky, I can't really explain why did it go like this for me :P.

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

    G is also similar (or same) to this USA TST problem.

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

      I'd go with similar; dividing vertices into two halves is a much simpler idea than taking 14-bit hashes with popcount 7. (In fact, I tried the dividing idea for much of the contest, but it is not good enough here as it uses too many colors.)

»
5 years ago, # |
  Vote: I like it +49 Vote: I do not like it

I feel like B and G were the hardest problems of the contest. How to solve B?

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

    I tried to greedly put '(' while there was still a solution.

    If there is a solution it means that emptypref[i] + sumpref[i] >= 0 and emptysuf[i] - sumpref[i] >= 0 for all i from 1 to 2n.

    sumpref[i] = sum in range[1,i] if we denote '(' as 1 and ')' as -1 from the parenthese sthat we already greedly put.

    emptypref[i] = how many positions in which we can still put parentheses in range [1,i]

    emptysuf[i] = the same for suffixes

    I kept two segment trees where I could update a range and query min on intervals one for preffix and one for suffix. If the min of one the segment tree was < 0. Than I try to use a ')'. If that's still not good, then there is no solution.

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

      Our team had the same solution, however, the realization is a bit simpler in my opinion. You need just one segment tree.

      Can someone proof the correctness of this idea, because we didn't try during the contest, just submit xD

      code

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

    I think I have a simpler solution other than the one in the editorial. First of all make the first distinct $$$N / 2$$$ integers open brackets and the rest closed.

    Now iterate over the current string and add $$$+1$$$ if you face an open bracket and $$$-1$$$ if you face a closed one once the value becomes less than $$$0$$$ at index $$$i$$$ it seems optimal that you need to replace one of the open values with second occurrence $$$> i$$$ with one closed with second occurrence $$$\leq i$$$ this way you can add $$$2$$$ to your current value. it seemed optimal to me that you need to replace the open value with largest first occurrence and closed value with smallest first occurrence. I only used some sets to make this solution pass.

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

      I've came up with exactly the same solution during the contest, but discarded it, because when you flip 2 pairs of brackets, you decrease balance on some segment that you already passed by 2 and it may make it negative. Why won't it happen?

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

        Also, when I asked for solution I expected something with proof. And none of the solutions I've seen so far are proven, not even the one in the editorial. :(

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

        It will happen actually so after reconstructing the string you need to make sure that the sequence is a CBS.

        Also this might not look like a proof but it made sense to me. First of all it's obvious that at index $$$i$$$ you won't replace an open value with second occurrence $$$< i$$$ since it will not add to the current value. when adding a value from closed set it's also kind of obvious that i need the smallest value with the first occurrence since the value i will remove from the open set will surely be before that so i need to focus on lexicographicality. Now the only problem is why remove an $$$x$$$ with second occurrence $$$y > i$$$ while i can remove an $$$x2$$$ with second occurrence $$$y2 > y$$$ that might help me in the future. I don't have a proof for this part but I thought that I will remove $$$x$$$ first and if i ever come to a negative value again I can then re-revert $$$x$$$ and add $$$x2$$$ if i had passed $$$x$$$'s second occurrence by that time.

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

    Proof of the solution in the editorial (obviously, not invented during the contest) (I hope it's correct):

    For simplicity, assume that ( is equivalent to $$$+1$$$ and ) is equivalent to $$$-1$$$. Now, the following conditions are equivalent:

    1. The bracket sequence is "correct".
    2. The sum of brackets is $$$0$$$ and each suffix is non-positive.

    Take an optimal solution $$$s$$$ and assume that the greedy solution identified $$$s_i$$$ incorrectly. Of course, $$$s_i =\, ')'$$$ and greedy must have chosen (. We'll construct a new correct bracket sequence $$$s'$$$ with the same prefix and $$$s'_i =\, '('$$$.

    Assume $$$s_i$$$ is paired with $$$s_j$$$. Obviously, $$$i < j$$$. Just after greedy decided that it wants to put at ( at the $$$i$$$-th and $$$j$$$-th position, only the pairs of brackets $$$(s_a, s_b)$$$ where $$$i < a < b$$$ are undecided yet. Consider all such pairs where the optimal solution puts (. There are two cases now:

    • There is an opening pair of brackets in the optimal solution: $$$(s_a, s_b)$$$, $$$i < a < b$$$, where $$$b > j$$$. Take any such pair and replace $$$s_a, s_b$$$ with ), and replace $$$s_i, s_j$$$ with (. The sum of brackets didn't change, and no suffix sum increased (because $$$a > i$$$, $$$b > j$$$). We just found a better correct bracket sequence.
    • There is no such pair. Take the opening pair of brackets $$$(s_a, s_b)$$$, $$$i < a < b$$$, with maximum $$$b$$$. (Such a pair must exist or else $$$s$$$ would contain fewer opening brackets than we put in the greedy solution so far.) Notice that $$$i < a < b < j$$$. Again, replace $$$s_a, s_b$$$ with ), and replace $$$s_i, s_j$$$ with (. Now each suffix is still non-negative:
      • suffix sums $$$[p, 2n]$$$ for $$$p \leq b$$$ or $$$p > j$$$ decreased or remained the same,
      • suffix sums $$$[p, 2n]$$$ for $$$p \in (b, j]$$$ increased by $$$1$$$, but are still non-positive (as these are exactly the suffix sums kept in the structure when the greedy decided to put ) at the $$$i$$$-th and $$$j$$$-th position).

    In both cases we managed to put ( at $$$s_i$$$ and $$$s_j$$$, so the greedy was actually right to put it there.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve A?

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

    We can define the number of moves a position can give to Alice / Bob: He/she can either move it to another node it owns, either move it to one of the opponent's nodes. However, neither Alice nor Bob will ever move a token to a node of the other color if the other one can move it afterwards (Alice won't move from a to b if Bob can move it after from b to c). This is because it would mean basically spending a move to give the other one at least one move.

    So we can define liberty[x] = number of moves from x without giving the opponent the chance to move it.

    Now we just have to use the knapsack problem to find a positive difference between the number of moves of Alice and of Bob.

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

      If both have the same number of moves(liberty) who wins? it depends on the next parts of path.

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

        If both have same liberty then the first to move (Alice) loses, since she will run out of moves in her own color and be forced to move tokens into nodes of the other color, giving Bob more moves.

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

          consider paths are like this:

          WWBWW

          BBWWW

          now the Alice wins!

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

            Liberty counts the number max number of W(or B) -1 in a path without BB(or WW). The path can be something like WWBWWBWBWBW...

            The -1 removes the last move to the BB/WW.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Is it possible to practice the problems after the contest? actually I forgot about it. Though joined half an hour before ending and solved one. I want to practice the rest problems! Is it possible?

»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

How to solve C?

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

    C is a linear programming problem. If you write down dual program, you will need to find $$$y_1, y_2, ..., y_n \geq 0$$$, such that $$$\sum a_i y_i$$$ is minimized and $$$y_i + y_{i+1} \geq 1$$$. There are 2 cases: each $$$y_i = 0.5$$$(this can only happen for odd $$$n$$$), and each $$$y_i$$$ is either $$$0$$$ or $$$1$$$. I don't have strict proof, but the intuition is that it's similar to linear program for max weight matching, so it behaves similarly. The case with $$$y_i = 0, 1$$$ is solved with dynamic programming $$$dp[i][y_0][y_i]$$$.

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

      Proof: There are $$$2n$$$ equations in the LP, $$$y_i + y_{i + 1} \geq 1, y_i \geq 0$$$ for all $$$i$$$.

      Since the feasible region is bounded, there must be an optimal extreme point solution, where $$$n$$$ linearly independent equations are satisfied.

      If none of these satisfied equations is of the form $$$y_j = 0$$$, then $$$y_i + y_{i+1} = 1$$$ must be true for all $$$i$$$. So the values must be of the form alternating $$$x, 1-x$$$. If $$$n$$$ is odd, the only possible solution is $$$\frac{1}{2}$$$. Else the objective function is (1-x) * (sum at even positions) + x * (sum at odd positions) which is minimized at either $$$0$$$ or $$$1$$$.

      Else, if $$$y_i = 0$$$, then $$$y_{i-1}$$$ and $$$y_{i+1}$$$ must be $$$1$$$. So, first remove all edges with values known to be alternating $$$0, 1$$$. Now we are left with line segments with no constraints on the sum of ends.

      Now, the LP for a line segment can be proved to have an integral optimum solution. Basically, in an extreme point solution, for atleast one edge, $$$y_i = 0$$$ must be satisfied (as we have $$$2n - 1$$$ inequations in the LP now). So, we use induction after removing this edge and its adjacent edges(with value $$$1$$$).

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

    After dualizing the linear program, you get that you need to minimize sum of $$$s_i y_i$$$ such that $$$y_i \geq 0$$$ and $$$y_i + y_{i+1} \geq 1$$$. Turns out that the solution is to either put $$$y_i = 0.5$$$ for all $$$i$$$ or $$$y_i \in { 0, 1 }$$$. We have a rough idea why that is, but we didn’t formally prove during the contest. To optimize the second case, you just do a simple dynamic programming that remembers whether or not the first and the last elements have value $$$1$$$.

    Edit: basically, what aid said above.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve F?

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

    We sorted the edges decreasingly by c. Each edge now connects two components. At this point, you should greedily alternate between these two components as much as possible. After you do that, you recurse into the larger of the two subtrees, delete the rest, and re-iterate the process for the edges in that larger component (where you have some nodes that are already connected, for which you keep a "lazy" value). You can do this whole process in O(n) (after sorting) if you compute the smaller of the two components by doing parallel bfs from both ends of the edge.

    I think our solution works for arbitrary weights. Not sure why the weights were powers of two.

    https://pastebin.com/SGcT5CJ3 (code might explain better)

    Easier solutions may exist. I am interested in them.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve J(div C+D)? i tried to do something with lca ans set with tin[v] comparator but it didnt work https://pastebin.com/u40S9zmM

»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it
#define int __int128_t

to the rescue in the last minute in E and it worked xD

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve I? I tried to use network flow with O(nlog) edges, there are some edges with capacity = 1, but get TLE on test 5.

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

    Model solution finds a lexicographically smallest maximum matching (smallest w.r.t query insertion time) in $$$O(n \log^2 n)$$$, using some divide and conquer based on Konig's theorem.

    How to solve if network flow can be computed in linear time (assuming all capacity 1 or infinity)?

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

      The naive method with network flow is to add edge and run flow again for each day? But I think we don't need to run flow for each day, just need to run for the last day. We will find augmenting path in order of edges added to flow network, which is order of days. So we will move back from last day to first day and decrease the answer when there is an respective augmenting path.

      P.S: I'm not sure about the correctness of this solution. I just feel that it may be true. My code that gets TLE is here. Can anyone please confirm its correctness? Some testcases that make my code WA would be great. Thanks in advance.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

D, anybody?

»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

( div c/d )H:How to arrange integer. How to solve it? I added directed edge from a to b if a divides b then answered number of strongly connected components but got WA.

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

    It was pointed out by my teammate shiv1470 that for a case like:

    2
    1 2
    2 1
    

    The answer was 2 rather than 1, as we can number node 1 as 1 and node 2 as -1. So, the final was to find the number of SCC, and then 2*(number of components with size > 1) + (number of components with size = 1).

»
5 years ago, # |
Rev. 3   Vote: I like it +172 Vote: I do not like it

Thank you all for participating! All problems in Div A/B were created and prepared by me, with a huge help of testers ko_osaga, caoash, jqdai0815, Endagorion, rushcheyo, chenjb, ainta, xiaowuc1, Subconscious, Roundgod, Rewinding, xtqqwq, WZYYN, Rebelz, VivaciousAubergine, never_giveup, Elegia, Hazyknight, gamegame.

You can find the editorial (not the final version) here.

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

    Could you please post the editorial for Div C/D as well?

»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Is there a link which can be publicly used to upsolve the contest? The link in the blog and website is for registered participants only.