GlebsHP's blog

Codeforces Round #363 problems analysis
By GlebsHP, history, 8 years ago, In English

New problems will be added as soon as the analysis is ready.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +64
  • Vote: I do not like it

Comments Comments (74)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it

You r a little bit of shit

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

The first test data of B is too weak......

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

Does C++ really have builtin tools to work with dates? As far as I know, it could only deal with timestamps (which might only store 32 bits, so the timestamps of 1012 given in the problem were too much for it to handle).

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

....

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

For problem C I didn't realize that we can look at this process backwards so instead I came up with a bit different solution.

Let's fix a number i and find the probability of it being in the final set after 10100 iterations. Let f(steps, mask) be the probability that after steps steps all numbers described by mask are located before element i in the list and the rest of the numbers are after it (here we ignore k and just assume that we're maintaining a list of all elements sorted by the time of their latest lookup). This thing describes a Markov chain and we're interesting in finding its stable state (i.e. such values of f() that f(step, mask) = f(step + 1, mask) = f(mask)).

Now, if we write down the equations for f(mask) where mask > 0, we can see that f(mask) depends only on f(mask') where mask' ≤ mask and there are at most n different values mask'. Instead of writing down the equation for f(0) we can use another equation that f(0) + f(1) + ... = 1 (the system has n variables and n + 1 equations so we can just discard the equation for f(0)).

In order to solve this system, let's assume that f(0) = X and for every f(mask) we'll compute the probability in the form of f(mask) = A·X + B (i.e. we'll store it as a pair of (A, B)), this can be done by dp because f(mask) depends only on f(mask') for mask' ≤ mask. Now, we can use the last equation (f(0) + f(1) + ... = 1) to find X (we'll have an equation of the form A·X + B = 1 for it) which will allow us to find f(mask) for every mask. At the end, we're interested in finding f(mask1) + f(mask2) + ... for all maski which have less than k bits equal to 1.

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

    I followed very similar thought process as yours during contest :). However noting that f(0) = pi simplifies things :). Btw aren't B coefficients always 0?

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

      Btw aren't B coefficients always 0?

      Shit. I knew it should be less complicated :)

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

    The main clue I cannot get is that probability has a limit when steps -> infinity.

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

Love this kind of graph from problem D :D (i call it flower graph because the components look like flowers to me and i never knew this name functional graph)

Problems with the same kind of graph:

Joining Couples from South America ICPC 2012 : https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=4151

BFFs from Google Code Jam 2016 1A: https://code.google.com/codejam/contest/4304486/dashboard

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

    I believe they are also known as Pseudoforests, if you are interested.

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

I always get hit by TLE when dealing with bitmask dp questions, can somebody please help and point out which part did I wasted all the computing power? Thanks in advance.

This time's Div2-E

A practice of 8C I have done a while ago, also a bitmask dp question

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

    If i understood your logic correctly, you are not using the memo table to avoid recalculations, you are just storing values there but still computing the same state more than once

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

      I just added a line "if(dp[prev|(1<<i)]!=0.0) continue;" Now I see what you mean, I think what I am doing is just something similar to dfs which leads me to visit the same point a few times instead of storing the value to use it later on, is it?

      I wonder if there is a way to generate bitmasks effectively, or at least "orthodoxy", now I only have an idea which uses a queue to store the possible next states of the bitmasks, somewhat similar to bfs, but this sounds cluncky and weird.

      UPD: Surprise surprise, it ended up working, thanks for pointing out my problem! :D

      http://mirror.codeforces.com/contest/699/submission/19267737

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

        Great! :)

        I don't think there is any special way. You just have to keep in mind that moving to a next state usually means setting a new bit (using bitwise OR with some power of 2). You can use some defines to create a interface, i think thats the best way to hide the bitwise operations in the code:

        #define bit(i) (1<<(i))
#define set(mask,i) (mask |= (1<<(i)))
#define get(mask,i) (mask & (1<<(i)))
        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    And another problem regarding Div2-F, I get the approach and tried to build a code for it, yet my sorting function fails to complete its' job. I suspect that it could be floating point problems, but nothing seems wrong with the angle even when checking the angle with setprecision(20)

    The code with an echo test

    I have to applaud on the great illustration of the test cases though, it helped me a lot in understanding the problem and the possible approach to solve the question. =D

    UPD: OMG my brain must be rotten during the contest... I've made a dumb mistake in the sorting function.

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

