DarthPrince's blog

By DarthPrince, history, 3 years ago, In English,

Div.2 A (Author: Haghani)

Idea is a simple greedy, buy needed meat for i - th day when it's cheapest among days 1, 2, ..., n.

So, the pseudo code below will work:

ans = 0
price = infinity
for i = 1 to n
      price = min(price, p[i])
      ans += price * a[i]

Time complexity:

C++ Code by amd

Python Code by Haghani

Python Code by Zlobober

Div.2 B (Author: amd)

Find all prime divisors of n. Assume they are p1, p2, ..., pk (in ). If answer is a, then we know that for each 1 ≤ i ≤ k, obviously a is not divisible by pi2 (and all greater powers of pi). So a ≤ p1 × p2 × ... × pk. And we know that p1 × p2 × ... × pk is itself lovely. So,answer is p1 × p2 × ... × pk

Time complexity:

C++ Code by amd

Python Code by Haghani

Python Code by Zlobober

A (Author: amd)

Problem is: you have to find the minimum number of k, such there is a sequence a1, a2, ..., ak with condition 2a1 + 2a2 + ... + 2ak = S = 2w1 + 2w2 + ... + 2w2. Obviously, minimum value of k is the number of set bits in binary representation of S (proof is easy, you can prove it as a practice :P).

Our only problem is how to count the number of set bits in binary representation of S? Building the binary representation of S as an array in is easy:

MAXN = 1000000 + log(1000000)
bit[0..MAXN] = {} // all equal to zero
ans = 0
for i = 1 to n
      bit[w[i]] ++ // of course after this, some bits maybe greater than 1, we'll fix them below
for i = 0 to MAXN - 1
      bit[i + 1] += bit[i]/2 // floor(bit[i]/2)
      bit[i] %= 2 // bit[i] = bit[i] modulo 2
      ans += bit[i] // if bit[i] = 0, then answer doesn't change, otherwise it'll increase by 1

Time complexity:

C++ Code by amd

C++ Code by Haghani

B (Author: amd)

If we fix x and bix mod n, then problem will be solved (because we can then multiply it by the number of valid distinct values of ).

For the problem above, let dp[i][j] be the number of valid subsequences of b where x = j and and . Of course, for every i, dp[i][1] = 1. For calculating value of dp[i][j]:

For this purpose, we can sort the array a and use two pointer:

if p0, p1, ...pn - 1 is a permutation of 0, ..., n - 1 where for each 0 ≤ t < n - 1, apt ≤ apt + 1:

for i = 0 to n-1
      dp[i][1] = 1
for j = 2 to k
      pointer = 0
      sum = 0
      for i = 0 to n-1
            while pointer < n and a[p[pointer]] <= a[i]
                  sum = (sum + dp[p[pointer ++]][j - 1]) % MOD
            dp[i][j] = sum

Now, if and x = l - 1 mod n, then answer equals to (there are c - j + 1 valid different values of for the first group and c - j for the second group).

Time complexity:

C++ Code by amd

C++ Code by Haghani

Java Code by Zlobober

C (Author: amd)

Solution is something like the fourth LCA approach discussed here.

For each 1 ≤ i ≤ n and 0 ≤ j ≤ lg(n), store the minimum 10 people in the path from city (vertex) i to its 2j - th parent in an array.

Now everything is needed is: how to merge the array of two paths? You can keep the these 10 values in the array in increasing order and for merging, use merge function which will work in . And then delete the extra values (more than 10).

And do the same as described in the article for a query (just like the preprocess part).

Time complexity:

C++ Code by amd

C++ Code by Haghani

Java Code by Zlobober

D (Author: amd)

Run binary search on the answer (t). For checking if answer is less than or equal to x (check(x)):

First of all delete all edges with destructing time greater than x. Now, if there is more than one pair of edges with the same color connected to a vertex(because we can delete at most one of them), answer is "No".

Use 2-Sat. Consider a literal for each edge e (xe). If xe = TRUE, it means it should be destructed and it shouldn't otherwise. There are some conditions:

  1. For each vertex v, if there is one (exactly one) pair of edges like i and j with the same color connected to v, then we should have the clause .

  2. For each vertex v, if the edges connected to it are e1, e2, ..., ek, we should make sure that there is no pair (i, j) where 1 ≤ i < j ≤ k and xe1 = xe2 = True. The naive approach is to add a clause for each pair. But it's not efficient.

