pranav232323's blog

By pranav232323, history, 15 months ago, In English

This man may not know much about programming, but he sure as hell knows something about persistence.

Full text and comments »

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

By pranav232323, history, 15 months ago, In English

There are many young school-aged kids on here, which is fantastic and helps foster a real sense of community on the platform.

Given how important community is for discovering new ideas and just generally keeping yourself motivated, I'd like to use this post to find mine -- people that are post-college and just starting out with programming contests.

Maybe we can start a discord or something. It can get really isolating when you have no one to discuss problems with or get excited with about a contest.

Full text and comments »

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

By pranav232323, history, 15 months ago, In English

I always seem to get a bunch of JavaScript and Chrome errors when trying https://cfviz.netlify.app/

Stack trace in case any of the developers is still active

Uncaught TypeError: Cannot read properties of undefined (reading 'length')
    at Object.success (single.js?__WB_REVISION__=1114:45:23)
    at c (jquery.min.js:2:27742)
    at Object.fireWith [as resolveWith] (jquery.min.js:2:28487)
    at l (jquery.min.js:2:78789)
    at XMLHttpRequest.<anonymous> (jquery.min.js:2:81117)
single.js?__WB_REVISION__=1114:164 

Uncaught TypeError: Cannot read properties of undefined (reading 'length')
    at Object.success (single.js?__WB_REVISION__=1114:164:23)
    at c (jquery.min.js:2:27742)
    at Object.fireWith [as resolveWith] (jquery.min.js:2:28487)
    at l (jquery.min.js:2:78789)
    at XMLHttpRequest.<anonymous> (jquery.min.js:2:81117)

DevTools failed to load source map: Could not load content for chrome-extension://cfhdojbkjhnklbpkdaibdccddilifddb/browser-polyfill.js.map: System error: net::ERR_FILE_NOT_FOUND

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By pranav232323, 23 months ago, In English

Hey all, I've noticed that although I can get AC on problems, I am utterly unable to formalize my intuition into a correctness proof.

For example, consider my AC solution to 1672C.

In my head, my justification for my approach was something like "after the $$$i$$$-th iteration, we have either performed an operation on it or not. If we performed an operation, $$$a_{i - 1} = a_i$$$, and this is the only index in $$$1, 2, \ldots, i - 1$$$ where this is true". This helped me realize that at the conclusion of the algorithm, we would have an array of equality $$$<=1$$$ as desired. However, despite my best efforts, I just couldn't show that my code did so in the minimal number of moves.

Now, this may be normal for a CP'er who's still in high school, but, as a CS graduate who's taken a number of math courses at university, I'm a little embarrassed that I'm having trouble proving the correctness of problems that are relatively simple (i.e. rated $$$[800, 1100]$$$).

To be explicit, I've taken proof-based classes in:

  • Discrete mathematics
  • Combinatorics
  • Graph theory
  • Number theory
  • Algorithms

so I know what rigorous math looks like, but the skillset just hasn't transferred over to correctness proofs. In my algorithms class, we spent a lot of time proving time complexities for standard algorithms like merge sort, but we never really focused on correctness.

I've looked at CLRS as well, but the exercises are formulated in a way that does the hard work for you (i.e. prove that this lemma is true vs. what is the lemma that you should prove to show correctness). Also, CLRS focuses on proving loop invariants via induction, but this isn't that useful for analyzing greedy algorithms, which dominate the problems I've been working on.

Has anyone successfully trained themselves out of this?

Is there a math book or a CSES-style problem set focused on correctness proofs that I could work my way through to get better?

Full text and comments »

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

By pranav232323, history, 23 months ago, In English

Specifically, I set the Country field to United States in Settings -> Social, but I can't find myself in this list.

How can I ensure that I show up there?

Full text and comments »

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

By pranav232323, history, 23 months ago, In English

Rather than focusing on the number of problems solved, I'd like to set goals on my consistency.

Full text and comments »

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

By pranav232323, history, 3 years ago, In English

I'm getting TLE despite having an optimal time complexity: $$$O(nk)$$$ where $$$k$$$ is the target and $$$n$$$ is the number of coins. I even tried optimizing the modulo operation according to https://codeforces.com/blog/entry/77506, but I still have one test case that keeps TLE-ing. Further, downloading and running that test case locally indicates that my code is executing in well under the time limit of $$$1$$$ second.

Is there anything I can do at this point?

Submission: https://cses.fi/paste/6a1dc1e39bbd5552186afe/

Problem: https://cses.fi/problemset/task/1635

P.S. Tagging pllk in case this is an issue with the judging servers.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By pranav232323, history, 3 years ago, In English

So, I've been using LeetCode to do some topic-wise practice on DP.

In particular, I've been doing the questions tagged medium and hard.

However, while I can usually solve the mediums in a reasonable time frame, I struggle to make any progress at all on the hards. As a result, I've been wondering whether or not I should attempt them at all at this stage. My official rating is $$$896$$$, but I think I'm around $$$1200$$$ since I haven't completed $$$6$$$ contests yet. In terms of goals, I'm trying to get comfortable with DP questions at the range of Div 2C.

Thus, my question is two-fold

1) How would you estimate the CF rating of LeetCode hard problems?

2) Should I continue solving LeetCode hards or just look for DP problems in the range of rating $$$\pm\ 200$$$.

Full text and comments »

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

By pranav232323, history, 3 years ago, In English

Hey guys,

The following submission keeps getting TLE even though it has the same time complexity as the official solution ($$$\mathcal{O}(n)$$$)

Submission: https://codeforces.com/contest/1430/submission/104613827

Problem: https://codeforces.com/problemset/problem/1430/C

Any ideas about what's going on?

Full text and comments »

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