vovuh's blog

By vovuh, history, 5 years ago, translation, In English

<almost-copy-pasted-part>

Hello! Codeforces Round 615 (Div. 3) will start at Jan/22/2020 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Daria nooinenoojno Stepanova, Mikhail awoo Piklyaev, Maksim Neon Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

This is unusual, but good news! Our friends at Harbour.Space have a message for you:

Hello Muscat

Hi Codeforces!

As a special prize for the Codeforces Round #615, we would like to invite the top 3 participants to take part in our Hello Muscat ICPC Programming Bootcamp, which will take place in Oman, from March 19 to March 25, 2020. The prize will cover the participation fee, accommodation, and half-board meals for the entire duration of the bootcamp (except flights)!

There are three requirements to satisfy:

  • You took part in at least 10 rated contests on Codeforces
  • Your max rating should be less than 1900
  • You should be eligible for ICPC and/or IOI 2020+
Fill out the form→

So unofficial participants are also in a game (if meet the requirements).

Good luck to everyone!

UPD: I want to thank Artem Rox Plotkin and Dmitrii _overrated_ Umnov for invaluable help with the round preparation!

UPD2: Editorial is published!

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

| Write comment?
»
5 years ago, # |
  Vote: I like it -33 Vote: I do not like it

First comment!!

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

**hope i will be cyan after contest **

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

Queueeeeeeeeeeeee.

»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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

codeforces: Div.3 contest
me: Let's get a speed performance check.

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

Why is vovuh always in the makers of div3 rounds(This does not happen in div 2 rounds).

No complains, just curiosity.

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

    I think that is so because vovuh started Div. 3 competitions. Not sure though....

»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Why someone sumbit a wrong solution on purpose then hack his solution ?

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

    Maybe they wanted to be at the top of the hackers during the hacking phase.

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

Again into the ashes

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

I think smarter requirements are needed for prizes in order to get rid of smurfing.

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

15000 participants but 100 upvotes?

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

Hope to become cyan. Hey rising_from_the_ashes! I felt in love with your handle!

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

    Thank you

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

    I hope to become blue idk how the scoring works

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

      hey, you can install its browser extension so that u will get an estimate that ur rating is going to change by how much

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

        I think I will just wait to see what happens. Though the site is very unstable currently (last round only took 2 hours for ratings to change)

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

          The site's not unstable, this round has a hacking phase that goes on for 12 hours after the contest. As successful hacks can change the results, standings are subject to change during the phase, and thus rating is not updated because rankings can change. Rating will update (relatively) shortly after the phase ends.

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

Want to become cyan after this round.

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

Guys! please answer me. How to tag someone by its handle in codeforces?

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

3bmcws.

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

Why i can't register now?

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

    there is many a times constraint in CF contest that you have to register atleast 5 min before the contest start

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

Long Queue!

»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Please do something about the long queue time. Thank you!

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

Queueforces!!!

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

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

{Deleted}

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

    There is no reason to kill yourself right now because of some computer not working properly, you will die somewhen anyway

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

anybody know how to solve E ?

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

    solve each column seperately. calculate how many steps of move 1 if you do k steps of move 2

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

    Solve for each column independently. For each shift $$$0 \le s \lt n$$$, count how many numbers will match their intended positions after shifting (let it be $$$f_i$$$ for a shift by $$$i$$$).

    Hint

    Then, for a fixed column, the answer is the minimum over all $$$n - f_i + i$$$, and the total answer is the sum of those.

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

How to solve C ?

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

    Get all prime divisors of the given number. To calculate first number Fix the first number as the very first prime number.

    To calculate second number: Start multiplying from next prime number onwards until the product becomes greater than first number.

    To calculate third number: Product of all the remaining prime numbers.

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

    Find all divisors of n.

    Than brute over all pairs of divisors and let that number be a, b.

    Than c = n/(a*b); if c is not divisible by that multiplication than don't select this pair. else you have found your answer.

    My Submission

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

      How your brute force pass?

      what is the maximum number of divisors a number has?

      I think it will be sqrt(n). Then how your solution pass.?

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

        no, it is cube_sqrt(n)

        see this: https://codeforces.me/blog/entry/651

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

        Any number less than $$$10^9$$$ has not more than $$$1344$$$ divisors, with $$$735134400$$$ having exactly that many. Actually, it is reasonable to estimate the number of divisors as $$$\sqrt[3]n$$$ for small numbers (even though it asymptotically grows slower than any polynomial).

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

    Simple and clear solution in 3 steps :
    1. find all divisors of n greater than or equal to 2.
    2. brute force the divisors using 3 loops and check whether you can get those 3 numbers say a,b,c such that a*b*c ==n and a!=b && b!=c && a!=c .If you got these 3 numbers then flag = true and break from all three loops.
    3.If flag is true then print yes and a,b,c else print no . for further reference see my code by clicking on C.cpp : C.cpp

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

    Greedy approach; let sq = sqrt(n) iterate i from 2 to sq, if n is divisible by i, store i in vector then divide n by i. Outside loop,if the vector size is 2 while looping, instantly break. if vector size < 2, print false. Else check if n(after loop) is not equal to numbers we push to vector and not equal to 1. If false then no, or else the answer is 2 numbers in vector and n that we get after looped.69322228

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

