Can anyone recommend resources for preparing for the Distributed Code Jam on June 14th? Some past problems of a similar nature would be really helpful.

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3673 |

3 | Um_nik | 3493 |

4 | apiadu | 3397 |

5 | 300iq | 3317 |

6 | maroonrk | 3250 |

7 | Benq | 3230 |

8 | LHiC | 3229 |

9 | TLE | 3223 |

10 | ecnerwala | 3216 |

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

1 | antontrygubO_o | 192 |

2 | Errichto | 185 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 168 |

6 | ko_osaga | 165 |

7 | Radewoosh | 164 |

8 | Um_nik | 162 |

9 | 300iq | 155 |

10 | Petr | 153 |

Can anyone recommend resources for preparing for the Distributed Code Jam on June 14th? Some past problems of a similar nature would be really helpful.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/07/2020 13:21:37 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

One problem which appeared in AE last year was to compute LCS of two strings up to 10

^{5}characters.Some Simple Problems :Problem 1Given a Sequence A of integers , find i and j such that A(i) + A(i+1) ...+ A(j) is Maximum/Minimum , where length of A can be upto 10^10 .

TL : 1 secIdeaBasically , we divide A into say 10^8 lengthed 100 segments , and then process each of them on different machines and later combine the information to find the answer .

Problem 2Given a number N as large as say 10^20 , find it`s number of divisors .

IdeaDivide the set of possible divisors <= 10^10 , into 100 groups and then add the result from each of them.

But problem 2 can be solved on a single computer, there is probabilistic algo

By the way, I always wonder why people don't multiply the complexity by

log(n) which goes from findinggcdon every step? Let alone multiplying it once again when we work with big numbers and every operation consumes not constant, but logarithmic amount of time.Because on average gcd will not really be log, and with sensible limits big numbers is just a constant

Because on average gcd will not really be logHow to prove it? If I got you right, you say that there is an upper bound for that is better than

log(n).It's indeed O(log(n)) number of steps on average. About Pollard's rho algorithm, probably textbooks usually mention only expected number of iterations to avoid analyzing complexity for different arithmetic operations implementations.

Thank you for the link!

Yeah, your claim is correct for elimination of the second

log(n), but after reading the wiki article I still have no idea why they don't mention the first one in the expected complexity.Speeding up Using Multiple InstancesProblemGiven a sequence of

N(<=10^10) integers , find if there exists a Majority element.IdeaDivide sequence into say

Ksegments , then we process each of them individually to find candidates of Majority element and then the Majority element itself , if any .So Complexity reduces to O( N / k )