The efficient way tho satisfy the second condition is to use prefix or: adding k new literals p1, p2, ..., pk and for each j ≤ i, make sure . To make sure about this, we can add two clauses for each pi: and (the second one is only for i > 1).

And the only thing left is to make sure (there are no two TRUE edges).

This way the number of literals and clauses are .

So, after binary search is over, we should run check(t) to get a sample matching.

Time complexity: (but slow, because of the constant factor)

C++ Code by amd

C++ Code by Haghani

Java Code by Zlobober

E (Authors: amd and Haghani)

Lemma #1: If numbers b1, b2, ..., bk are k Kheshtaks of a1, ..., an, then is a Kheshtak of a1, ..., an.

Proof: For each 1 ≤ i ≤ k, consider maski is a binary bitmask of length n and its j - th bit shows a subsequence of a1, ..., an (subset) with xor equal to bi.

So, xor of elements subsequence(subset) of a1, ..., an with bitmask equal to equals to . So, it's a Kheshtak of this sequence.

From this lemma, we can get another results: If all numbers b1, b2, ..., bk are k Kheshtaks of a1, ..., an, then every Kheshtak of b1, b2, ..., bk is a Kheshtak of a1, ..., an

Lemma #2: Score of sequence a1, a2, ..., an is equal to the score of sequence .

Proof: If we show the second sequence by b1, b2, ..., bn, then for each 1 ≤ i ≤ n:

  • bi =
  • ai =

each element from sequence b is a Kheshtak of sequence a and vise versa. So, due to the result of Lemma #1, each Kheshtak of sequence b is a Kheshtak of sequence a and vise versa. So:

  • score(b1, ..., bn) ≤ score(a1, ..., an)
  • score(a1, ..., an) ≤ score(b1, ..., bn)

score(a1, ..., an) = score(b1, ..., bn)

Back to original problem: denote another array b2, ..., bn where . Let's solve these two problems:

1- We have array a1, ..., an and q queries of two types:

  1. upd(l, r, k): Given numbers l, r and k, for each l ≤ i ≤ r, perform
  2. ask(i):  Given number i, return the value of ai.

This problem can be solved easily with a simple segment tree using lazy propagation.

2- We have array b2, ..., bn and queries of two types:

  1. modify(p, k): Perform bp = k.
  2. basis(l, r): Find and return the basis vector of bl, bl + 1, ..., br (using Gaussian Elimination, its size it at most 32).

This problem can be solved by a segment tree where in each node we have the basis of the substring of that node (node [l, r) has the basis of sequence bl, ..., br - 1).

This way we can insert to a basis vector v:

insert(x, v)
	for a in v
		if a & -a & x
			x ^= a
	if !x
		return
	for a in v
		if x & -x & a
			a ^= x
	v.push(x)

But size of v will always be less than or equal to 32. For merging two nodes (of segment tree), we can insert the elements of one in another one.

For handling queries of two types, we act like this:

Type one: Call functions: upd(l, r, k), and .

Type two: Let b = basis(l + 1, r). Call insert(al, b). And then print 2b.size() as the answer.

Time complexity: =

C++ Code by amd

C++ Code by Haghani

Java Code by Zlobober

F (Author: amd)

Use Aho-Corasick. Assume first of all we build the trie of our strings (function t). If t(v, c) ≠  - 1 it means that there is an edge in the trie outgoing from vertex v written c on it.

So, for building Aho-Corasick, consider f(v) = the vertex we go into, in case of failure (t(v, c) =  - 1). i.e the deepest vertex (u), that v ≠ u and the path from root to u is a suffix of path from root to v. No we can build an automaton (Aho-Corasick), function g. For each i, do this (in the automaton):

cur = root
for c in s[i]
	cur = g(cur, c)
	And then push i in q[cur] (q is a vector, also we do this for cur = root).