How do you lock your submission? I could not see the lock icon anywhere on the dashboard for the problems I solved.

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

    Submissions ran on system tests directly, so there are not pretests and options related to, like hacks and locking problem

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

      So for this contest there was no hacking phase? Sorry to ask stupid questions but I am new to this.

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

        Just like me boy!

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

          Why does it say "and after the round it will be a 12-hour phase of open hacks" in the blog?

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

how many number of divisors number has in problem c. In worst case.

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

    Try number 734033887

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

      It works for 30. which has 3 distint divisors 2,3,5

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

        You have missed the case where there are only two primes and both of their power is 2. For example : 36. Your code returns NO. But there is an answer : 2, 3, 6

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

    Haven't completely checked your code but you over-complicated the problem while the constraints aren't that big.

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

    Try 1 36

    Answer exists 2, 3 and 6

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

My approach for E: Process each column separately .For every column calculate cost for every possible rotation. For calculating the cost of every rotation loop through every value and find out for which rotation this element is at its correct position,and decrement the required no. of operation for that particular rotation by 1 .Choose rotation which require minimum operations .

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

Thanks for the contest!

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

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

Can someone help me understand where I went wrong in Problem C. My Solution Thanks in advance

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

    Your code is too long,I think you should learn to write concise code

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

How to solve D?

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

    I use std::set to matain the answer, and the code is pretty short and clear, here's my submission:69350130.

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

    even shorter code by maintaining the count of remainders

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

    Maintain array $$$B$$$, indexed from $$$[0, x)$$$. Initially, $$$B[i] = i$$$.

    For each query, do $$$B[y_j \text{ mod } x] \text{ += } x$$$. The answer after each query is the minimum value of $$$B$$$; however finding the minimum naively would be too slow ($$$O(qx)$$$ over all queries). We could use a segment tree, or even just an ordered set (for each query, remove $$$B[i]$$$ from the set, update $$$B[i]$$$, then add it back to the set. $$$B$$$'s values would always be distinct), to reduce it to $$$O((x + q) \log x)$$$, which should pass. Do be careful about overflow; either use 64-bit integers or stop updating an index if it exceeds a threshold $$$> q$$$.

    This works because it is always optimal to change each $$$y_j$$$ to the minimum possible non-negative value not already in $$$A$$$ (the array in the problem description), and $$$B[i]$$$ represents the minimum non-negative value $$$b$$$ where $$$b \text{ mod } x = i$$$ and $$$b \notin A$$$.

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

How to solve D?

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

    The question becomes easy when you observe that a number when added to x or subtracted to x, it's modulo w.r.t 'x' remains the same.

    Now, you just need to maintain precomputed of first % 'x' numbers, i.e from 0 to x — 1.Let's say this array as 'a'. Now, whenever a number comes. Find its modulo w.r.t 'x', and maintain a map or set, to check whether that number has come before.

    if you use this number, let's say y. then increase that number in your precomputed array i.e a[y] += x.

    Why? Because whenever a number will come, it will be holding place for next place of that modulo multiplicity.

    I tried my best to explain to you. Take a look at my submission, you will get more idea.

    My Submission

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

How to try on the hack? Its showing Illegal contest ID on clicking on 'Hack it!'

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

    I think there's no hacking phase. 'cause the solutions ran on system tests directly, and not pretests

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

      On div3 there is always a 12-hour hacking phase

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

        Oh, so you do not need to LOCK your solution in Div3.

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

          Locks are available in div1/div2 contests, not in div3 contests. You can read the rules of div3 to get more information

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

    to hack in div 3 open the solution of whom you want to hack and on the top right by clicking on "hack it" you will be directed to test case window where you can put the hack test case.

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

when will editorial come

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

    Presumably sometime after the 12 hour hacking phase ends

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

Who can explain to me why in my solution to Problem D I have to use long long.

the code:https://codeforces.me/contest/1294/submission/69352519

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

Where it is mentioned in problem D that we can increase or decrease one element in an operation more than once?? I mean a[i]-m*x or a[i]+m*x is possible for m>1 also in one single operation????

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

Very similar to Problem F ?

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

    Yes and the author is my teammate sonu628. Unfortunately I couldn't solve it. ;_;

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

      Never mind, I could not solve it either, even after solving it in the contest. I assumed the diameter of a linear tree = n (thus WA 39) :(

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

    Didn't expect someone will remember :)

    P.S:- feeling happy ;)

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

Hacks for C?

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

In problem F, what is wrong with this approach? First, I find a diameter and choose a and b as the ends of that diameter. Then, I banned every edge between a and b and create the new graph. After that, I run DFS from every vertex between a and b. Finally, I choose c as the vertex whose depth is higher (depth 0 is also considered, in that case c is between a and b). This was my submission.

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

    I didnt read your code but your approach is O(n^2) you can simply do a multisource bfs.

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

      Once I have erased the edges between the nodes in the diameter, I have a forest in which I have a tree rooted on each node and running DFS from them is O(V + E)

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

      Can you please explain your Multi-Source BFS Approach ?

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

        Its also basically the bfs, but initially in queue you have to put all the nodes whose distance is initially 0, also make their distance 0 initially. Now in the while loop instead of queue having a single node it will have many nodes with distances 0. The time complexity is same since it traverses whole graph, maintaining correct distances i.e O(V+E) .

        Now in this particular question after finding the diameter ends,for all the nodes in their path make their distance 0, and run multi-sources bfs to get the third node which is farthest from the path.

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

    TRY this case:

    12 11

    1 2

    2 3

    3 4

    1 5

    5 6

    6 7

    1 8

    8 9

    9 10

    8 11

    8 12

    I think the answer is 9 but your approach will give 10.

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

      please ignore. my bad. your approach will also give 9

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

        Don't worry, thanks. I got AC. The approach was right, I had a bug of using the name of the variable temp instead of diameter in my loop.

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

69357392 I know my code is not that clean, but please check it for my bug on B!

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

In problem D, what does "in one move" mean? It means increase or decrease any element of the array only one time or any? I asked my friend after contest, he said any. Did i forgot something?

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

    One move means increase/decrease one element once, but since they give you unlimited moves, you in effect can do unlimited increases/decreases.

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

      I mean why unlimitedly moving not declared in detail?

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

Approach for D?

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

    simplest way I can think to explain D

    #include<bits/stdc++.h>
    #include <utility>
    using namespace std;
    typedef long long int ll;
    
    int main()
    {
     ll q,x,i,j,k,l,m,o,p,t;
     cin>>t>>x;
     set<pair<ll,ll>> se;
      for(i=0;i<x;i++)
      {
          se.insert(make_pair(0,i));
      }
      map<ll,ll> mp;
      while(t--)
      {
          cin>>i;
          l=mp[i%x];
    
          se.erase(make_pair(l,i%x));
          mp[i%x]++;
          se.insert(make_pair(mp[i%x],i%x));
        //  cout<<(*(se.begin())).first<<(*se.begin()).second<<"dekh le\n";
          cout<<x*(*(se.begin())).first+(*se.begin()).second<<endl;
      }
    }
    
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked this Div 3 round. Especially how Mathematical C and D were. And that there were only 6 distinct problems.

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

    Agreed, I come from Project Euler background so it is familiar

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

      Great. How many problems did you solve on Project Euler ?

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

Is there anyone else with E failing on Test 8 ?

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

how to solve E? I heard that it is greedy, but i can't understand. Why greedy works? :(

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

    while traversing in each column(say j), if any element(x) is found which belong to column j in the final matrix. Then find no of moves required in the cyclic shift of this column so that x reaches to its correct position.

    Maintain a map[mv,fre]

    mv: no of moves required so that x reaches to its correct position in the cyclic shift.

    fre: frequency of such elements which reaches to its correct position after mv moves in the cyclic shift.

    Now, for each column min no of moves required(say min_col) is the n-max(difference between freq and mv). So the ans is sum of all min_col

    For better understanding have a look

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

can somebody help me with the testcase on which my soln is failing

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

hello all. My code for problem C gives the wrong answer on test case #2. Here is what I am doing: a) Find the "first" divisor of n greater than equal to 2. b) Find the "second" divisor which is not equal to the first divisor if possible. c) If possible then check if n/(first*second) is >= 2. d) If not possible then there is only one divisor >= 2 of n except itself. Then choose "second" = (first*first) and check if triplet is possible.

Please Help!![submission:69361400]

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

    Sure, try $$$100$$$ as test case. According to your code, your first divisor is $$$2$$$ and the second one is $$$4$$$, so you check if $$$4$$$ divides $$$50$$$ and that gives you NO, you should choose a divisor after extracting the previous one. Also, your code is $$$O(t*n)$$$ and $$$n \leq 10^9$$$ and $$$t \leq 100$$$, so it will give you TLE.

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

what is the hack for C ?

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

    Idk, but maybe it's due to the timeout since most of the hacked code got over 1900ms...

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

What is test case 8 in E??

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

hi guys can anyone tall me how to solve C? I don't understand why it always is optimal to try first divisor of n

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

    find all prime factors with their respective powers in sqrt(n) time then check three cases case 1. no. of prime factors are more than3 answer always exist and it is any combination you can pick up then

    case 2 only 2 prime factors but their total power is greater than or equal to 4 then answer exist else no. (a,b,a^x*b^y)

    case 3 only 1 prime factor available then check if its power>=6 (a,a^2 a^3) then answer always exist else no.

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

      I also wrote my solution based on same logic, except that I was considering for case 2 that the sum of powers should be greater than equal to 3

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

    We just need to find 2 different divisors such that one of them is a composite one with again 2 different divisors and also you need to check that they are greater 1.

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

    hmmmm you can list all of divisors of N, the max numbers of divisor of N is 100 (if N == 1e9) so you can use O(N^3), right? Use 3 loops and check every divisor by conditions of problem

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

      Not exactly n³ because no. Of divisors are way to less for numbers <= 1e9.Its not 100 but around 1700-1900 i guess

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

        you can check it! numbers of divisors of 1e9 is 100, I tried it before I wrote my solution

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

          Any number less than 1e9 has not more than 1344 divisors, with 735134400 having exactly that many. Actually, it is reasonable to estimate the number of divisors as cbroot n for small numbers (even though it asymptotically grows slower than any polynomial).

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

            Maybe you don't understand what I say :(

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

              Maybe that's the reason but this logic works right XD

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

Guys, I am confused about the Problem D. In the example it states that: "After the fourth query, the array is a=[0,1,2,2]: you don't need to perform any operations, maximum possible MEX is 3 (you can't make it greater with operations)." __ However, if we add one to the last element will get a=[0,1,2,3] which I think has a MEX of 4. Can someone explain me why adding one to the last element does not improve the MEX?

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

    You can add only number x. In this testcase x equals to 3, so u cant add 1, u can add only 3 as many times as you want

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

Whats testcase 3 of problem F?

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

    This testcase worked for me:

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

No hacking in this Round? I am getting Illegal contest ID.

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

any idea to solve problm D please ?

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

When the ratings will be updated?-

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

Whoops, looks like I submitted a solution for 1294E - Obtain a Permutation that has an error in it not covered by the testing suite, but it's too late to hack it: 69397747

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

    I have hacked it now with the sample you provided

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

I think I am the only one who solved C via Miller-Rabin.

It proves that it is no use to think the problems as too difficulty in div3 rounds

»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

I have created the video solution for the first four problems, explaining my understanding and approach for the same. Codeforces 615 DIv3 Video editorials

Do like comment, share, subscribe if you like the video. Do subscribe for more such content

Happy Coding

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

I think your test cases for 1294E - Obtain a Permutation is too weak. 69353056 Shows: Output: 0 For Input: 4 4 5 2 3 4 Where the actual result is: 1

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

Huge gap between next contest....... Please decrease the gap

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Hi dear,

I participated in Codeforces Round #615 (Div. 3) with my 2 personal handle (7ouda,7ooda) and submitted same solutions so my submissions was skipped, and I didn't know that it's a rules violation, so please can you help me.

Thanks, Mahmoud.