First dislike!

Actually, you are not right. The first comment was 10 years ago when codeforces was just opened. The comment was created by VitalyPavlenko

Not bad!!

I can relate.

indeed

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

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

Thank you

I hope to become blue idk how the scoring works

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

3 minute of queueueueue

I got 9 penalty.

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

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

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$$$).

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.

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.

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

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

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

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

Try number 734033887

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

Try 1 36

Answer exists 2, 3 and 6

Many people failed on test 25 because of it

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

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

even shorter code by maintaining the count of remainders

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$$$.

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

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

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.

Presumably sometime after the 12 hour hacking phase ends

In the notes describing the example

They didn't say you have to do only one operation. You can do operation as many times as you want.

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

Didn't expect someone will remember :)

P.S:- feeling happy ;)

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

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.

anyone!? ;_;

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

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;
  }
}

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

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

your code is printing 0 which is not allowed

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.

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

Let $$$dp(v, i)$$$ be the maximum number of edges between chosen vertexes in the subtree of vertex $$$v$$$ if we took $$$i$$$ vertexes in this subtree($$$0 \le i \le 3$$$). To calculate it use another dp — $$$f(i, j)$$$ means we are currently on the $$$i$$$-th child of current vertex and took $$$j$$$ vertexes. Then iterate over childs of current vertex $$$v$$$, suppose we are on $$$i$$$-th child, iterate on how many vertexes we took from the previous childs, let it be $$$prev$$$, iterate on how many vertexes we take from the current child $$$u$$$, let it be $$$cur$$$, and let $$$cost$$$ be $$$1$$$ if $$$cur = 1$$$ or $$$cur = 2$$$ (in this case we will count edge from $$$v$$$ to $$$u$$$) otherwise $$$0$$$. Then update $$$f(i, prev + cur)$$$ with $$$f(i - 1, prev) + dp(u, cur) + cost$$$. In the end update $$$dp(v)$$$ with the help of $$$f$$$ and don't forget the possibilty to take vertex $$$v$$$.

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.

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.

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

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

This testcase worked for me:

10
5 8
5 2
8 9
8 6
8 7
5 3
8 10
9 1
7 4

6
1 2 4

I have hacked it now with the sample you provided

Write it here.