end[cur].push(i) 	// end is also a vector, consisting of the indices of strings ending in vertex cur (state cur in automaton)
last[i] = cur // last[i] is the final state we get to from searching string s[i] in automaton g

Assume cnt(v, i) is the number of occurrences of number i in q[v]. Also, denote .

Build another tree. In this tree, for each i that is not root of the trie, let par[i] = f(i) (the vertex we go in the trie, in case of failure) and call it C-Tree.

So now, problem is on a tree. Operations are : Each query gives numbers l, r, k and you have to find the number .

Act offline. If N = 105, then:

1. For each i such that , collect queries (like struct) in a vector of queries query[i], then run dfs on the C-Tree and using a partial sum answer to all queries with k = i. There are at most of these numbers, so it can be done in . After doing these, erase i from all q[1], q[1], ..., q[N].

Code (in dfs) would be like this(on C-Tree):

partial_sum[n] = {}; // all 0
dfs(v, i){
	cnt = 0;
	for x in q[v]
		if(x == i)
		++ cnt;
	for u in childern[v]
		cnt += dfs(u);
	for x in end[v]
		partial_sum[x] += cnt;
	return cnt;
}
calc(i){
	dfs(root, i);
	for i = 2 to n
		partial_sum[i] += partial_sum[i-1]
	for query u in query[i]
		u.ans = partial_sum[u.r] - partial_sum[u.l - 1]
}

And we should just run calc(i) for each of them.

2. For each i such that , collect queries (like struct) in a vector of queries query[i]. (each element of this vector have three integers in it: l, r and ans).

Consider this problem:

We have an array a of length N(initially all element equal to 0) and some queries of two types:

  1. increase(i, val): increase a[i] by val
  2. sum(i): tell the value of a[1] + a[2] + ... + a[i]

We know that number of queries of the first type is and from the second type is . Using Sqrt decomposition, we can solve this problem in :

K = sqrt(N)
tot[K] = {}, a[N] = {} // this code is 0-based
increase(i, val)
	while i < N and i % K > 0
		a[i ++] += val
	while i < K
		tot[i/K] += val
		i += K
sum(i)
	return a[i] + tot[i/K]

Back to our problem now.

Then, just run dfs once on this C-Tree and act like this:

dfs(vertex v):
	for i in end[v]
		increase(i, 1)
	for i in q[v]
		for query u in query[i]
			u.ans += sum(u.r) - sum(u.l - 1)
	for u in children[v]
		dfs(u)
	for i in end[v]
		increase(i, -1)

Then answer to a query q is q.ans.

Time complexity:

C++ Code by amd

C++ Code by Haghani

Java Code by Zlobober

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

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

Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).

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

Fastest editorials till date :)

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

Is there any faster solution for problem F?

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

    What's wrong in this solution? Let's build suffix array for the string s1 + '# + s2 + ... + sn, then lcp array for this suffix array. For the given query (k, l, r) we are interested in suffixes which have lcp >= length(s[k]) with our string. We can find them using binary search. They will form a segment in this array. Then we need to cound amount of number l <= x[i] <= r in this segment, where x[i] is the index of string of the i-th suffix. It can be done with segment tree storing for each node sorted subarray of x. It seems to work in O(N * log^2(N)).

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

      It seems that you misunderstood problem statement...

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

C was kinda much easier compared to B... What ya think?

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

...

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

WOW :D Thanks for the super fast editorial :D ^_^ PrinceOfPersia

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

I think i am doing exactly as the editorial for question div2-D/div1-B.

Can someone help me find the mistake ?

http://ideone.com/S98N8o

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

Your editorials are so nice to read :)

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

It has been a long time since the last contest which has an easy-to-hack problem, so funny! And well, that moment you realized that the test you used to hack others is the test that could hack yours too...

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

My solution for F in as well but it uses another idea. I split strings in blocks of string each. Then for each block I build Aho-Corasick and using this data I count how many times strings from block occur in sk. And also manually check corner strings.

My AC solution: 13648193

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

Fastest Editorial ever, thank to PrinceOfPersia

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

Awesome Contest !

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

div2E/div1C can also be solved using Centroid Decomposition. For each level of the centroid tree, I maintain

int d[LOGN][N][10]

