SirShokoladina's blog

By SirShokoladina, history, 6 years ago, In English
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
  • +62
  • Vote: I do not like it

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

I asked someone to explain my div1B solution to me in this comment

And you actually did that, thanks :D.

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

SirShokoladina please fix div2E. There is parsing error.

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

A lot of things to learn...

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

C shows up as "unable to parse markup" for me.

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

Can you please provide code to the solutions, especially Div 2D/1B... really hard to understand the solution for me. Thanks a lot

Also, Div 2E/1C problem is missing it's solution

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

I don't understand div2 C part where it says that answer can be no more than n-x. Can somebody explain me little bit better?

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

    I think there is some inaccuracy. Consider cycle and every element in it: break it on intervals between elements equal to concerned element (include first boundary, exclude second). When element is single there is one such interval. Obviously that on every interval there is exists at least one bad replacement. So in every cycle at least k bad replacements, where k is max number equal elements in cycle. So if there is x equal elements in array then in every partition on cycles there is at least x bad replacements.

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

      how is it obvious that there is one bad replacement on each interval, why cant all elements be good replacements for some particular interval of some cycle ?

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

        Because we start and end on same value. Try to move ahead with this thought.

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

          Okay, that's pretty clear now, thanks !!

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

Great Contest! With mind blowing problems. SirShokoladina Sir, you should conduct contests more often.

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

LOL I did some kind of precalc on div1B. 40296044. My solution has complexity . But I can't implement it without map which contains vectors so it is very slow. Then i noticed that it can be precalculated and instead of 43 * log with bad constant it gives clear 43.

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

I think for the second solution to C, you mean to say that X and Y are the minimal possible values satisfying that condition (but the solution works).

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

Overall, I thought the logistics of the contest could have been managed better. Some of the problem statements could have been worded better, there were a lot of clarification announcements, etc.

