NovusStellachan's blog

By NovusStellachan, history, 5 months ago, In English

Ok, here's the formal statement:

We have some array of integers $$$a_1, a_2, \dots, a_n$$$ with $$$n$$$ large (around $$$10^5$$$). We have to support the following types of operations:

  • Update: Select some subarray $$$[l, r]$$$ of $$$a$$$ and an arbitrary integer $$$x$$$, and add $$$x$$$ to each of $$$a_i$$$ for $$$l \leq i \leq r$$$. That is, we must be able to perform range addition. Note that $$$x$$$ can be both positive or negative.

  • Query: Count the number of integers at most $$$x$$$ in some subarray $$$[l, r]$$$ of $$$a$$$. Note that $$$x$$$ is allowed to change across queries.

Obviously, the interest is in subquadratic solutions. Fast online solutions (or offline) are interesting to me, and I'd be happy to know about them.

Thank you, NovusStellachan

Full text and comments »

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

By NovusStellachan, 7 months ago, In English

As a lot of us already know, Codeforces has certain differences in how it treats upvotes from users.

There are rating tiers on what your upvote is worth, and it is done to give non-negligible importance to the rare high-quality content that more experienced people can generally perceive quicker than others as useful for the community. For example, sometimes low rated accounts cannot distinguish between useful and useless higher level content, which has the potential to help them as they grow. This also gives people motivation to work harder to get to a better rating, though this is still very debatable. People treat this as ratism, but it is up to you to decide whether this is a good thing or not. It already works well as a spam-reduction measure, though.

However, it also recently started treating upvotes from "contest-inactive" accounts as worthless (i.e., accounts that have not participated in a rated contest for more than 6 months are unable to show that they like/dislike certain content on Codeforces without commenting). This brings down the weight of upvotes from people who have not participated down to 0 — below what even a newbie's upvote is worth.

Interestingly, some contest-inactive but very cf-active and high-rated people noticed that on the original Codeforces site, voting was completely disabled for contest-inactive accounts, showing that Codeforces might be becoming more explicit about this choice (though this is not the case for the mirror site). Is this a bug?

Is the contest-inactivity cutoff implemented to combat spam and upvote farms (i.e., alts made to upvote/downvote content)? There are definitely much better ways to combat this spam — for example, if you are being conservative, keeping upvote weight intact for contest-inactive Div 1 accounts. Here is why the current system of contest-inactivity based cutoffs might actually be bad for Codeforces:

  • Majority of the users that still read/contribute to Codeforces are contest-inactive and have a higher proportion of more experienced people, so filtering out what is known as wisdom of the crowd makes the process already less informed and it portrays the opinion of only a small subset consisting of generally less-experienced people as the overall community opinion (which has obvious consequences in terms of more volatile herd mentality and so on, which is a major factor in proliferation of spam/controversy/low SNR content).

  • Accounts that are used for upvote/downvote farming and commenting in a way that wants to influence community opinion tend to participate in much fewer contests compared to the usual user, and it should also take a lot of time to get to Div 1 for many accounts, for example, if you don't submit from multiple accounts in the same contest (and this can be detected via anti-cheating measures that are currently in place). This supports the argument that lower rated contest-inactive accounts are more likely to be spam/alts than higher rated contest-inactive accounts.

  • Higher rating is correlated with how serious someone is about competitive programming and related things, so the same argument that holds for giving different weights to upvotes also holds for this suggestion. Arguably, older people who have engaged with the community for a longer time also tend to have more mature opinions (in the sense of community moderation) and are also smarter (have higher rating).

  • Div 1 contests have historically been much rarer than lower division contests so it's possible that someone is not able to participate in contests for longer than someone who is div 1, and thus the 6 month penalty is penalizing div 1 accounts more than it penalizes lower rated accounts.

A few final suggestions:

  • Remove inactivity cutoff for high rated users.

  • Have better moderation for content from lower rated accounts.

  • Have optional filters to remove content from lower rated accounts.

  • New posting space for every color, and accounts with color >= cutoff_for_that_space are allowed to interact (post/comment/vote) in that area, but it is visible to all.

    • Catalog was a solution in this direction, but the cutoff rating was so high that there was no activity there for long periods of time. Thus, it is important to have better granularity.
  • Make users aware of these quality of life improvements when they register/next visit Codeforces.

Constructive comments are appreciated!

Full text and comments »

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

By NovusStellachan, history, 11 months ago, In English

Hi, I'm a grade 11 student from (country reveal later) looking for someone who can train me in OI to IOI level. My current level is clear from my profile (?). I was a master at some point but I'm in a slump right now. I think my performance is usually like a CM? Except for a few bad contests here and there I think I usually manage a CM perf.

I have gone up to the national camp for OI twice in my country now, with the current year being my third attempt at making IOI team. If you are interested in training me yourself, or know someone who is looking for a student like me, please let them know about me/ reach out to me via CF PM. I would've given out my discord here, but seeing as this blog is public I'd like to avoid random discord DMs. My aims are getting an IOI medal and eventually reaching GM on CF.

Thanks, NovusStellachan

PS: I do math olympiads as well, and this year I represented my country at the IMO, winning a bronze medal.

Full text and comments »

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