danilka.pro's blog

By danilka.pro, 10 years ago, translation, In English

483A - Counterexample

Problem author gridnevvvit

This problem has two possible solutions:

  1. Let's handle all possible triples and check every of them for being a counterexample. This solution works with asymptotics O(n3logA)
  2. Handle only a few cases. It could be done like this:

if (l % 2 != 0) l++; if (l + 2 > r) out.println(-1); else out.println(l + " " + (l + 1) + " " + (l + 2));

Jury's solution: 8394832

483B - Friends and Presents

Problem author gridnevvvit

Jury's solution is using binary search. First, you can notice that if you can make presents with numbers 1, 2, ..., v then you can make presents with numbers 1, 2, ..., v, v + 1 too. Let f(v) be the function returning true or false: is it right, that you can make presents with numbers 1, 2, ..., v. Let f1 be the number of numbers divisible by x, f2 — the number of numbers divisible by y, and both — number of numbers divisible by x and by y (as soon as x and y are primes, it is equivalent to divisibility by x·y). Then to first friend at first we shold give f2 - both numbers, and to second friend f1 - both numbers. Then we must check, could we give all other numbers divisible neither by x nor by y.

This solution works with

Jury's solution: 8394846

483C - Diverse Permutation / 482A - Diverse Permutation

Problem author gridnevvvit

Let's see, what's the solution for some k = n - 1:

1 10 2 9 3 8 4 7 5 6

At the odd indexes we placed increasing sequence 1, 2, 3 .., at the even — decreasing sequence n, n - 1, n - 2, ... First, we must get the permutation the way described above, then get first k numbers from it, and then we should make all other distances be equal to 1.

This solution works with O(n).

Jury's solution: 8394876

483D - Interesting Array / 482B - Interesting Array

Problem author gridnevvvit

We will solve the task for every distinct bit. Now we must handle new constraint: l[i], r[i], q[i]. If number q[i] has 1 in bit with number pos, then all numbers in segment [l[i], r[i]] will have 1 in that bit too. To do that, we can use a standard idea of adding on a segment.

Let's do two adding operation in s[pos] array — in position l[i] we will add 1, and in posiotion r[i] + 1 — -1. Then we will calculate partial sums of array s[pos], and if s[pos][i] > 0 (the sum on prefix length i + 1), then bit at position pos will be 1, otherwise — 0.

After that, you can use segment tree to check satisfying constraints.

Jury's solution: 8394894

483E - Game with Strings / 482C - Game with Strings

Problem author gridnevvvit

Let's handle all string pairs and calculate the mask mask, which will have 1-bits only in positions in which that strings have the same characters. In other words, we could not distinguish these strings using positions with submask of mask mask, then we must add in d[mask] 1-bits in positions i и j. This way in d[mask] we store mask of strings, which we could not distinguish using only positions given in mask mask. Using information described above, we can easily calculate this dynamics.

Now, when we have array d calculated, it is not hard to calculate the answer. Let's handle some mask mask. Now we should try to make one more question in position pos, which is equal to adding one more 1-bit in mask in position pos. After that we may guess some strings, they are 1-bits in mask s = d[mask] ^ d[mask | (1 << pos)]. Then you have to calculate number of bits in s quickly and update the answer.

Jury's solution: 8394918

482D - Random Function and Tree

Problem author RoKi

Let's calculate d[v][p] dynamics — the answer for vertex v with size of parity p.

At first step to calculate this dynamic for vertex v we should count all different paintings of a subtree visiting all children in increasing order of their numbers. By multiplying this number by 2 we will get paintings visiting children in decreasing order. Now some paintings may count twice. To fix that, let's have a look on a some subtree of a vertex v.

Consider all the parities of children subtrees visited by our function (0 or 1). First thing to note is that among these parities exist two different values, the subtree will have different paintings with different ordering (you can prove it yourself). Otherwise, all our children sizes have the same parity.

If all sizes are even, this subtree will be counted twice. Otherwise, if sizes are odd, we are interested only in odd count of visited subtrees. This way, we must subtract from our dynamic the number of ways to paint any number of children with even subtree sizes and odd number of children with odd subtree sizes.

Jury's solution: 8394936

482E - ELCA

Problem author danilka.pro

Let's split all M requests in blocks containing requests each. Every block will be processed following way:

First using dfs we need to calculate for every vertex v, where u is every ancestor of v, sizei — size of subtree of vertex i, including itself. This value shows how will the answer change after removing or adding vertex v as child to any other vertex, furthermore, answer will change exactly by pathv·sizev (decreasing or increasing).

Then we will calculate chv the same way — the number of all possible vertex pairs, which have LCA in vertex v. This value shows how the answer changes after changing Vv — if Vv changes by dVv, answer changes by chv·dVv.

Then mark all vertexes, which occur in our block at least once (in worst case their number is ). Next, mark every vertex being LCA of some pair of already marked vertexes, using DFS. We can prove that final number of these vertexes is at most . After all this we got 'compressed' tree, containing only needed vertexes. Parent of vertex i in compressed tree we will call vertex numbered Pi.

On the image above example of this 'compression' way is given. Vertexes colored red are vertexes in request block, blue — vertexes marked after LCA, dotted line — Pv → v edges in compressed tree.

Example of compressed tree

On such compressed tree we need to calculate one new value Cv for every vertex v — the size of a vertex, lying on a way from Pv to v after Pv on main (non-compressed) tree (son of a Pv vertex in main tree).

