ABC 335

 

ABC 335

 

 

Problem C

This is a fun puzzle, cause once you make the connection it feels great.  You need to make the connection that when the dragon moves, you just append new position of head, and then all of the other positions move one forward, so just look at bottom N element sin the stack.  So you just look at the position p from the back of the stack to get where that current segment of the dragon is in the coordinate space.

Problem D

I think this is a little obvious, just take the spiral.  Implementing the spiral to fill in the values is the only tedious aspect.

Problem E

The easy approach to this problem is to observe that it is not a DAG.  But you can merge adjacent nodes that have the same value with union find or dfs.  And have those act as a connected component and it is now a supernode.  Then this will create a DAG and now you can perform DP on it.  Cause you need DP to find the maximum number of distinct nodes in a simple path from first to last node.

 

Another approach is using a priority queue that will force you to explore the nodes with the smallest value so far.  This way it will make it explore the graph in a greedily manner.  I don't have a great argument for why this works, but it feels intuitive.  And if asked I can probably provide a more concrete reason. 

 

Problem F

 

You can solve it with dynamic programming to count the number of ways.

dp(i) = number of ways to paint

 

I see how you could solve it in O(n^2), cause you have all the connections and it is just sum of everything that can connect to current state.  But like yeah how do you do that faster than O(n^2).  Maybe convex hull trick or dp on segment tree?

 

The AM–GM inequality, or inequality of arithmetic and geometric means, states that the arithmetic means of a list of non-negative real numbers is greater than or equal to the geometric mean of the same list.

 



 

 

I read the example with 1,2,2,3,3,3,4,4,4,4... and I extended that pattern out to 200,000 elements, you get to something with ...,631. But what I observed is that each of those elements is visited 1,2,2,3,3,3,4,4,4,4... I believe. If you do this all the way out with 200,000 elements you get the ...,631. So for the worst case I get about 80 million iterations. And if you take N * sqrt(N) with N = 200,000 you get about 89 million. So I guess it is O(N * sqrt(N)) for that worst case. Still not to sure. This is just extending the worst case scenario introduced in the editorial. I don't have enough time to think about this for now though.

 

Problem G

Discrete Logarithm Problems, that should be interesting.  That is a known difficult problem in mathematics.

 

This is really deep into modular arithmetic and number theory, yikes.

 

baby step giant step algorithm for solving discrete logarithms.

 

More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naïve algorithm, some of them proportional to the square root of the size of the group, and thus exponential in half the number of digits in the size of the group. However none of them runs in polynomial time (in the number of digits in the size of the group).

 

The solution:

Since P is prime you might be able to do something with Fermat's Little Theorem

Fermat's Little Theorem gives you this dime if P is a prime integer


This means that the powers of Ai will form a cycle, and the length of it must be a divisor of P - 1



 

Important to note that the first A^0 = 1, the smallest possible integer is 1 for the multiplicative cases here.  Can't multiply a number by itself and get 0.

 


 

We want to find the multiplicative order of


which is the smallest ki such that this is true.

 

The algorithm for finding the multiplicative order is quite simple.  Just find the prime factors of P.  Then start with x = P - 1 and then just test. 


And if this is true then update x to be this.  x will continue to become smaller as it works towards the smallest multiplicative order of the Ai.  This should take


 time.

 

Then comes the next part.

 

Now an (i, j) is valid pair if kj divides into ki.  You can store these in (value, counts) pairs, and since ki is divisiors of P - 1, there can be at most possibly 10,752 So it should be fast enough.  But the question is why is this valid and solves the problem?

 

Proof:

You can take an arbitrary element with multiplicative order P - 1, this is something special and is called a primitive root, let's call it g.  We know this exists, because it always does for a prime moduli.  This means that the first P - 1 powers of g will take all the values in the range [1, P).  You can also think of it that each integer Ai will have an index in where it fits with the primitive root. Here we didn't pick one but if we did it would have integer

 

Example of a primitive root of P = 7, is g = 3

because under modulo 7

3^0 = 1

3^1 = 3

3^2 = 2

3^3 = 6

3^4 = 4

3^5 = 5

3^6 = 1

 

