Aksenov239's blog

By Aksenov239, history, 2 years ago, In English

Hello, everybody!

We would like to invite you to participate in the Mirror of The ICPC World Finals Moscow Invitational Contest. The original contest was made for the teams who cannot come to The World Finals in Moscow. They were competing for the medals and glory. The Invitational contest has already passed and the results will be revealed on October 5th.

The mirror contest will be held by almost standard ICPC rules with 10 to 14 problems. The difference from the traditional ICPC format is that your team can use three computers instead of one. The problems are expected to be of The World Finals difficulty. Also, the round will be unrated!

The problemset was prepared by NERC Jury Team with the help of many other people. The chief judge is Roman elizarov Elizarov. The jury members are Pavel PavelKunyavskiy Kunyavskiy, Georgy kgeorgiy Korneev, Evgeny eatmore Kapun, Ilya izban Zban, Niyaz niyaznigmatul Nigmatullin, Vasiliy SirShokoladina Mokin, Daniil danilka.pro Sagunov, Gennady tourist Korotkevich, Oleg snarknews Hristenko, Egor Egor Kulikov, Borys qwerty787788 Minaev, Pavel pashka Mavrin, Mike MikeMirzayanov Mirzayanov, Anton Paramonov, Bruce bmerry Merry, Zachary Friggstad Friggstad, Jakub Wojtaszczyk, David Van Brackle, and myself. (I hope I haven't missed somebody. :P)

I hope you will like the contest! Good luck and have fun!

UPD: The editorial is available here.

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

| Write comment?
»
2 years ago, # |
  Vote: I like it -81 Vote: I do not like it

Will we get certificate of participation???

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

    In the mirror you will not recieve any certificates, unfortunately.

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

For the first time ICPC WF problems will get CF ratings (in problem-set page).

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

    Which will probably be broken anyway, as the problem X-rated guy can solve in 5 hours is a bit harder than a problem X-rated guy can solve in 2...

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

      Most contestants participate in teams, which increases their rating by 100-200, which more or less takes care of the fact you pointed out. But for solo participants, it won't reflect that, it's true.

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

Problems are cool, recommend to participate, but if you are not div1, it will be too hard and sad for you.

»
2 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Can anyone tell the maximum team size please? Thanks ;_;

»
2 years ago, # |
  Vote: I like it +17 Vote: I do not like it
what does it mean?
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    I think Codeforces can find(guess) that they are dangerous teams.

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

      i.e. cheaters? I checked one team, no cheaters are there

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

    I think it means that someone of that team is already in another team

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

Anyone wants to team up with me ?

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

Where can I find the live leaderboard of ICPC WF?

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

How to solve L ?

  • »
    »
    2 years ago, # ^ |
    Rev. 5   Vote: I like it +58 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 3
    Hint 4
    Our Solution
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Here is a very overcomplicated (I have no idea if this indeed is the solution) and ugly (we managed to fit this in 1880ms) idea.

    We use binary search for the answer. For each $$$W$$$, we check if $$$W$$$ can be the width when we finish the run (hence answer will be $$$W - \sum c_i$$$)

    To check for each $$$W$$$, we use union-find and check the nodes in reverse order. We start with $$$W$$$, and subtract weight every time we eat candy. When we eat sufficiently many candies, width is reduced enough and new edges are now open (thus UF works).

    Although we don't know where to start (i.e, in the original problem, where to end), we can check as "if we started at $$$x$$$, can we reach $$$y$$$" with UF.

    To do this, we maintain for each component of UF, set of next-extendable vertices. When we eat a candy, we have information in the form of "by taking this component as a whole, we can decrease our width by $$$x$$$" and for all extendable vertices from this component, we can merge those vertices with current component, increasing $$$x$$$ and possibly opening new edges.

    When merging, this 'set of next extendable vertices' should also be merged. Here we use small-to-large trick. Also the set can be maintained as priority queues.

    Summary : Binary search with (DSU + priority queue extendable vertices + small to large). Time complexity is $$$O(n \alpha(n) \log^2 n \log 10^{9})$$$ which looks horrendous.

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

      This idea can be implemented without binary searching for the answer: at every step of your DSU process, just pick the edge that allows for the greatest initial width. Then, the minimum of these allowed initial widths is the final answer. This leads to an $$$\mathcal{O}(n \log^2 n)$$$ solution; my code passes in about 200ms.

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

        Wow. Why weren't we able to think this in contest... This now makes a lot more sense. Thanks.

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

        Why log^2? Isn't it just single log?

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

          In the worst case, my solution performs $$$\mathcal{O}(N \log N)$$$ priority queue insertions, leading to a second log factor.

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

        Excuse me, can I have a look at the code

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

      Thanks!

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

Will you make others' solutions visible?

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

Where can I upsolve the problems?

Also, Is this the intended solution in M? (It passed)

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

    In fact, only output 0 and 1 is enough to pass M. XD

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

      How to find the proper 01 string ?

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

        I have used evolutionary algorithms and I got 86%:

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

          these are the bins of some solutions:

          1. 4 9 14 19 29
          2. 4 9 15 21 31
          3. 3 7 12 19 31
          4. 4 8 13 21 32
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve H ?

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

    Pair up brackets using a stack and build such tree:

    Spoiler

    Note: 0 is root there.

    How can it be done? When you meet '(', add its ID to stack, When you meet ')' pop the top of the stack and add this ID to its parent. When you meet '-' just ignore it and the next character.

    Now let's write recursive function int get_order(int ID). It works lazily. If order is already computed return it. Otherwise if there are no children of this vertex then the order is $$$0$$$. Otherwise let's merge all the children into parent's order.

    The answer is get_order(0).

    Code: 130485662

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

Will there are be a mirror of the ICPC WF on the 5th of October?

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

How to solve B ?

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

    Assume the ranges are $$$[l_i,r_i]$$$ where $$$l_i < r_i$$$. You can show that $$$[l_j,r_j]$$$ intersects this if ( $$$l_j \leq l_i$$$ and $$$l_i \leq r_j \leq r_i$$$ ) or ( $$$l_i \leq l_j \leq r_i$$$ and $$$r_i \leq r_j$$$ ).

    Now, we will draw these $$$[l_i,r_i]$$$ on the eucledian plane. We notice that those intervals that intersects $$$[l_i,r_i]$$$ actually form 2 rectangles on this plane. So we can just maintain some 2d data structure. Since one side of the rectangles extend to infinity, we can use a priority queue as one of the layers of this 2d data structure.

    code

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

When the practice submission will be allowed?

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

has someone solved L with offline queries of searching the narrowest edge on a path in mst? my approach with sqrt-decomposition is getting wa3 and I don't know whether it's bug or solution is wrong

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

It is so funny that my team's solution for K is the fastest. We just did $$$N=61$$$ maximum independent set and copied the fastest solution for MIS from yosupo's judge. Surpringly, it ACs.

code

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

How to solve G?

+Is there a scoreboard for official WF Invitational Contest?

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

    It is still frozen. It should be revealed on October 5th as far as I understand.

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

    For each subtree $$$x$$$ and for each leave $$$v$$$ in $$$x$$$, we want to compute the probability of $$$v$$$ to be the winner in that subtree.

    To do so, we simply need to merge two subtrees, which turns the problem into computing ($$$\sum_i \frac{b_i x_j}{y_i+x_j}$$$) for every $$$j$$$. For the part $$$y_i>x_j$$$, we divide the denominator and numerator both by $$$y_i$$$ (now $$$0<\frac{x_j}{y_i}<1$$$), then use the Taylor series of $$$1/(1+x)$$$ around $$$1/2$$$. For the part $$$y_i<x_j$$$, we could divide denominator and numerator both by $$$x_j$$$ and do similarly.

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

    Here is the official scoreboard :)

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

    We updated the editorial with the editorial of G.

    Thanks for participating!

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