Now we should process request on changing parent of vertex v from pv to u on a compressed tree. The answer will change by pathv·sizev. Now for every vertex i, lying on a way from root to Pv vertex, two values will change: sizei will be decreased by sizev, but chi will be decreased by sizev·(sizei - Ct), (Pt = i), but pathi will stay unchanged. For every other vertex j only pathj will be changed: it will be decreased by . After that, we got compressed subtree where subtree of a vertex v is missing. Next, doing the same way as above, all values are changed considering that v (and all it's subtree) is a children of a vertex u. Do not forget to change Cv too.

Let's see, how the value-changing request of a vertex v is to be processed. As described above, the answer will be changed by chv·dVv. For every vertex i lying in vertex v subtree only pathi will be changed (it could be easy done using Cto values), all other values stay unchanged.

This solution has complexity, but in N = M case it has to be .

Авторское решение: 8394944

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

| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, will English translations be available at sometime? google translate was blocked in China.:D

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

I think that problem 483B could be solved in a mush easier way, which works O(1): 8386617

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

    The gcd function would give the log factor. So it wouldn't be O(1) ;)

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

      As soon as x and y are primes, there is no needed — their is equal to x·y.

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

      Oh, I see. I forgot that.

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

There are lots of very similar ways to solve Game with Strings. Here are two more of them: first, calculate d[mask] as in the editorial.

1) The number of different masks you visit during a game is equal to number of questions you ask. So from linearity of expectation the expected number of questions is the sum of the probability that you will visit mask, for all masks.

That probability is easy to calculate: it's .

See 8396215 for the code.

2) Let dp[mask] be the expected number of questions from state mask. When we try to ask question pos in state mask, the chance that we will not guess correctly right away is equal to the fraction frac = bitCount(d[mask ^ (1<<pos)]) / bitCount(d[mask]).

So dp[mask] is equal to the average of 1 + dp[mask ^ (1<<pos)] * frac, for all pos not in mask.

See 8412617 for the code.

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

    Why should I divide binom(len, bitCount(mask)) ? I don't understand this.Can you explain it?

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

      You're on the start state and you want to know the probability that you will reach the set of questions asked represented by mask. You will reach mask unless one of the following things happen first:

      • By asking all questions (or some of them) in mask you already know what the answer is.
      • You ask a question not in mask.

      For the first item not to happen, you need the final answer to be one of the values which is not immediately distinguishable from the replies to queries to positions in mask. By construction of the d[] array, there are bitCount(d[mask]) such values, so the probability that the answer is a "good" one for you to reach mask is .

      This leaves the second case. If the answer is a good one, it's still possible that you will ask a question not in mask, and therefore not reach it. For this not to happen, you need your first bitCount(mask) questions to be exactly the ones in mask. As you have len choose bitCount(mask) ways (or binom(len, bitCount(mask)) ways) to choose your first bitCount(mask) questions and only one of those ways is good, this is responsible for the factor.

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

What does totalGuessed[i] denote in the link given in the Div1 C- Game of Strings? http://mirror.codeforces.com/contest/483/submission/8394918

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

Why we are doing sum[r[i]]-- in the solution of Div1-B ??

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

    Instead of iterating all the intervals to set the bits to 1, he stores the beginning and end of those intervals and only iterates the whole array one time for each bit position

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

Can someone explain Div2/b with more details?

#include <iostream>

using namespace std;


int main()
{
    int cnt1,cnt2,x,y;
    cin >>cnt1 >>cnt2 >>x >>y;
    int l=1,r=INT_MAX,m;
    while(l<r){
        m=(r-l)/2+l;
        if(m-m/x>=cnt1 && m-m/y>=cnt2 && m-m/(x*y)>=cnt1+cnt2){
            r=m;
        }
        else{
            l=m+1;
        }
    }
    cout <<r;
    return 0;
}

always CE

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

Sorry, but can anyone explain to me the Div1-C method? I can't understand it well. 1. the solution says: Let's handle some mask mask. Now we should try to make one more question in position pos, which is equal to adding one more 1-bit in mask in position pos. What does it mean by saying "make one more question"? 2. what does this s = d[mask]^d[mask|(1<<pos)] mean exactly? I took it as "if I guess position pos, the remaining 1-bit(s) in s denote the string that I am not sure if the selected string is one of them". But I am not sure about this.

Please forgive my broken English...

»
10 years ago, # |
Rev. 6   Vote: I like it -14 Vote: I do not like it

Deleted

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

HI ,Every one.
Can you help me with pro Div1B/Div2D ?
My submission got ACCEPTED.
BUT, I have a test which it's answer should be NO.
AND my AC code print YES.
the test is:
5 2
1 5 1023
1 5 511
AND THIS IS MY SUBMISSION:
http://mirror.codeforces.com/contest/482/submission/29177333

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

      Abusing notifications, huh?

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

      Passing system test doesn't mean your program is correct. It only means it passed all tests, the author thought of. It should happen barely, but you can't get rid of it.

      For example think of a code, which does if()s for all given test cases, and prints the correct answer. Obviously it won't work generally, but it will get AC.

      It's okay if you notice this, and ask to add this to tests, but you shouldn't abuse notifications, as extraVirgin said. Also, you should fix your code at your own, to pass both system tests, and this test.

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

483A — Counterexample how did he come up with that algorithm ? can anyone please explain

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

    see ,between any two even number there is an odd number(ex:10,11,12) so if (r-l+1)>3 and l is even then the answer is l,l+1,l+2 else you have to print l+1,l+2,l+3.(please ensure that if d==3 or d<3 and l is odd then answer is -1)