Summary of the problem: You are given a polynomial $$$a_0x^0 + a_1x^1 + a_2x^2 + .... + a_nx^n$$$

Initially, you will be given the values of $$$a_0, a_1, a_2, a_3 ..... a_n$$$.

The degree of this polynomial(n) will be at most $$$200000$$$.

Then there will be another $$$200000$$$ query. In each query, you will receive $$$x$$$. You will have to find the value of the polynomial after evaluating with $$$x$$$ with $$$mod$$$ $$$786433$$$.

Problem Link: Codechef Polyeval

Note: There is an editorial about this problem. But in that editorial, setter mostly discussed about the details of FFT rather than the details of the problem. Or I might be missing the whole point. So, can you please help me here? :(

Thanks a lot. I would be obliged.

Hi,

Recently I came across the problem SPOJ-Maxmatch While doing a marathon on FFT. After being unable to solve this, I went to search for the editorial of this problem. Found a blog explaining this.

But cannot actually visualize what is going on here. Why does matching function respond to that polynomial or why does it work? And how we represent the polynomial in the form: $$$(x^{-1} + x^{-3} + x^{-4})$$$? Can anyone please explain?

Thank you so much!

Hello community,

So Earlier, I wanted to learn about the topic 'Gaussian Elimination'. But couldn’t manage to find any standard resources(From seniors in my university) .

Can you please provide me some good resources regarding it?

Thanks a lot.

Hello Community,

So I recently went through some strange situation while using different versions of the compiler in code forces. While solving 448C - Про покраску забора, I wrote a basic straightforward dp code. But when I submitted the code in C++17(64 bit) it showed the verdict Runtime Error on test case 27 and I had no idea why. Then I tried to debug my code for hours later came up with no solution. Then for no reason when I submitted the same code in c++11 it got accepted in one go.

AC Code: 78082968

RTE Code: 78083039

Besides, I also faced a situation where a certain code gets Accepted in a compiler version but gets TLE in another version. Can you explain the reason? Thanks.

Hello Community,

Thanks for participating in Criterion 2020 Round 6.

Standing: here.

A. Code At The Time of Pandemic

Author: Hasinur_

This problem is very simple. Let, totali = Number of total infected people till the ih day. So, the number of new infected people on (i+1)th day newi+1 = totali * 2 and total number of infected people till (i+1)th day = totali + newi+1 Totali and newi become large with increasing N. So, the calculation may not fit into 32-bit integer calculation.

Code.

B: The Multiplication

Author: Shefin_

The main idea is: for each k, pre-calculate all possible values of ( (1+k) x (1+2k) x …. x (1+ik)) mod m, where ik <= 2^27. But to store them, we need a huge amount of memories. So, we will store the values maintaining a period. For example, if we maintain a period of length = 1000 and we store the values in an array called pre[], then for each k,

pre[1] will store ( (1+k) x (1+2k) x …. x (1+1000k) ) mod m pre[2] will store ( (1+k) x (1+2k) x …. x (1+2000k) ) mod m and so on.

If we need to calculate ( (1+k) x …. x (1+2115k) ), then we can use the value stored in pre[2] and calculate the rest manually. As we are maintaining a period of length = 1000, we don’t need to run more than 1000 loops to perform that rest calculation.

The rest of the task is pretty simple. They are for the readers to find out.

[Note: The length of the period should not be much large. In that case, a large amount of loop will be needed in each test case and that will give a Time Limit Exceeded verdict.]

Code.

C: Hasinur’s Mission

Author: Hasnaine_

It is a simple Dp problem with a little bit of combinatorics in it. If you have the basic idea of dynamic programming, you might have solved this problem already in the contest.

So, we have to calculate from a certain node how many other nodes are there along the way where he will pass at least one road with prime numbers. Then if there is a total of x nodes from the node y where he will meet the condition. Ans will be increased to (xP2 = x permutation 2) or simply x * (x — 1). You can calculate the number of nodes y from every node x by a single or two dfs using dynamic programming.

Complexity(O(n))

Code.

D: Stick Game

Author: Dhruba10414

When a beauty number becomes replaced by another number in a range, after a few updates it will be several blocks continuously with the same numbers. You have to merge them in one big block. Use segment tree to do this. You can also use square root decomposition in this problem.

Complexity O(nlogn).

E: Change In Array

Author: tanus_era

At first divide the array into sqrt(n) blocks, where each block contains sqrt(n) elements. This trick is called sqrt decomposition. Then the update queries can be done using DSU(Disjoint Set Union) in each block. Total time complexity is O(q*sqrt(n)) . Here m is the number of queries and n is the size of the array.

This problem can also be solved in bruteforce, by using some compiler optimization trick. Setters were not aware of this technique, but some(Almost everyone having an AC solution of E) contestants have solved this problem using that. Here you can learn about that technique.

Code.

Hello Community,

We would like to invite you to the Criterion 2020 Round 6. It is a rated round of Toph hosted once in a week.

Time: 10th April 2020, 15:00(Bangladeshi Time)

Duration: 2 hours 30 min

Contest Format: ACM ICPC Format

Number of Problems: 5-6

The problems are prepared by: Hasnaine_, Dhruba10414, Shefin_, tanus_era,Moshiur_, Hasinur_.

We would also like to thank TarifEzaz and hjr265 for the beautiful platform and the opportunity.

Happy Coding, see you in the scoreboard!

UPD: Editorial is here.

UPD 2:

Standing:

1. Alpha_Q

2. fsshakkhor

3. Egor

4. arman_ferdous

5. aniks2645

Congratulations!

Hello Competitive Programmers from BANGLADESH!!

As we have already been informed 'Technocracy 2019' is offering a segment called 'INTER UNIVERSITY PROGRAMMING CONTEST'.

Here some details have been shared about this programming contest.

About teams and slots, here are some details -

• It’s an inter university programming contest. So, any university student from all over the country can form team to compete in this contest.

• The teams competing consist of up to three persons (not less than two persons).The coach has to be a faculty member.

• Total numbers of the teams will be 90.

• Slots will be allocated to each university. Allocated slots for each university will be published on 17 June, 2019.

• The primary registration will be continued till 15th June. And every team is requested to register within this time.

• The payments should be completed after allocating the slot to each university and within the payment deadline.

About Registration here are some details -

• Event Link: Click here.

• Our primary registration is going on. For registration, Click here.

• Last date of primary registration : 15 June, 2019.

• Slot distribution : 17 June, 2019.

• Final registration with payment starts: 18 June, 2019.

• Last date of Final registration and payment: 28 June, 2019.

• Registration Fee: 3500 bdt + 53 bdt (bkash).

For the Rulebook link of IUPC, Click here.

More details about the contest environment will be published soon...

Happy Coding. <3

Problem Link: https://www.hackerearth.com/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/practice-problems/algorithm/sherlock-and-inversions/description/

The problem is about counting the number of inversion in a particular range(from L to R).

My approach: I used Mo's Algorithm here. And to calculate the add and remove function I used Merge Sort Tree. I was pretty sure it will pass the dataset of 5s. But somehow it gave TLE. Maybe miscalculated the complexity.

There is few solution available in the internet where I saw every of them solved it using Binary Indexed Tree. So, my question here is, if the problem will be solved using Merge Sort Tree or not after any kind of optimization. Or should I definitely use BIT. And if i do have to use BIT, then why?

My code: https://ideone.com/wPb0AC (You can skip the code though)

I am confused about something. Whatever i post in codeforces blog, whether it is a funnier one, or tutorial one. I always get downvoted. I had to delete most of my previous post because of getting too many downvote. I wrote about a trick about segment tree a few days ago. I had to delete that too. :) Thanks.

I don't know if most of the codeforces user biased in giving vote by rating or not. Keep everyone demotivated by downvoting. :)