Can some one please explain the dp we have to use in Div2-E LRU.

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

    DISCLAIMER: I AM ALSO NEW TO BITMASK DP SO WHAT I AM EXPLAINING COULD POSSIBLY BE WRONG

    So, I believe that you have already understood why does the problem becomes "Choosing K items to be added at the end of the cache", so now we will need to use dp in order to find out the chances of picking up certain combination.

    In this bitmask dp, we store the states of each item: 1 representing it has been picked up and 0 as the opposite, then we combine the flags together. (That means, for n=3, if item 2 and 3 has been picked up, the flag could be 110 or 011, depending on implementation but I prefer using the rightmost bit as the first item).

    Similar to regular dp, bitmask dp also stores previously processed value for further processing to avoid reprocessing. In order to walk from state to state, we have to do some bitwise operation to set some flags active (i.e. picking up a new item). Remember to generate states efficiently and don't make the mistake I have made above.

    The answer for each item is the sum of dp[(k flags active)] which the item is also set active. At the end of the editorial it mentioned to take care of 0.0 probability (test case 13), and the chance of having not enough k items having non-zero probability (test case 17). Take care of these cases and you are done.

    http://mirror.codeforces.com/contest/699/submission/19267737

    My AC solution, again, I am new to bitmask dp so my implementation might be considered as unorthodox.

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

      I know what bitmask dp is. What is the recursive equation for the dp?? dp[011] = what in terms of other dp

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

        Let me try to explain: dp[011] = dp[001]*P[1]/(P[2]+P[1]) + dp[010]*P[0]/(P[2]+P[0]) where P[0] is the possibility of the first video, P[1] is the possibility of the second video and P[2] is the possibility of the last one. Note that the most significant bit is responsible for the last video, shows whether it is in the cache or not and the least significant bit is responsible for the first video similarly. If you still have any questions, please feel free to ask.

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

          I have a confusion. Isn't dp[011] also not dependent on dp[101]? you have 3rd and 1st video in the cache and then 3rd video is removed by the second video if second one is called? I am sorry I know I probably dont understand the state transitions clearly. Could you clear that up for me?

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

            We are looking at the problem from the other end. Instead of finding out which videos are in the cache at the end, we start filling an initially empty cache with new videos until it's full.

            This way there's no removals since we stop processing once the cache is full.

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

      hi..any hints on how to solve div1d

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

