niyaznigmatul's blog

By niyaznigmatul, 6 weeks ago, translation, In English,

The contest is in the gym: Innopolis Open 2019-2020, qualification, contest 2

Hello!

The second qualifier to Innopolis Open 2020 rescheduled to December 14th 1:00 PM UTC.

Qualifier duration is 5 hours, there are five problems in the contest. Those, who scored high enough, will be invited to the final contest that takes place on February 22-23, 2020. Those, who already qualified, can compete in second qualifier as well, but they won't influence qualification.

Innopolis Open is only for middle and high school students. All others will be able to solve the problems in Codeforces::Gym.

There is a trial round taking place, it ends in the evening of December 13. If you are new to Innopolis Open it's good to take part in trial round to get to know the testing system and format of problems. Be careful, the trial round and qualifier don't take place on Codeforces website. To take part in the trial round or the qualifier you are required to sign up on Innopolis Open website. Don't forget to read the rules and the testing system guide on the website.

First qualifier took place several weeks ago, you can try to solve the problems in Codeforces gym: Innopolis Open 2019-2020, qualification, contest 1.

Previous year contests. Be careful, some of them may be in ICPC format:

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

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

Is there any kind of editorial for First Qualification Round?

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

    There is one in Russian + source codes: link, but we didn't translate it into English.

    We will be glad if someone from the community translates some of the ideas into English.

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

It sounds kinda strange, but how the checker for problem 4 at the first round is made? I think it is harder task to solve..

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I have submited in the last minute before the time has finished and you did not judge it sorry for my poor english but could you please check what's wrong ? My name is Besher Islambouley.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It seems that

    ll &ret=memo[id][xxx][crnt];
    

    part is wrong, because memo is int array.

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

      I have submited after that another one.

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

        I don't see another submission. Seems the server didn't receive it.

        I've searched for logs, and your submission was rejected, since it arrived to server at 21:00:00.665, which is 665ms after the contest end.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +13 Vote: I do not like it