That being said, I thought the problem quality was good, especially Div 1 C. If Div 1 BC were shifted down 1 problem (can't speak towards D or E), and another Div 1 B made, I think the problem scaling would have been perfect.

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

Can't understand the second solution for Div1.B. The solution says:

"In such way every satisfying this criteria parallelepiped (not considering the orientation) with three different side lengths was counted 6 times."

Let's consider the large parallelepiped to be 4x6x10, the small parallelepiped 2x3x5 will only be counted once. Why the solution says that it is counted 6 times?

(Actually, can't understand the first solution either... What does "mask" mean in the solution?)

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

    we count it 6 times — as 2x3x5, as 2x5x3, as 3x2x5, as 3x5x2, as 5x2x3 and as 5x3x2

    mask of length 3 in a subset of set {1, 2, 3} written as a 3-digit binary number. so 0 = 000 = {}, 1 = 001 = {1}, 2 = 010 = {2}, 3 = 011 = {1, 2}, 4 = 100 = {3}, 5 = 101 = {1, 3}, 6 = 110 = {2, 3}, 7 = 111 = {1, 2, 3},

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

      But the direction of the large parallelepiped is fixed, and 3 is not a divisor of 4, so why is 3x2x5 counted?

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

        Because we use the IEP on rotations (permutations), so both 2x3x5 and 2x5x3 are rotated in all directions and if at least one orientation satisfies then it is counted once, otherwise it is not counted.

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

so my understanding of div2D was correct but problem statement and number of submissions prevented me,huh,sad

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

can anyone help fix my mistake for div2 B?

Submission Link

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

    x > curh and y <= curh it will not update curh, in fact, curh = y.

»
6 years ago, # |
  Vote: I like it -21 Vote: I do not like it

?detaR tI sI

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

Why did my code of div1C which used "exit(0);" get "Idleness Limit Exceeded" in pretest 12?

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

    you noob

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

    maybe you use "exit(0)" before you actually guess the correct numbers?

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

    Oh I found a precision error in my code. But when I changed "exit" into "return" it got accepted.

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

      can you show me your code?

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

        exit:http://codeforces.net/contest/1007/submission/40288030

        return:http://codeforces.net/contest/1007/submission/40303376

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

          seems like the codes are really equivalent... I don't know, maybe you have ub.

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

Can Someone Please tell me a more intuitive way to understand the solution of div2 C (div1 A) or different easier approach if possible???

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

    The problem can be done by using two pointers. Lets sort the given array and initialize count and both pointer to 0. say pointers be i and j. starting from index 0, take next biggest element(by changing j) and when you find that, increase i, j and count. Here we are calculating the possible number of pairs in which smaller can be replaced by bigger number. Here is snipped for what I did:

    sort(a,a+n);
        ll cnt = 0;
        ll p1=0,p2=0;
        while(p1<n && p2<n){
            if(a[p1]==a[p2]){
                p2++;
                continue;
            }
            if(p2==n)
                break;
            else{
                cnt++;
                p1++;
                p2++;
            }
        }
    
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone please elaborate on the Div1B Second solution? (The Inclusion exclusion one) ...?!

It is not very clear to me how the "ans2" part is calculated by the author's solution...

If you had a different combinatorial solution please share that as well ..

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

    ans2 supposes that the first two lengths of the parallelepiped coincide. That means that this length should divide two chosen dimensions of the big parallelepiped. thus we use g[x[0] | x[1]]

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

    Look at my other comment lower, maybe it will help.

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

      thankyou , the whole approach is still exotic to me as I have never seen something like this before, but get your solution..

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

It seems that SirShokoladina forgot to link the editorial to the problems in Div2 (contest 1008). In any of the five problems we can't see the link of editorial.

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

    I don't know how to link them. I guess Codeforces this automatically.

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

      I'm sorry... I don't know that before.

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

      You can do that by clicking clip image at the top of the blog

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

Can anyone explain div2d in understandable way?

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

    I can elaborate on the second solution. First, google what inclusion-exclusion principle is. I'll explain its meaning. Assume you have a bunch of sets and want to know the size of their union. If for every set of this sets (for example "1st 2nd and 4th set" or "3rd and 5th set") you know the size of their intersection then you can count the size of their union.

    We have six orientations. Each of them gives us a set of parallelepipeds that we can pave the big one with. One of such sets is "1st side divides the 2nd side of the big, 2nd side divides the 1st side of the big and 3rd side divides the 3rd" side of the big", let's mark it 213. Now how can we find the size of intersection of several such sets? If we had two permutations 132 and 231 then a parallelepiped is inside the intersection of their sets if it satisfies both orientations. So its 1st side must divide both 1st and 2nd sides of the big, 2nd divides the 3rd side and 3rd divides also both 1st and 2nd. Then there are #d(gcd(A, B)) * #d(C) * #d(gcd(A, B)) such parallelepipeds (where #d is number of divisors). So we know the size of every intersection, thus we know the size of the union, which is the number of parallelepipeds that we can orientate somehow so it can pave the big. But now 2x3x5 and 3x2x5 are both counted. That's why we need to count something more, read the tutorial and I will continue if you don't understand.

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

      I understand to your part. Can you elaborate more? I mean, I know the inc-exc principle (union of a,b,c is a+b+c-ab-bc-ca+abc etc.) but I dont understand the editorial having read it 5 times already xD

      Maybe its just simple language but yours seem much more clear. Cant understand a single word from both solutions :P im bad at math lol Also, what do u mean about 2x3x5 and 3x2x5 being counted multiple times sir

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

      So for one query we perform following algorithm: use exc-inc principle for all 6 permutations (1,2,3) and count intersections of each subset of sets so we can obtain the union of this permutations which is our answear am i right? Second question is what does exactly p(m) from the end of the editorial mean, i dont get it ;(

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

        You were right in the beginning, but that is not exactly our answer. This is the answer, but when 1x2x3 is counted 6 times (as 1x2x3, 1x3x2, 2x1x3, 2x3x1, 3x1x2 and 3x2x1), 1x1x2 is counted three times (1x1x2, 1x2x1 and 2x1x1) and 1x1x1 is counted once.

        So the second number we count will be the same, but considering only parallelepipeds XxXxY, so two first sides coincide. Assume we fixed a set of sets and found which sides each side of the small parallelepiped must divide. In my example it was (A, B), (C), (A, B). Now as we know that first two sides are equal, we must unite the first two sets, so it will become: (A, B, C), (A, B, C), (A, B). So the number of such parallelepipeds will be #(gcd(A, B, C)) * #(gcd(A, B, C)) * #(gcd(A, B)).

        In the second number 1x2x3 was not counted (as 1 != 2), 1x1x2 was counted once (1x2x1 and 2x1x1 are not counted as 1 != 2) and 1x1x1 was counted also once.

        We multiply the second number by three and add it to the first. Now 1x2x3 is counted 6 times, 1x1x2 is counted 6 times and 1x1x1 is counted 4 times. Now we add #d(gcd(A, B, C)) * 2 and everything is counted 6 times. Then divide by 6 and get the answer.

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

          So we do count the second number exactly the same as the first one but on each intersection we consider first two sides to be equal? We use inc-exc principle once again right?

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

For div2C does cycle decomposition work if the permutation contains repeated elements? I mean for the proof it is assumed that there is a cycle decomposition?

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

Haha, I have a passing O(number of divisors * constant) solution of div1B. It's only barely passing though.

We can build bitmasks for each divisor describing which input numbers it divides. The key is that for each triple of bitmasks corresponding to the smallest, middle and largest number, we can pick an arbitrary assignment of dimensions to these three bitmasks (or ordering of three chosen divisors). Then, for each query and each ordering of divisors (6 in total), we can process the divisor list corresponding to the middle number, use 2 pointers to keep the number of divisors from the divisor list corresponding to the smallest number (similarly for the largest) that are smaller than the current divisor from that middle list, then check all pairs of bitmasks (smallest, largest number) that are valid for that current divisor's bitmask and the current ordering; since we have the number of ways to choose the remaining two divisors, computing the answer is straightforward.

The advantage of this approach is that there's no need to think about what to add, what to subtract, which orderings to use etc. It's all just iterating over initially arbitrarily chosen things. The obvious disadvantage is that it's slow, I needed some optimisations in the last test (namely "if all pairs of bitmasks give 0, skip innermost loop").

more detailed and formal explanation
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

anybody got any implementation for Div1C second solution?!

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

Hello, I have a question about my algorithm on div 2D/ div 1B.

First, I made some observations (not sure if they are correct):

  1. In order to divide the large parallelepiped into smaller (and equal) ones, we need each dimension of the small to be divisible by the corresponding dimension of the large.

  2. By adhering to the above observation, we enumerate a lot of duplicate parallelepipeds. For example, the parallelepiped (2, 2, 2) can be split into the following ones:

(1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (2, 1, 1), (2, 1, 2), (2, 2, 1), (2, 2, 2)

but, in reality, we only need the (1, 1, 1), (1, 1, 2), (1, 2, 2) and (2, 2, 2).

So, I have thought that we can just create the dimensions in increasing order. That means if we have a tuple (a, b, c), we have the constraint: a <= b <= c.

Now, on the programming part:

For each query,

  1. I find the divisors of a, b and c (the dimensions of the large parallelepiped).

  2. I find the number of all the possible combinations of the divisors I found above such as if I have the (a, b, c) tuple, I accept only the ones where a <= b <= c. On this step, I do some optimizations in order not to trigger a TLE.

Here is my code for reference:

http://codeforces.net/contest/1008/submission/40527094

(it is a bit unorganized, but, on a top level I implement the above steps)

So, my question is what am I doing wrong?? It is difficult for me to make sense of the editorial and compare my solution to the ones provided in order to find my mistake!

Thanks in advance! Any help is highly appreciated!

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

    your observations are correct. i think, what you are doing wrong is that you don't take into consideration that the orientation of the big parrallelepiped should not necessarily coincide with the orientation of the small parrallelepiped.

    if the sides of the big parallelepiped are A, B and C, you are trying to find the solutions of the form a <= b <= c, where a | A, b | B, c | C. but you do not find the solutions of the form a <= b <= c, where a | B, b | C, c | A.

    for example if the big parallelepiped is (3, 4, 5), you will not find the solution (2, 3, 5)

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

      Thanks for the reply! I will try to solve the problem now! :)

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

Hi, can anyone please help me with my div2C submission, it is getting error on test case 8

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

int main(){
	int n;
	cin>>n;
	std::vector<int> v(n);
	for(int i=0; i<n; i++)
		cin>>v[i];
	sort(v.begin(),v.end());
	int k=0;
	for(k; k<n; k++)
		if(v[k]>v[0])
			break;
	std::vector<int> num(v.begin()+k,v.end());
	int count=0;
	for (int i = 0; i < num.size(); ++i)
	{
		if(num[i]>v[i])
			count++;
		//cout<<num[i]<<" ";
	}
	cout<<count;
}
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1007A — Reorder the Array — this problem can be solved by using two pointers . Here is my solution Link