Div1 C can also be solved by inclusion exclusion. We brute force for last occurrence of a[i] and then choose a mask of numbers which will appear on its right. This leads to a GP which can be trivially summed. We can use inclusion exclusion to remove overcounting. See my implemention for details

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

    Can you give a detailed explanation please?

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

      For each a[i], we repeat this algo :

      We brute force for its last occurrence, then to its right can be some no more than K-1 distinct numbers. So consider this formula for a particular mask of numbers which will appear on right(number of set bits must be <= K-1) : x ^ j ,

      where x = sum of a[i] in mask and j = number of positions available to the right of a[i]. This means any of numbers in mask can appear to its right

      We have to sum this for all j. It will be 1/(1-x).

      If you consider only those masks where number of set bits are K-1, you will cover all cases, but you will overcount(a lot). For that you have to subtract answers for those masks where set bits are K-2. Then again you will have to add those of K-3 etc. Note that we can't just naively keep subtracting/adding the answer for mask, we have to count exactly how many cases are being overcounted.

      Consider a general mask p : It will be already counted in all masks which are its superset. You can find the number of its supersets by an initial brute force or some combinatorics.

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

        My solution was exactly the same.

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

          Can you explain this part in your code? 


          ~~~~~
                for(int l  = 0;l+ln<n;l++)
                {
                    if(l+ln < K){
                    if(l&1)
                    {
                        ans[k] -= C[n-1-ln][l]*(sm)/(1-sm);
                    }
                    else
                    {
                        ans[k] += C[n-1-ln][l]*(sm)/(1-sm);
                    }
                }

          ~~~~~

          I cannot understand reason for multiply C[n — 1 — ln][l]

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

For div2/C, I think there's a more straightforward greedy solution.

If possible, then Vasya will not rest. So now we define pre = a[0], now = a[1],ans = 0.

Let's iterate from i = 1. if pre == 0 : Vasya will get rest, ans++. if pre == now && now != 3 : Vasya will get rest at the i day, don't forget modify a[i] to 0 after increases the ans. if now == 3 : change a[i] to 1 if pre == 2, or 2 if pre == 1. if pre == 3, doesn't matter, Vasya absolutely will not get rest at the i day

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

problem c div2 has a greedy solution also, here is my submission[submission:19270426]

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

I met a problem with Div2.E (Div1.C). When I calculate the value of dp[mask], it seems that I need to use dp[mask] itself to calculate dp[mask].

For example, if there are 4 videos and the size of the cache is 3. dp[1100] means the probability of the first and the second videos in the cache. If we choose the first video again, the mask will still be 1100. It seems to be a "self reference". How can I deal with this problem?

My English is not good. Sorry if my question is hard to understand.

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

    Since we are considering the possibility after a googol of query, we would only like to consider the last chosen k items. Choosing an item again could be considered as skipping a query, which has an insignificant effect due to we are considering a googol of query.

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

    Thanks haleyk100198 for the answer. But personally I think it's not the case.

    My solution for this problem is to solve an equation. For example, in order to calculate dp[1100] in my previous post, I will solve this equation:

    dp[1100] = _p1*dp[1100] + p2*dp[1100] + p1*dp[0100] + p2*dp[1000]

    (_p1_ means the probability the first video is chosen, p2 means the probability the second video is chosen)

    So the answer is dp[1100] = p1/(1-p1-p2)*dp[0100] + p2/(1-p1-p2)*dp[1000]

    But actually it's incorrect. The correct answer should be dp[1100] = p1/(1-p2)*dp[0100] + p2/(1-p1)*dp[1000]

    I can't understand why my solution is wrong.

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

      I understand your doubt, but the problem is about the last K distinct items chosen.

      Consider that we are trying to fill the cache with 3 items and infinite moves. For state [1100], choosing items 1,2 again doesn't mean that we have the calculate the value of [1110] and [1101] recursively due to there are (p1+p2) chance of reaching the state [1100] again. Instead, since there is infinite moves, you should consider that choosing these option 1 and 2 as invalid, because we are not going to move on to the next state until we choose something that is not chosen yet — this is why that we could completely ignore p1 and p2 in our calculation.

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

        I don't think you can ignore choices this way, you can do it only if p1+p2 is 0.

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

          Well, I don't have a strong proof for ignoring the choices, but I think that since we are getting back to the state until we have chose something different, and we have infinite moves, all the recursive calculations could be treated as p1 and p2 are not here.

          UPD: Consider sum of GS to infinity, the chances of reaching [1110] from [1100] equals to p3*p[1100]+(p1+p2)*[1100]*p3+.... = (p3*(1-(p1+p2)^inf))/(1-(p1+p2)) = p3*[1100]/(1-p1-p2). Same for any options and other states, thus p1 and p2 could be ignored here.... Maybe it's just not the word I should use. (Well unless p1+p2=1, but we had handled the case of p3=0)

          UPD2: Rethought about this... Yeah... it's my bad to use the word "ignore" here, it's kinda misleading.

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

      Your equation doesn't represent what you think it does. Given your equation, what your dp[mask] actually represents is, what is the probability that the cache will be exactly at state mask in the end of the process?

      We can see then that, because the cache will end up with K bits, the solution for all masks with less than k bits set is dp [mask]=0, and then we don't have enough equations to deduce dp [mask] for masks with K bits.

      The dp we actually want is, "what is the probability that, at some point in time, the cache equals mask?" which has a different and not self-referential equation, already explained.

      (The probability you move from mask1 to mask2, picking j, is P (mask1, j)= pj + sum of ps in mask1 * P (mask1,j), solving we get P (mask1,j) = pj / (1-sum of ps in mask1)).

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

    Let's say that mask has t set bits — (V1, V2, ..., Vt). Now let's fix the next query, denote its index with F. Now we need to add dp[mask|(1<<F)]*p[F] to the answer. We will keep a variable S (comes from Sum).

    So if F is not among those V1,V2,...,Vt, then let's add dp[mask|(1<<F)]*p[F] to S. If F is V1, we need to add dp[mask]*p[V1] to the answer. If F is V2, we need to add dp[mask]*p[V2] to the answer. And so on, if F is Vt, we need to add dp[mask]*p[Vt] to the answer. Or in total, if F is among V1,V2,...,Vt, we add dp[mask]*(p[V1]+p[V2]+...+p[Vt]) to the answer.

    To sum up, we have dp[mask]=S+dp[mask]*(p[V1]+p[V2]+...+p[Vt]). Well everything is simple now because we know S, we know p[V1]+p[V2]+...+p[Vt] and we need to find dp[mask].

    S=dp[mask]-dp[mask]*(p[V1]+p[V2]+...+p[Vt])
    S=dp[mask]*(1-(p[V1]+p[V2]+...+p[Vt]))
    dp[mask]=S/(1-(p[V1]+p[V2]+...+p[Vt]))

    Don't forget to consider the case when p[V1]+p[V2]+...+p[Vt]=1 because you will have division by zero :)

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

I have a question about my solution to div2 E. See #65 and #36, n is the same and #36 contain many 0 probabilities, but my solution do about the same amount of operations for both, however, #36 costs much more time than #65. It seems that time cost of mul/div operations on double type depends on the values. so strange.

http://mirror.codeforces.com/contest/699/submission/19276677

UPDATE： change dp[l | (1 << i)] += dp[l] * p[i] / sum; to if (sum > ERROR) { dp[l | (1 << i)] += dp[l] * p[i] / sum; } and the time is ok, seems that division by 0 on double doesn't cause runtime error but costs more time.

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

- Problem D__ - I don't understand what if there's no cycles in given graph?

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

    It is impossible. The graph containing n vertices and n edges must have at least one cycle.

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

In Div2-E, why is f(mask) divided by (1-sum of probabilities of all videos whose bit is set in mask)? I mean it should just be sum of p[i]*f(mask^(1<<i)].

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

    Check out my comment above, the formula can be proved by sum of GS.

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

      I doesn't understand your comment. We need ith video to be one of the last k different videos. So it doesn't matter what videos are being requested for in previous requests. So we can multiply 1 for those videos. Why are you summing on how many times no. of videos not in mask are requested? f(mask) = probablilty of bits set in mask to be in cache. f(011) should be equal to p[1]*f(010)+p[2]*f(001) but why its equal to (p[1]*f(010)+p[2]*f(001))/p[3]

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

        Choosing videos that are requested before DOES matter.

        Again, I am going to try to explain the idea with "filling the cache". This is what we are considering:

        [blah blah blah 123212] + [k distinct items] (a total length of one googol)

        You can agree that our problem now becomes finding the chances of each latter sequence appearing regardless of its' length, and sum the probability to the chance to the corresponding flags, right? Great.

        So since we are counting the probabilities regardless of the sequence's length, choosing an item repeatedly effectively increases the length of the sequence by one, and it should be considered as a different sequence. This is why we have to consider choosing it repeatedly, and the probability of moving from state [mask] to [mask|(1<<i)] equals to p(i) * [mask] + p(sum of chosen items) * p(i) * [mask] + ... , which can represented as a sum of Geometric Sequence to infinity.

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

          Thanks for the great explanation for the problem.

          However, I have difficulty in understanding because I think below formula can hurt final precision. Could you please correct me if I'm thinking wrong?

          • sum of all possibilities of choosing previously chosen items in mask equals to infinity power of "probability sum of chosen items"

          For example, if we consider 2 chosen items, I can find the probability of choosing 2 times sequencially(p1*p2) in square of their sum. However, it is (2*p1*p2) which is more than what if we calculate correctly.

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

This division was the first I participated in officially. After I tried to hack someone's code, I have two questions.

I saw that someone used lower_bound, which can trigger runtime error.And I copied it and figured out some data which can make runtime error in visual studio. So I tried to hack by using that data. But after hack, it didn't lead to error and output normally. Why this situation happenend? Can't we hack runtime error code? Secondly, when I tried to hack Div2-A for O(n^2) code, I couldn't hack because of limitation of text file size. Then, can't we hack TLE code which needs a big data?

Anyway, it was good experience and specially thanks for hacker who hacked me :). It helped me be the "BLUE" for my first trial.

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

    2) You may use generator — program that prints test to stdout 1) Yes, you can, but you should understand that usually runtime is not guaranteed and it's actually UB that may work and return right answer

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

    2) for large tests you can send generators.

    Example generator I hacked with
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, I didn't know that. Thanks for great tips!

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