How many contestants will qualify for the on-site contest?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

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

    One solution is to maintain set of possible sums, this is done by maintaining non-intersecting segments of sums, that is possible to get, initially only one segment $$$[0;0]$$$. After adding segment $$$[l;r]$$$, each segment of sums $$$[a;b]$$$ creates segment $$$[a + l; b + r]$$$, just merge intersecting ones. Observe, that if you sort segments of sums by $$$l$$$, then $$$1.4 \cdot l_i \le r_i$$$, $$$r_i < l_{i + 1}$$$. Therefore number of segments is at most $$$log_{1.4}(s)$$$. Another solution will be in tutorial, which is unfortunately in Russian. Idea is to divide segments into $$$2$$$ groups : $$$l_i > (1 - 1 / 1.4) \cdot s$$$ and others. Then from the first group you need at most $$$3$$$ segments, because if sum of $$$l_i$$$ of $$$3$$$ segments doesn't exceed $$$s$$$, then they're good set. Now consider only sets of at most $$$2$$$ segments from the first group. If those have sum $$$l_i$$$ at most $$$s$$$, then add some segments from first group until sum of $$$l_i$$$ is at least $$$s / 1.4$$$, or just all. You can notice, that it won't be more than $$$s$$$ at that point. So you need to pick $$$2$$$ segments with $$$l_1 + l_2 \le s$$$ and $$$r_1 + r_2$$$ being maximized, which is done by $$$2$$$ pointers.

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

      Thank you, the first solution is very nice! I didn't really get the second one at first, but now I think I got that one too. I think you wanted to write $$$l_i > (1-\frac{1}{1.4}) \cdot s$$$. Here's a description I wrote for myself to better understand the method:

      So basically we have 3 intervals $$$A=[0s;(1-\frac{1}{1.4})s]$$$, $$$B=[(1-\frac{1}{1.4})s;\frac{1}{1.4}s]$$$ and $$$C=[\frac{1}{1.4}s;s]$$$. If for some $$$l_i \in C$$$ we're done. Continuing with the second interval, because $$$1-\frac{1}{1.4}>\frac{1}{4}$$$, a solution with $$$4$$$ elements from $$$B$$$ cannot be valid, but also because $$$3 \cdot (1-\frac{1}{1.4}) > \frac{1}{1.4}$$$ if there's a solution with $$$3$$$ elements from $$$B$$$ the smallest $$$3$$$ must also form a solution. Thus we have three cases left, we either choose $$$2$$$, $$$1$$$ or $$$0$$$ elements from $$$B$$$. Here goes a handy claim that helps in all $$$3$$$ cases: let the sum of all left ends that lie in interval $$$A$$$ be $$$X$$$, if we choose some different elements from $$$B$$$ such that their sum $$$Y$$$ is smaller than $$$\frac{1}{1.4}s$$$, but $$$Y+X \geq \frac{1}{1.4}s$$$ then there is a solution, since if $$$Y+X \leq 1$$$ there is obviously one, but in the case $$$Y+X>1$$$ we can take out elements from $$$A$$$ until the sum will be smaller or equal than $$$X+Y$$$ and since all the elements we take out are $$$\leq 1-\frac{1}{1.4}$$$ we can't take out an element and then have a sum smaller than $$$\frac{1}{1.4}$$$ if before that the sum was greater than $$$1$$$. This claim immediately finishes the case when we examine the case when we take $$$0$$$ elements from $$$B$$$. If we take $$$1$$$ elements from $$$B$$$ we just loop over all the possibilities. If we take $$$2$$$ elements from $$$B$$$, we can use $$$2$$$ pointers as you mentioned.

      Did I understand correctly?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for pointing out my mistake, everything is correct in your explanation.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve D for k=4 faster than expected $$$O(b^4)$$$ calls to sqrt?

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

    Can you share your approach? Our approach does $$$O(b)$$$ sqrts on average.

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

      There are 2 observations:

      1) The prime gaps are $$$O(b)$$$ on average

      2) The difference between $$$\sqrt{n}$$$ and $$$\frac{p_1+p_2}{2} \cdot \frac{q_1+q_2}{2}$$$ is $$$O(b^2)$$$ on average.

      So we can loop over the prime gaps divided by $$$2$$$(let's call then $$$a$$$ and $$$b$$$) and $$$\frac{p_1+p_2}{2} \cdot \frac{q_1+q_2}{2}$$$(let's call it $$$e$$$). Let's call $$$\frac{p_1+p_2}{2}$$$ $$$c$$$ and $$$\frac{q_1+q_2}{2}$$$ $$$d$$$. Then $$$n=(c^2-a^2)(d^2-b^2)=c^2d^2-a^2d^2-b^2c^2+a^2b^2=e^2+a^2b^2-a^2d^2-b^2c^2$$$, so we can easily get $$$a^2d^2+b^2c^2$$$.

      $$$(a^2d^2+b^2c^2)^2=(a^2d^2-b^2c^2)^2+4abcd=(a^2d^2-b^2c^2)^2+4abe$$$ so we can easily get $$$a^2d^2-b^2c^2$$$ by square rooting and then finally get $$$a^2d^2$$$ and $$$b^2c^2$$$. Since we know $$$a$$$ and $$$b$$$ this allows us to easily get the values of $$$c$$$ and $$$d$$$, so now the factors are $$$c-a$$$, $$$c+a$$$, $$$d-b$$$ and $$$d+b$$$.

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

        An interesting solution! That's cool that you don't need any complicated factoring algorithms or knowledge for it, too bad it takes too long. Sadly, I don't see an easy way to improve it...

        Our solution is based on Fermat's factorization. Basically, whenever you have $$$n = rs$$$ and $$$|r - s|$$$ is small (to be precise, it must be $$$O(n^{\frac 14})$$$), you can find those $$$r$$$ and $$$s$$$ quickly. In our case, $$$n = p_1 p_2 q_1 q_2$$$ has two factorizations into close pairs: $$$p_1 q_2 \cdot p_2 q_1$$$ and $$$p_1 q_1 \cdot p_2 q_2$$$. Thus, we use Fermat's to find $$$p_1 q_1$$$, $$$p_1 q_2$$$, $$$p_2 q_1$$$, $$$p_2 q_2$$$, and then take pairwise GCDs to find primes.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?