After searching on the internet I couldn't get a definitive answer, so I am asking here.

Does Fast Fourier Transform come up in Olympiads often or at all?

# | User | Rating |
---|---|---|

1 | tourist | 3748 |

2 | Benq | 3540 |

3 | Petr | 3470 |

4 | Radewoosh | 3355 |

5 | ecnerwala | 3347 |

6 | maroonrk | 3345 |

7 | jiangly | 3324 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 200 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 179 |

8 | Ashishgup | 176 |

9 | -is-this-fft- | 173 |

9 | maroonrk | 173 |

After searching on the internet I couldn't get a definitive answer, so I am asking here.

Does Fast Fourier Transform come up in Olympiads often or at all?

Today I lost expert and my girlfriend broke up with me.

I am making this blogpost to ask everyone for suggestions on how to deal with such an event.

help.

I've noticed that the blogs getting on the TOP tab on codeforces aren't necessarily the most upvoted ones.

I'm sure there exists a more complicated algorithm, but it seems to be based largely on the number of comments that a post has. This means that more controversial, stupid or someone started an argument in the comments posts which get people to comment will rise rapidly to the top.

What does the Codeforces community think about this? How would you change it?

I_Love_YrNameCouldBeHere and I are glad to invite you to Unofficial Div 4 Round #2. Which will take place this Wednesday at 14:35 UTC (The round is over now, but you can still participate virtually). The round will not be rated for any participants since it is unofficial.

Contest link: https://codeforces.com/gym/102873

You will be given six tasks and two hours to solve them. The problems were created and prepared by ssense and I_Love_YrNameCouldBeHere for users with a rating range from 0 to 1400 but anyone is welcome to participate in the round!

We want to thank everyone who was involved in the round preparation:

Errichto for thorough testing and publishing this round on the gym.

Also, after the contest Errichto will post videos about this contest and the responsibilities of a tester.

UPD: Videos are now up: Fixing A, Testing A, Testing the rest.

Brodicico for help with problems and testing the round.

And a huge thank you to the testers: Errichto, 1-gon, galen_colin, gupta_samarth, arujbansal, Chihai_Ion and Grumpah .

MikeMirzayanov for Polygon and Codeforces platforms.

Even though the contest is unrated, we believe it is an excellent way of practice, especially for Div 4 users.

Remember, if you don't know how to solve one problem, look at others!

UPD 1: Registration available now!

UPD 2: Round is over! We hope you enjoyed the problems and congratulations to the winners!

UPD 3: Editorial is out!

Div. 4 winners:

Not Div.4 Winners:

First to solve each problem:

A: First: Valera_Grinenko

Div. 4 first: anuragdvd

B: First: Geothermal

Div. 4 first: Lelouch_1

C: First: Geothermal

Div. 4 first: Lelouch_1

D: First: Geothermal

Div. 4 first: RamPrabodhInduri

E: First: Geothermal

Div. 4 first: -deleted-

F: First: IgorI

Div. 4 first: sahaun

Announcement of Unofficial Div 4 Round #2 by ssense SlavicG

Hello Codeforces, a lot of people have been asking me ** "How do I get GF!?"**. Well, I'm here to answer this question once and for all.

Until I have reached expert, no girl wanted to talk to me. Right after contest Codeforces Round #677 (Div. 3)(when I reached expert) my Instagram and Snapchat DM's were full of messages from girls asking me out, this will happen to you too.

But you can't only get the girl, you have to maintain her! Which brings me to step 2.

Once you reach Expert, you have to keep it, unless you want her to leave you for another expert. This can be easily done by 2 main ways

Never participate on Codeforces again.

Ask solutions from other people during contests.

PS: Make sure not to get higher than Candidate Master.

Ok, you are maintaining Expert, now you have to keep the girl attracted to you. Wavelength isn't going to do everything.

Buy her stuff. This is a very important step to maintaining a girlfriend(Eg: Food and Purses).

Teach her competitive programming, but make sure you have more rating.

Fight every simp she has to assert dominance.

No dates until marriage.

Upvote this blog post.

What's the point of having a GF if you can't flex on single people? NONE!

Message every single one of your friends and tell them about your brand new girlfriend.

This is the editorial for the **Unofficial Div4 Round#1** created by I_Love_YrNameCouldBeHere and ssense.

Previously you could only virtually participate, now the contest is open for practice!

Invitation link for the contest: https://codeforces.com/contestInvitation/d477e058f265a72092af5c11074234d720a0fb5f