A dragon curve related problem :PA2011 5A szl

Problem D is much easier than this PA problem. Since you only need to locate the point here. During the contest, I just found the code I wrote about 10 years ago and passed.

BTW, in this PA problem, you need to answer the number of consecutive lines in a strip. I tried hard and didn't solve it when I was young. And I didn't have another try these years, so I still don't know how to solve it yet.

If anyone knows the solution to this problem, please let me know. Thanks.

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

    I love how easily you said " I just found the code I wrote about 10 years ago and passed"

    I can't even find my code from last month.

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

Sorry to ask, but is there any access to virtual participation?

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

How to solve problem I(Interactive Rays)?

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

    First we can rotate the plane to make sure the center is above the x-axis and the circle doesn't cross the third quadrant. Next I use binary search to find two rays $$$a:(0,0)\to (x_1,y_1)$$$ and $$$b:(0,0)\to (x_2,y_2)$$$ that are almost tangential to the circle.

    Then I enumerate all possible radius $$$r$$$($$$r$$$ is an integer not greater than $$$10^5$$$ so it's ok to do so)。With the distance between $$$a$$$ and the circle (let's call it $$$d_1$$$) and it's radius $$$r$$$ we can work out the coordinate of the center $$$(x,y)$$$ (with some senior high school geometry). I also make sure that $$$(x_1,y_1)$$$ lies in the second quadrant and is as close to the circle as possible (so if the circle doesn't cross the second quadrant, what I will get is $$$x_1=-1$$$ and $$$y_1=10^5$$$). Because of the constraints above (the bolded part) we can see that $$$d_1$$$ is always useful information (which means that $$$d_1$$$ is not $$$\mathrm{distance}((x,y),(0,0))-r$$$, this infomation is useless because it's too easy to get and we can't fix $$$(x,y)$$$ simply with $$$r$$$ and $$$\mathrm{distance}((x,y),(0,0))-r$$$ : we need more infomation : $$$d_1$$$)

    picture

    After fixing $$$(x,y)$$$ we have the whole circle, so we can calculate the distance between the circle and $$$b$$$, and check whether it is equal to what the interactor outputs. If yes, then $$$(x,y,r)$$$ is the answer, otherwise go through other radii until we find out the answer.

    the code

    (I'm a Chinese student, sorry for my poor English.) I spent four hours on the problem (from 9:30 p.m. to 1:30 a.m!) so I don't have time to help my teammates lol

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

I almost solved M... I got like 99% of the way to an accepted solution... but couldn't make the final leap. I wasted 3 HOURS faffing about like an idiot.

Spoiler

I want to scream. I feel like a tremendous idiot. I think this will haunt me for the rest of my life...

»
2 years ago, # |
  Vote: I like it -18 Vote: I do not like it

Can the editorial be opened without Google?

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

How to solve A?

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

I have a question regarding the editorial for problem B.

Otherwise, we are joining two components on the same depth. Let’s say A is to the left of B (so, R(A) < L(B)). There can be at most one component between them, which is on a smaller level.

In this case, 3 and 6 have the same depth 2 but there are 2 components between them (14 and 58). Did I misunderstand something?

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

    Well, seams there is bug in editorial. I'll try to fix it later,

    In fact, In that case, we can just join both of them with parent, and it's correct (solution do like that). Probably I was thinking this parent is same for them, but than find it's wrong during stressing, but forgot about it again, when writing editorial. Anyway, it will become same at some point, and they would be merged, and total number of merges still small.

    You can check my solution for details

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

Anyone know the members of Peking University team? Peking U (Wang, Yang, Guo)

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

Can you change settings to display (failed) tests after the contest? Like in any CF round. I still can't fix my WA on test 102 in 1578I - Interactive Rays.

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

could anyone help me with problem E please, I,ve written a code but I get TLE on test 3, this is my code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int TC;
    cin>>TC;
    while(TC--){
        int h, p, rem = 0;
        long long n, ans = 0;
        cin>>h>>p;
        int i = 0;
        while(i < h){
        	n = pow(2, i);
            if(n <= p){
                ans++;
            }
            else{
                n -= rem%p;
                ans += n/p;
                rem = p - n%p;
                if(n%p) ans++;
            }
            i++;
        }
    cout<<ans<<endl;
    }
    return 0;
}

thnx in advance.

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

    First, you can replace pow(2, i) with a bitwise shift operation: 1 << i. Second, you don't have to go through each value of i. I hope this helps.

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

    use faster i/o

    code :

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

Problem E: I submitted a solution which I think shouldn't result in TLE but it is resulting. Can anyone point out possible mistake. I am failing to find any.

My solution: https://codeforces.com/contest/1578/submission/142363694

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

    use fast io and use binary exponention instead of pow

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

will the test cases be published?