I felt the a standard solution for B where you would sum walls per column and row was too tricky with corner cases. I made another solution. The idea is too add the walls one per one while we design the solution filtering the reliable coordinates (x, y) to put the bomb. We will define a queue of coordinates (x, y) . This queue contains all possibilities for the bomb in a particular moment. But, there are cases where there this queue may be too big. For example at the beginning (with no wall processed) all places could be used thus the size of the queue would be (N*M). So, to simplify the solution, we'll say x =  - 1 or y =  - 1, two values out of range, if any place could be used in that stored chance as x or y. We start with only one value on queue, (-1,-1), cause at the beginning any place is reliable, and then we process for each wall, each bomb possibility to be reliable with this wall.

  • If X =  - 1, then we add to the new queue (W.x, Y) as the possibility must be modified as now with this chance, X value is fixed, not variable.
  • If Y =  - 1, then we add to the new queue (X, W.y)
  • If X = W.x or Y = W.y then we can add the same possibility to the new queue, as the bomb possibility won't be changed by the wall.

We destroy the old queue and replace it with the new queue for the next wall processing. In the end we will get a queue with all the possible coordinates for the bomb.

The total complexity is O(N * M * J) where J is the time to process the queue in wall processing. I feel it is not very big as the possibilities filter very fast by my intuition. If you want you can do the analysis of J complexity.