PROBLEM A:

Idea: I_Love_YrNameCouldBeHere

We find the day that Alin got the maximum amount of money by iterating through the array. If we have no day when the sum is positive, output 0.

Create a variable max, a variable sum and a variable pos. Set $$$max = 0$$$, $$$sum = 0$$$, $$$pos= 0$$$. Iterate through the array and add $$$arr[I]$$$ to $$$sum$$$. If $$$sum > max$$$ then save $$$i$$$ in the variable $$$pos = i$$$, and set max to the current $$$sum$$$. After you are done iterating print $$$pos$$$.

Link to solution: https://ideone.com/wZWJBW

PROBLEM B.

Idea: ssense

The following greedy solutions always works: Sort the array $$$arr$$$, and then iterate until you find the minimum even number. If at the end of the loop it doesn’t exist then we have no answer and the solution is $$$-1$$$. Because we can not create an even number without any even digits. If there is an even element, save it’s index to a variable.Then print the array decreasing order (from $$$n$$$ to $$$1$$$)without the minimum even digit(the element at the saved index). After printing the array, print the minimum even digit so the number will be even.

Link to solution: https://ideone.com/fyDKc2

Problem C:

Idea: I_Love_YrNameCouldBeHere

This problem can be solved using dynamic programming.

The idea is for every element we try $$$k$$$ elements before it to see which one will give us the least cost.

Set an array $$$dp[n+1]$$$ and all the elements are equal to $$$10^9$$$ and set $$$dp[1]$$$ = 0; iterate through the array from $$$2$$$ to $$$n$$$ and for each $$$dp[i] = min(dp[i], dp[j]+abs(arr[i]-arr[j]))$$$ where $$$(i-k \leq j < i)$$$ and $$$j$$$ indicates one of the last $$$k$$$ bus stops. After you are done iterating print $$$dp[n+1]$$$.

Link to solution: https://ideone.com/zllXMy

Problem D:

There are $$$2$$$ cases: If $$$k$$$ is even Bob makes the last move and he can always insert a coprime number with the gcd of the array, so after the insertion the $$$gcd$$$ of the array is $$$1$$$.

Idea: ssense

If $$$k$$$ is odd then Alice makes the last move. Alice wins if we can remove an element from the starting array such that the $$$gcd$$$ of $$$arr$$$ is bigger than 1. To find this out we can use the fundamental theory of arithmetic which states that any integer can be expressed as a product of prime numbers.For each element in the array we find what primes divide it by iterating through all the primes under 100(since it is given that $$$a_i \leq 100$$$). If any prime divides more than $$$n-1$$$ elements Alice wins since if Bob introduces a number Alice can delete that number in the next move. If no prime divides more than $$$n-1$$$ elements then bob wins.

Link to solution: https://ideone.com/nmWCRz

Idea: I_Love_YrNameCouldBeHere

Another solution for when $$$k$$$ is odd is with prefix and suffix $$$gcd$$$. Iterrate over all $$$a_i$$$ from $$$1$$$ to $$$n$$$ and set $$$prefixgcd[i] = gcd(prefixgcd[i-1],prefixgcd[i])$$$. Then do the same for $$$suffixgcd$$$, but in reverse order: from $$$n$$$ to $$$1$$$ and set every element $$$suffixgcd[i] = gcd(suffixgcd[i+1],suffixgcd[i])$$$. Be careful at $$$prefixgcd_1$$$ and $$$suffixgcd_n$$$, You should just attribute them the value of the element at the index. After that we just iterate over all the array and check if $$$gcd(prefixgcd[i-1], suffixgcd_[i+1]) > 1$$$ ( again, be careful at $$$a_1$$$ and $$$a_n$$$). If this is true for at least one element then the answer is $$$"YES"$$$. But if we can not find such i then the answer is $$$"NO"$$$.

Link to solution: https://ideone.com/R5YyHC

Problem E:

Idea: ssense

We create an array $$$sum$$$ where $$$sum[i]$$$ is the sum of all the elements in array $$$a$$$ with index smaller than one. Set $$$sum[0]$$$ = 0. We have $$$sum[i] = sum[i-1]+a[i-1]$$$. Now we can use binary search to find the smallest sum bigger than $$$b[i]$$$ then print the index where the smallest sum bigger than $$$b[i]$$$ is.

Link to solution: https://ideone.com/1DCK0b

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/03/2021 00:10:01 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|