Codeforces Round #363 problems analysis

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
38:26:44
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

View all →

→ Find user

→ Recent actions

Detailed →

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 of Codeforces Round 363 (Div. 1)

Tutorial of Codeforces Round 363 (Div. 2)

GlebsHP
8 years ago
101

Comments (74)

Show archived | Write comment?

Tornad0

8 years ago, # |

← Rev. 2 →

-27

You r a little bit of shit

→ Reply

DonMichaelCorleone

8 years ago, # ^ |

Be a person who first solves.

→ Reply

fresher96

8 years ago, # ^ |

wrong site buddy. this is not facebook!

→ Reply

hnust_xiaoluoluo

8 years ago, # |

← Rev. 2 →

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

→ Reply

ffao

8 years ago, # |

+33

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 10¹² given in the problem were too much for it to handle).

→ Reply

TimonKnigge

8 years ago, # ^ |

-15

http://www.cplusplus.com/reference/ctime/tm/

→ Reply

Shik

8 years ago, # ^ |

+13

It looks like the g++ used in Codeforces is 32-bit, so time_t is a 32-bit integer which cannot store 10¹² :(

Why not support 64-bit compiler Q_Q?

→ Reply

hsyue

8 years ago, # |

← Rev. 2 →

-9

....

→ Reply

hsyue

8 years ago, # ^ |

← Rev. 2 →

-9

.....

→ Reply

hnust_xiaoluoluo

8 years ago, # ^ |

my code was accepted,but the B 2 2 .* *. is YES 1 1

→ Reply

TsReaper

8 years ago, # ^ |

+18

You can place the bomb on a '.', so (1, 1) is also a correct answer.

→ Reply

KADR

8 years ago, # |

+35

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 10¹⁰⁰ 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(mask₁) + f(mask₂) + ... for all mask_i which have less than k bits equal to 1.

→ Reply

Swistakk

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

KADR

8 years ago, # ^ |

Btw aren't B coefficients always 0?

Shit. I knew it should be less complicated :)

→ Reply

Tornad0

8 years ago, # ^ |

I still don't understand:D

→ Reply

NotImplemented

8 years ago, # ^ |

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

→ Reply

skavurskaa

8 years ago, # |

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

Aemon

8 years ago, # ^ |

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

→ Reply

haleyk100198

8 years ago, # |

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

skavurskaa

8 years ago, # ^ |

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

haleyk100198

8 years ago, # ^ |

← Rev. 2 →

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://codeforces.net/contest/699/submission/19267737

→ Reply

skavurskaa

8 years ago, # ^ |

← Rev. 2 →

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

haleyk100198

8 years ago, # ^ |

← Rev. 2 →

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

emm

8 years ago, # |

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

→ Reply

haleyk100198

8 years ago, # ^ |

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://codeforces.net/contest/699/submission/19267737

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

→ Reply

emm

8 years ago, # ^ |

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

→ Reply

abdullah_alperen

8 years ago, # ^ |

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

contest_dhuye_pani_khai

8 years ago, # ^ |

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

yuizy

8 years ago, # ^ |

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

arasmus

7 years ago, # ^ |

hi..any hints on how to solve div1d

→ Reply

pranjal.ssh

8 years ago, # |

← Rev. 2 →

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

rhezo

8 years ago, # ^ |

Can you give a detailed explanation please?

→ Reply

pranjal.ssh

8 years ago, # ^ |

+28

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

jtnydv25

8 years ago, # ^ |

My solution was exactly the same.

→ Reply

alibaba

8 years ago, # ^ |

← Rev. 2 →

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

TouchMe

8 years ago, # |

← Rev. 3 →

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

Reference

8 years ago, # |

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

→ Reply

TsReaper

8 years ago, # |

+16

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

haleyk100198

8 years ago, # ^ |

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

TsReaper

8 years ago, # ^ |

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

haleyk100198

8 years ago, # ^ |

← Rev. 2 →

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

P_Nyagolov

8 years ago, # ^ |

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

→ Reply

haleyk100198

8 years ago, # ^ |

← Rev. 5 →

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

ffao

8 years ago, # ^ |

← Rev. 2 →

+16

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

P_Nyagolov

8 years ago, # ^ |

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

Tiny

8 years ago, # |

← Rev. 2 →

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://codeforces.net/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

TaTaPiH

8 years ago, # |

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

→ Reply

GlebsHP

8 years ago, # ^ |

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

→ Reply

TaTaPiH

8 years ago, # ^ |