// d[i][j] stores the 10 minimum vertices on path from root till j in the i'th level of decomposition.

Now for each query u,v. I find it's LCA in centroid tree.Let level of LCA be "lvl". Answer would be a minimum vertices in the combined array of d[lvl][u] and d[lvl][v].

See this code for better understanding http://codeforces.com/contest/588/submission/13641078

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

In problem D:

When you add two clauses and , how can you avoid the case where both xei and pi is false but pi is true?

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

Another way to solve Div 2/C is by using map , Reason: two numbers a&b : 2^a + 2^b= 2^x then a=b; here is the soln —

http://ideone.com/carXAR

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

    This solution is absolutely the same, but it uses a map instead of an array, so you get O(n * log(n)). Good solution.

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

      Thnx MistaFrosty , but space complexity is less for this soln..

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

div1b

"For the problem above, let dp[i][j] be the number of valid subsequences of b where x=j and floor(i_1/n) = 0 and floor(i_x/n) = i"

isn't it supposed to be like x=i and floor(i_x/n) = j?

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

any prove for B div2 ?? it's not clear for me :/

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

    Well lets present N like N = p[1] ^ a[1] * p[2] ^ a[2] * ... * p[k] ^ a[k]; So any divisor of N can be presented like p[1] ^ s[1] * p[2] ^ s[2] * ... * p[k] ^ s[k], where 0 <= s[i] <= a[i]. So if we try to maximize the answer we should make s[i] as much as possible but we cant make any s[i] > 1, because then our 'answer' would be divisible by p[i] * p[i]. That's why the actual answer is p[1] * p[2] * ... * p[k]

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

I used persistent segment tree for Div2 E, so,no merging is needed here,simply build the tree in less than 10 lines of code and query for your answer in 4 lines :) A nice problem to solve during contest...

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

    and I implemented 300++ lines of code in virtual contest , and still couldn't solve it :|

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

Were there large random tests in E? I've tested my solution on one of them during the round, the first submission worked in 6.7s, so I decided to optimize it, and the third submission ran in 5.5s on that test. And I was quite surprised to see that my solution has maximal time 3.8s, so I think my first submission was AC too.

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

    My solution worked in 9s locally against ~6s on CF, and about the same time ratio for solution of C. I blame system performance difference.

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

      Yes, these were times on custom invocation on CF. Locally it ran about 8s in the beginning, and the last version worked in 6.2s.

      Any comments from administration? It seems that custom invocation doesn't show the right time the solution runs on system tests, I think it's quite important issue.

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

        If your soluion got TL then it will rerun on free core with high priority several times. So if your solution got AC, the value of running time maybe incorrect. But if you got TL, you can be sure that your solution actually works slow.

        P.S.: Thanks for -100 with #define int long long.

        P.S.2: I'm not administration, so information can be wrong.

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

          I don't think that's the case: TL is 7s, and the running time of the solution is 3.4s. Also I chcked that test generation works in 358ms, so it shouldn't have affected the running time much.

          P.S. Sorry for that, I almost always use it, when seeing a problem involving long long-s.

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

Div1A/Div2C was fun. Which should be the approach if the subsequences must be contiguous? I was struggling with this question before the clarification

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

Any ideas of how to prove mathematically that the above Div2-A relation/function is the best strategy to minimize the amount of money Malek will have to pay?

I mean it seems the best according to humantic logic and I see that, but how to prove it with a mathematical model?

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

    Proof by contradiction should do the trick.Or an inductive proof.Lets assume a cost function C(n) to represent the minimum cost that duff spends and a min containing minimum price found till date. Base Case : C(1) = a[1]*min(Here we only have one pricing so indeed min = p[1]) Lets assume this strategy to be true for C(k) for k being some positive Integer with min being minimum cost found till k.C(k+1) = C(k) + (a[k+1]*min).Now the possible candidates for min is either minimum found till k or p[k+1].So min = minimum(min,p[k+1]).Now assuring that min is still minimum by making the most optimal choice we conclude that C(k+1) is also the minimum cost.Hence the result.

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

The artwork was wonderful as always!

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

Can somebody explain how the function insert(x, v) works in the question E of Div 1?

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