The nice thing of this algorithm it is that is so general that we can avoid to analyse the tricky cases :) Code: 19309915

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

F? :(

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

    After so many days F is still not out. (and the problem seems interesting O_O)

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

Well,I am confused about LRU. I don't understand what is the exact meaning of dp[mask]. My confusion is:after a long time(10^100) in this problem,the probability of all mask(or status) will converge to a fix number.However,when considering the limit of probability of status less than k bits,the probability must be 0(unless n<k),for example,assume a final status having m(m<k) bits,then each time the new choice must be within these m bits,then the probability is less than (m/n)^infinity,which is obviously 0. So,if we use dp[mask] to calculate dp[mask|(1<<i)]... ,it will be 0 forever. I am sure I misunderstood the exact meaning of dp[mask]. Can anyone explain it in details?

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

Could anyone please help me to solve div2.F? my_submission

I couldn't figure out why my simple solution doesn't pass for TC#7.

Here's my approach,

  1. Distribute lines from each teleportspot to other monsters. The line parameters are normalized by absolute gcd of its parameters (L = Pk X Pn).

  2. So, a line contain one or more monster(point) within. And these monsters(points) are sorted by distance from teleport-spot.

  3. Search for all permutation of k(by dfs) and check every line within the teleport-spot and take maximum one monster for a line at front. If the front monster can reachable from the other teleport-spot visited before, then ignore them)

  4. The final result is the maximum number of reachable monster among all permutation of k.

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

In Div 2D (or Div 1B) is the graph directed or undirected? Or does it not matter which way we assume it to be? Because if it is undirected then there can be multiple edges between a pair of vertices.How to solve the problem then?

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

    Both interpretations are fine. Choose the one you understand better. If it's undirected, two edges between a pair of vertices form a cycle of size 2.

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

I don't understand why 21387180 is failing :( Can anybody help?

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

Sorry for necroposting this, but where's the editorial of Div2F ? How to solve Div2F ?

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

hey can someone explain me the Div2 C problem ?... thanks in advance ....

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

    My submission I think the code is pretty self explained, but i will also add here my idea

    What to do in each day: 0 — just rest 1 — if you participated in a contest last day, is a free day, otherwise mark that today you participated 2 — if you went to the gym last day, is a free day, otherwise mark that today you went to the gym 3 — if last day you participated in a contest, today you will go to the gym; if last day you went to the gym then you will code; if you did nothing last day you can do both, but we can mark this as doing nothing without counting it as a free day

    days 0 1 2 are pretty clear, but the last case of the day 3 maybe needs to be explained more, consider we have: 3 1 — we will consider first day as a 2 day 3 1 — we will consider first day as a 1 day 3 3 1 — we will consider first day a 1 day, second day a 2 day 3 3 3 1 — we will consider first day a 2 day, second day a 1 day, third day a 2 day

    but we will do something regardless of what day will be tomorrow

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

I actually wrote the editorial for 698D - Limak and Shooting Points three years ago in Polygon but it still isn't updated in this blog. Let me paste it:

Spoiler
→ Reply
»
5 years ago, # |
← Rev. 9   Vote: I like it 0 Vote: I do not like it

Sorry for touching this old post.

I wrote a recursive DP approach for this problem similar to the editorial.

the submission https://mirror.codeforces.com/contest/699/submission/74297232

If someone could help me shorten down my code.

I looked for a bit but couldn't find any recursive solutions amongst people's submissions as I wanted to write it shorter.

(If anybody has some good coders who write recursive dp solutions please mention them. I would like to add them to my friends)

E-for consecutive days storage for sports, F-for contests I have used 0 for rest, 1 for sports and 2 for contests

→ Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why no solution of 698F?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

[problem:C] in test case 5 why answer in this case is 8, in think its just 7

10 0 0 1 1 0 0 0 0 1 0

Participant's output 7

Jury's answer 8

Checker comment wrong answer expected '8', found '7'

→ Reply