Okay this is a primitive root because all integers [1, 7) appear in the cycle.  and the cycle is 3, 2, 6, 4, 5, 1 and it will keep repeating forever.  Now the question is if you have g^x  = Ai (mod P), you want to solve for x, that is none other than the discrete logarithm which is


It is the discrete logarithm with the base g with argument Ai which will give the index at which Ai appears in the cycle that cycles through all integers in P.

 

 

So, when it's said that the length of a cycle is one of the divisors of  −1P−1, it means that the number of steps after which the sequence of powers of a number modulo  P repeats itself exactly divides  −1P−1. This is a fundamental property in number theory and has important applications in fields like cryptography.

 

So why can you translate the problem from multiplicative operations modulo P to additive operations modulo P - 1?

 


 

 

By the properties of exponents, 


implies that the exponents themselves, k*ai and aj are congruent modulo P - 1. This is because the order of the group generated by g is P - 1 and thus the exponents cycle every P - 1 steps.  In simpler terms, the powers of g start repeating after P - 1 steps, so we only need to consider the exponents modulo P - 1.

 

Use example above of primitive root 3 for modulus 7 as an example.  you have 1,2,3,4,5,6 powers forming the 6 distinct integers.   But if you start from 0 now you get 0,1,2,3,4,5?  not making sense still though.

 


 

And it follows when you have this congruence you can say that the gcd(ai, P - 1) divides gcd(aj, P - 1)

 

 

Concept:

if you have two gcd values such as g1 and g2 and g1 divides into g2, that means all the prime factors of g1 also exist in g2.

 

 The code in github repo: https://github.com/algosand/archive-cp/blob/master/atcoder/abc/beginner335.md

 

 

 

 

 

Comments

Post a Comment

Popular posts from this blog

Codeforces Round 918 div4

Image
  Codeforces Round 918 (div 4)   Problem A Use the frequency to determine the element that appears once.   Problem B Have a set for each row and column with "ABC" and remove characters in specific (r, c) pairs. And there will remain a single set with just one character.     Problem C Determine if the sum is a squared integer.   Can use math.sqrt to determine this.   Problem D Create string of C and V for identifying the consonants and vowels. create a deque to store the locations of dots. Iterate over the CV string, and anytime you find CC, that means it must be CVC was the prior syllable.   Cause you found a CVCCXXX,   The other pattern that can appear is if XCVCVX,   if you see VCV, that means there must be a CVCVX,   You know there was a CV pattern before the CV of most recent.   Which the most recent could be a CVC, you don't know what X is ...
Read more

Codeforces Round 920 div3

Image
  Codeforces Round 920 (div 3)     Problem F Square root trick, You can use the square root trick to calculate prefix sums in n * sqrt(n).  Where you compute the prefix sums for each step size from 1 to sqrt(n).  Now anytime you have a query where d <= sqrt(n) it can be solved in O(1) with the precomputed prefix sum.  Else it will have sqrt(n) iterations in brute force looping through to get the value.   You do need two prefix sums because you have to create the ones that will give the answer for this specific problem.  Which is a little bit tricky to derive.  Problem G   My approach was very bad for this problem.   You want to use a diagonal prefix sum and column-wise prefix sum.   But the thing is that implementation is very important.   If you try to pad by K to avoid where the diagonal is out of bounds you will end up with 10^5 by 10^5 matrix which is too large.   And if you pad by 1 for the diagonal ...
Read more

Algorithm: Digit DP

Image
  Algorithm: Digit DP    Solutions to some problems that can be solved with Digit DP algorithm. Digit Sum   The problem is asking to find the count of integers in the range from 1 to K (inclusive) such that the sum of digits is divisible by D.   Do you want to exclude zeros? If the answer is yes than you need to track which states do not contain a nonzero digit yet.   Why do I want to exclude zeros, because 0 % 1 = 0 in python, so it says 0 is divisible by 1 or actually any positive integer.   So we have one part we will track which is the "zero"   Do you want separate logic for tight bounds? Yes you want to make sure you have separate logic for when the prefix is exactly equal to K.   This way it doesn't allow any numbers greater than K.   So we have another part "tight"   Of course we need to track at what index we are when iterating through the digits. So we have an "index" ...
Read more