Thanks for Python Code for Div2 A, B :D

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

Div1 C is identical to a problem on SPOJ 3 years ago which requires a O(qlogn) solution. It seems that many guys just submitted their SPOJ code to get over this prob lol.

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

Div 2 E can be solved with persistent segment tree aa well . solution

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

Hi first thank you for contest:) I have a little problem with problem C(Div2), I got Wrong answer in Test 11,but i dont know why?!!:( 13659056 Plz help me... Ty

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

    Hey anybody there?!! Please help,im really confused

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

I'm wondering if anyone has solved Div1A by using a priority queue instead of counts? Such solution has O(n log n) asymptotics and hopefully should pass with n = 1000000 if using a fast implementation of PQ. Unfortunately it TLEd for me with stock java.util.PriorityQueue (13631725), probably because it treats those ints as objects instead of using an array of primitives.

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

Can you help mr, please? I'm trying to solve Div2C/Div1A in Java. (http://ideone.com/SxR0n8) And got TimeOut at test11. How can I improve my solution?

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

I have a really simple idea for Div1A/Div2C Let there be Ci weights of weight = Wi.

Thus, total weights from Wi is Ci * (2^Wi) which is same as (Ci << Wi) — let's call this Ti

Let's bitwise OR all Ti forall i and call it T.

The number of set bits in T is the answer!

This is because if xth bit is set in T, we can safely make a group out of each ith weight class whose (x >> Wi) bit is set.

But, my solution times out :( — any idea why??

http://codeforces.com/contest/588/submission/13659655

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

can someone explain the logic for div2c ?

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

can anyone tell me why my solution for C div 1 gets TL ? http://codeforces.com/contest/587/submission/13660815

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

Can any one tell me way my approach is wrong for problem B/Div2

we now that each number n can be written as product of prime factors :

see the image

so i created prime sieve generator , and for each prime that divide n ( n%p == 0 ) , i add it once to the answer ( ans*=p )

what's wrong with this approach .

this is my submission 13667353

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

    what if n is prime ?

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

      in that case ans will be equal to 1 so i can print n but it's not the case for my submission .

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

        If there is one prime larger than 10^7, like N = 2000000014 = 2 * 1000000007, then ans will be equal to 2, and you'll not add 10^9 + 7 to the answer.

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

Could someone please outline the proof that the answer is the number of set bits in div1A/div2C? Thanks in advance!

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

Div-2 (B)

Firstly, Sorry for my naive question. I didn't understand why a ≤ p1 × p2 × ... × pk ? Can anyone explain? Thanks!

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

    because the original number is made of those prime factors each of them is raised to some power so if you remove those powers of course you end up with a number which is smaller than or equal to the original number (in case the powers =1 )

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

In Div1: Problem A i understood number of set bits is equal to the unique number power of two addition But after that i didn't understand Why this algorithm working...

MAXN = 1000000 + log(1000000) bit[0..MAXN] = {} // all equal to zero ans = 0 for i = 1 to n bit[w[i]] ++ // of course after this, some bits maybe greater than 1, we'll fix them below for i = 0 to MAXN — 1 bit[i + 1] += bit[i]/2 // floor(bit[i]/2) bit[i] %= 2 // bit[i] = bit[i] modulo 2 ans += bit[i] // if bit[i] = 0, then answer doesn't change, otherwise it'll increase by 1

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

    I think it is done this way Suppose we obtain this for two element array

    [a, b]

    a = bit[k] b = bit[k + 1]

    Then,

    a * 2^k + b * 2^(k + 1)

    => ((a/2)*2 + a0) * 2^k + b * 2^(K + 1)

    => a0 * 2^k + (a/2)*2*2^k + b * 2^(k + 1)

    => a0 * 2^k + (a/2)*2^(k + 1) + b * 2^(k + 1)

    => a0 * 2^k + ((a/2) + b) * 2^(k + 1)

    So,

    bit[k] = a0 = (a & 1)

    bit[k + 1] = b + (a / 2)

    Now, a0 = (a & 1), the least significant bit

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

A small correction for complexity of Div1B: it should be O(n k + n log n), not just O(n k), because of sorting. This can make a difference when n = 1000000 and k = 1.

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

Can anyone offer a brief explanation about problem E please? I really don't know what is the basis of a vector and why the answer is 2 ^ (b.size()) ...

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

Can someone explain the notation in Div-2 D/Div-1 B ?

Please correct if I am wrong, but I think that a valid subsequence of length x will contain exactly one element from the sequence [b[k*n], b[(k+1)*n-1] for every (k+1) <=x.

As far as I understand, dp[i][j] stores the number of subsequences of length j that pick element b[(j-1)*n+i] in the last round. If this were true, the final answer would be sum of all elements in dp[][] (minus cases where we counted the last element to be at an index greater than c). I don't understand the need for the quadruple summation and the multiplication with (c-j) at all.

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

Can somebody explain Div. 1B/Div. 2D (Duff in Beach) ?

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

In Div1 B , How are we able able to satisfy condititon that : For each 1 ≤ j ≤ x - 1, (floor (i[j] / n)) + 1 = (floor (i[j + 1] / n)) ?? UPD : Got it.. :)

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

    This is just an overcomplicated way to say that you should pick each member of your subsequence from a consecutive sequence of instances of the given sequence a. This formula looks so ugly that I have actually missed it during the contest:) This mistake made me count the number of any subsequences, not just consecutive ones. At least I have learned how to compute binomial coefficients for a fixed n up to 10^18 as a result of this failure :)

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

