kirankumarmitra's blog

By kirankumarmitra, 5 years ago, In English

Hello CF ! I don't understand the editorial or the solution to USACO 2016 Feb Plat P2, P3. Can somebody help me understand them ? Thank you so much for all your help !

Problem 2 USACO 2016 Feb Plat 2 Problem, USACO 2018 Feb Plat 2 Solution I understand that one has to use the idea of Kruskal, but why these lines are true (or what do they acutally mean) ?

Also, if we're connecting a row and have already connected k columns (for k > 1), then we only need to remove m−k fences in that row, since the columns we've already processed are guaranteed to be connected.

Doesn't it depend on which vertical fence you remove ? There are two cases, for the first one you need to remove 4 fences, and for the second one you need to remove 1 fences (note: the picture shows the graph, not the original configuration. Edges are Cell-Cell distance, and vertices are cells)

Another way to think about this problem is to note that, if we have an optimal solution, then the solution isn't affected by switching two adjacent rows or two adjacent columns.

What does this means ?

Problem 3 USACO 2016 Feb Plat 3 Problem, USACO 2018 Feb Plat 3 Solution For this, I understand and can come up with the O(N3K) algorithm with myself, but I don't understand how you optimize it to .

In the editorial, I understand all but this para:

We can compute the best solution using k doors via dynamic programming, iterating on k and adding one door at a time. We can use a divide-and-conquer algorithm to solve the linear version of this problem. The idea is that we can compute the middle values of the dynamic program first: if we compute the position to put our k-th door in dp[k][n/2], then dp[k][i] for i<n/2 must be to the left of that and dp[k][i] for i>n/2 must be to the right of that. In this way, we can on average halve the search space at each level of the recursion, so we don't have to do O(n) work to compute each value of the dynamic program. At each level of the recursion, we do O(nk) work, meaning the total runtime of this algorithm ends up being O(nklogn) for the linear version of this problem.

In particular, how you calculate dp[k][n / 2] without calculating dp[k][1], ..., dp[k][n / 2 - 1] first ?

PS: Here's a question my friend asked on CSE: https://cs.stackexchange.com/questions/101109/intuition-behind-floyd-warshall-being-faster. Can you answer it there/here ? I and him came up with the problem while discussing it.

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

By kirankumarmitra, history, 5 years ago, In English

Hello Codeforces community

I have good math contest background (I can solve IMO Shortlist C5-C7 with 60% success rate, went to national Math Olympiad Selection Camp in 2018 summer). However I don't have much CP experience.

What should I do to reach Codeforces Orange and USACO Platinum within christmas ?

Currently I can solve ~1.5 problems (out of 3 problems) in USACO (new) gold within around 1.5 hours and looking at past Codeforces Contests I can solve DIV 2 4-5 problems/ DIV 1 A-B very easily (within 40 minutes) (but I have difficulty implementing them: https://codeforces.com/blog/entry/61899)

I don't have much time to put on informatics since I have Math Olympiad TST's coming up soon.

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it

By kirankumarmitra, history, 6 years ago, In English

How can I reduce sillies while in programming contests ?

For example, in the last contest I took in some other coding site, I solved (solved means got the idea, just need to implement them) FIVE questions within twenty mintues (out of two hour contest). Now the first two was completely trivial to implement — I did that within ten minutes. So half hour, two questions down and I only need to implement four — sounds trivial right ? But I couldn't successfully implement any of them ! In one question I forgot to use long long instead of int, in another I forgot to increment by one in a case (but I didn't test that case), and in another question I couldn't figure out how to implement them (it looked very difficult).

So some questions:

  • How do I reduce the excessive amount of sillies I make while implementing ?
  • How do I implement effortlessly ? (In ideal world, implementation shouldn't take much thought right ?)
  • How do stop losing my sweat over those edge cases/off by one errors ?

Full text and comments »

  • Vote: I like it
  • +22
  • Vote: I do not like it

By kirankumarmitra, history, 6 years ago, In English

Can someone suggest any good resources to learn about how various integer data types are manipulated in C++ from a competitive programming perspective ? I'm having problems with understanding them, for example

  • When you do something like long int x = y*z, where y and z are long long int, but the value of y and z are small (say 100), would it cause overflow ?

  • When you do something like int x = (a*b) % prime when a, b, prime are of the order 109 (but still stored in int), would it cause overflow ?

  • What is the difference between double/point/long double etc ? How they're manipulated (like the above) ?

  • Does using longer (for example, using long long int instead of int) causes the programme to run slower ? If yes, then how much (like a factor of 2 ? a factor of 4 ?)

  • Why almost nobody uses long double in competitive programming ?

  • When manipulating digits of HUGE orders (like 10500), how that's done in CP ?

  • Why the strange result in running the following code ?

code

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it

By kirankumarmitra, history, 6 years ago, In English

IMO 2014 perfect score Alex Gunning will stream IMO 2018 solutions. Check this thread on Art of Problem Solving: https://artofproblemsolving.com/community/c6h1669224 for more info. Just wanted to share with CF community because you might be interested and more people watching this will give him more enthusiasm so this can happen again in the future.

PS: I'm in no way related to Alex Gunning

Full text and comments »

  • Vote: I like it
  • +44
  • Vote: I do not like it

By kirankumarmitra, history, 6 years ago, In English

Hello,

Where I can find Hard DP problems using different ideas in codeforces ? Sorting the problems tagged by dp in order of submission doesn't helps, as most of them recycle a few small set of ideas again and again. Some contains some new and novel ideas (http://codeforces.com/contest/626/problem/F) and are also hard, I'm looking for such problems.

Thanks !

Full text and comments »

  • Vote: I like it
  • +21
  • Vote: I do not like it