got it, спасибо)

→ Reply

solution_hacker

8 years ago, # |

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

haleyk100198

8 years ago, # ^ |

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

→ Reply

solution_hacker

8 years ago, # ^ |

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

haleyk100198

8 years ago, # ^ |

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

dcshin

8 years ago, # ^ |

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

petil777

8 years ago, # |

+13

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

riadwaw

8 years ago, # ^ |

+16

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

tweety

8 years ago, # ^ |

+13

2) for large tests you can send generators.

Example generator I hacked with

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << 200000 << endl;
    for (int i = 0; i < 200000; i++) {
        cout << 'R';
    }
    cout << endl;
    for (int i = 0; i < 200000; i++) {
        if (i) cout << " ";
        cout << i * 2;
    }
    cout << endl;
}

→ Reply

petil777

8 years ago, # ^ |

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

→ Reply

ariel.nowik

8 years ago, # |

← Rev. 6 →

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

kalimm

8 years ago, # |

+57

F? :(

→ Reply

zscoder

8 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Kyle_Chi

8 years ago, # |

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

Kyle_Chi

8 years ago, # ^ |

got it

→ Reply

dcshin

8 years ago, # |

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,

Distribute lines from each teleportspot to other monsters. The line parameters are normalized by absolute gcd of its parameters (L = Pk X Pn).
So, a line contain one or more monster(point) within. And these monsters(points) are sorted by distance from teleport-spot.
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)
The final result is the maximum number of reachable monster among all permutation of k.

→ Reply

prateek_jhunjhunwala

8 years ago, # |

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

Errichto

8 years ago, # ^ |

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

barun511

8 years ago, # |

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

→ Reply

mochii

7 years ago, # |

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

→ Reply

Dee_code

6 years ago, # |

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

→ Reply

DysKode

6 years ago, # ^ |

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

Errichto

5 years ago, # |

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

There are $$$k$$$ places and $$$n$$$ monsters. For each of $$$k$$$ places let's sort monsters by angle. Thanks to that, for each pair (place, monster) we will be able to know which monsters don't allow us do directly hit this monster from this place.

Let's iterate over monsters and for each of them independently check if it can be hit. We want to get the complexity $$$O(n \cdot k!)$$$ or $$$O(n \cdot k! \cdot \log n)$$$.

We fixed a monster $$$m$$$. We want it to be hit in some moment. So, let's iterate over places — considering which place will eventually hit a monster $$$m$$$.

We fixed a place which will hit $$$m$$$. Thanks to the preprocessing (sorting by angle at the beginning), we are able to check if the fixed place can directly hit $$$m$$$. While we can't hit directly we find any blocking monster (it may be e.g. the first monster in this direction, looking from the fixed place). Let's call it $$$m2$$$. If we want to succeed then some place must hit $$$m2$$$.

Iterate over which place will hit $$$m2$$$. Again, check if it can directly hit now. If yes then mark this place as used and $$$m2$$$ as killed (and go back to checking $$$m$$$, but with monster $$$m2$$$ killed and thus not blocking us anymore). Otherwise, find any monster in this direction and again, iterate over a place to hit it in the future.

While checking if a monster may be directly hit by some place, remember that some monsters may be already killed and thus they don't block anything.

The above should give you the rough understanding of the solution. Let's talk about the details and the implementation.

Iterate over a monster to check and over $$$k!$$$ permutations of places. Create a recursive function rec(int monster_to_kill, list<int> & permutation). Take the first place from the list and remove it for ever from the list. This will be a place to eventually kill monster_to_kill, maybe not now. While there are any alive monsters between the fixed place and monster_to_kill , choose any of those alive monsters and run rec(that_monster, &permutation).

Don't treat permutation as the order of teleportation stones to use. It's only the order in which we take them from some stack/list. It only allows us to nicely simulate iterating over a place from which we want to get rid of some blocking monster.

Some words about the correctness. Is it possible that the described solution isn't able to find a way to kill a monster while there exists a way? In such a way there is some place from which Limak will hit the monster. We simulated iterating over such a place. We can't hit directly at the beginning only if there are some blocking monsters between the place and the monster. Each of them must be hit from some place. We don't assume anything about the order of monsters or about the order of places from which we hit. In the "optimal" way, every monster initially blocking us must be hit in some moment by some place so we can (and must) iterate over a place from which it will be hit. If there are some new blocking monsters then again — in the "optimal" way some place hits it and we iterate over it.

→ Reply