can anyone help me find the mistake in my solution for problem C?thanks~

Your code here...
#include <stdlib.h>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <stack>
#include <queue>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <tr1/unordered_map>
#define _INDEX(i,j,n) ((i)*(n)+(j))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
typedef long long ll;
using namespace std;
const int MAX_N=1e5;
const int MAX_E=2e5+2;
const int MAX_M=1e5;
const int MAX_Q=1e5;
const int MAX_LOG=17;
int head[MAX_E];
int node[MAX_E];
int nxt[MAX_E];
int edgeCnt;
int n,m,q;
int c[MAX_N];
int par[MAX_N][MAX_LOG];
int h[MAX_N];
vector<int> pos[MAX_N];
vector<int> ID[MAX_N];
int result[10];
void addEdge(int u,int v) {
    node[++edgeCnt]=v;
    nxt[edgeCnt]=head[u];
    head[u]=edgeCnt;
}
void init() {
    memset(node,0,sizeof(node));
    memset(nxt,0,sizeof(nxt));
    memset(head,0,sizeof(head));
    memset(par,-1,MAX_N*MAX_LOG);
    memset(h,0,sizeof(h));
    memset(c,0,sizeof(c));
    memset(pos,0,sizeof(pos));
    memset(ID,0,sizeof(ID));
    edgeCnt=0;
}
void dfs(int u,int p=-1){
    par[u][0]=p;
    if(p+1) {
        ID[u]=ID[p];
        h[u]=h[p]+1;
    }
    if(pos[u].size())
        ID[u].insert(ID[u].end(),pos[u].begin(),pos[u].end());
    for(int i=1;i<MAX_LOG;i++)
        if(par[u][i-1]+1)
            par[u][i]=par[par[u][i-1]][i-1];
    for(int i=head[u];i;i=nxt[i]) {
        int v=node[i];
        if(p-v) dfs(v,u);
    }
}
int lca(int u,int v) {
    if(h[u]<h[v])
        swap(u,v);
    for(int i = MAX_LOG - 1;i >= 0;i --)
        if(par[u][i] + 1 && h[par[u][i]] >= h[v])
            u = par[u][i];
    if(u==v)
        return u;
    for(int i = MAX_LOG - 1;i >= 0;i --) {
        if(par[u][i]-par[v][i]) {
            u=par[u][i];
            v=par[v][i];
        }
    }
    return par[u][0];
}
void test() {
    for(int i=0;i<n;i++) {
        cout<<i+1<<":";
        for(auto id:ID[i])
            cout<<id<<" ";
        cout<<endl;
    }
}
void query(int u,int v,unsigned int a) {
    int l=lca(u,v);
    //cout<<"lca "<<u+1<<" "<<v+1<<" "<<l+1<<" a "<<a<<endl;
    priority_queue<int> heap;
    for(unsigned int i=ID[l].size();i<ID[u].size();i++) {
        heap.push(ID[u][i]);
        if(heap.size()>a)
            heap.pop();
    }
    for(unsigned int i=ID[l].size();i<ID[v].size();i++) {
        heap.push(ID[v][i]);
        if(heap.size()>a)
            heap.pop();
    }
    if(pos[l].size()) {
        //heap.insert(heap.end(),pos[l].begin(),pos[l].end());
        for(auto p:pos[l]) {
            heap.push(p);
            if(heap.size()>a)
                heap.pop();
        }
    }
    int k=heap.size();
    for(int i=0;i<k;i++) {
        result[k-1-i]=heap.top();
        heap.pop();
    }
    printf("%d ",k);
    for(int i=0;i<k;i++)
        printf("%d ",result[i]);
    printf("\n");
}
//WA in cf??
int main() {
    freopen("587C_DuffInTheArmy.fin","r",stdin);
    int u,v,a;
    while(~scanf("%d %d %d",&n,&m,&q)) {
        init();
        for(int i=0;i<n-1;i++) {
            scanf("%d %d",&u,&v);
            u--;v--;
            addEdge(u,v);
            addEdge(v,u);
        }
        for(int i=0;i<m;i++) {
            scanf("%d",c+i);
            pos[c[i]-1].push_back(i+1);
        }
        dfs(0);
        test();
        for(int i=0;i<q;i++) {
            scanf("%d %d %d",&u,&v,&a);
            u--;v--;
            query(u,v,a);
        }
    }
    return 0;
}

13764478

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

for Div 2C/ Div 1A .. could someone please explain how we actually counted Number of set bits in a sequence .. is that a particular algorithm for this question .. I am actually not bale to understand the working or logic behind the editorial given Plz HELP!!

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

    Hello ankush, Really simple. When you have two set bits at pos i, this is equivalent to one set bit at pos (i+1). Hence the equation b[i] += b[i-1]/2. (since 2^(i-1) + 2^(i-1) = 2^i)

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

      thanks a lot but is there any online theory or tutorial regarding the logic??

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

In DIV2E, In Haghani's code , why does he do nodey y = get(v,d[v]-d[p] + 1). Why is the +1 required? Wouldn't that be going further up than p?

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

Can somebody please re-explain Div1-A?

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

The construction of the 2-SAT in Div1.D is really interesting! By the way, binary search is not necessary here. Just sort the edges by their destruction time in decreasing order, and set them to false in order until a contradiction occurs.

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

Proof for Div2.C please? And the procedure to count no. of set bits in S is not clear to me. Please help.

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

2a1 + 2a2 + ... + 2ak = S = 2w1 + 2w2 + ... + 2w2. Obviously, minimum value of k is the number of set bits in binary representation of S (proof is easy, you can prove it as a practice :P). can anyone prove this ? even an example will work

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

By problem Duff in the Army, I studied about LCA deeply. Thank you very much for this problem.

»
14 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Isn't O(Q * sqrt(N) * log(N)) supposed to pass Div2E / Div 1C ? I used Mo's algorithm on trees according to this link .

Here is my submission:

With FAST I/O

WITHOUT FAST I/O

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

Div1 B, output doesn't match answer:

3 12 2
5 9 1

Author's code output: 30, but there are 48 non-decreasing subsequences, e.g.

5 9 1  5 9 1  5 9 1   5 9 1  --> b
1 2 3  4 5 6  7 8 9  10 11 12 --> positions

length 1 subsequence 12
length 2: 
1-4,1-5,1-7,1-8,1-10,1-11,2-5,2-8,2-11,3-4,3-5,3-6,3-7,3-8,3-9,3-10,3-11,3-12,
4-7,4-8,4-10,4-11,5-8,5-11,6-7,6-8,6-9,6-10,6-11,6-12
7-10,7-11,8-11,9-10,9-11,9-12

total 36+12 = 48

What's wrong here?

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

Can someone provide a formal proof for Div2 C/Div1 A. Please!! UPD: I understood it.