Top Recent Blog Posts
By tdpencil, history, 42 hours ago, In English

As tensions in the Middle East grow, I want to strongly remind everyone to stay respectful on the website. People are struggling right now and being insensitive will only make matters worse. Racism is racism — stereotypes are stereotypes, no matter if the person is Arabian, Jewish, White, Black, Hispanic / Latinx, Asian, or any other ethnic group. We are all people, with different dreams, aspirations, and hopes. Please, don't bring up issues that aren't needed to be brought up on a competitive programming website.

Thanks, Have an awesome day

Dwight (tdpencil)

Read more »

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

By mango_lassi, history, 18 hours ago, In English

I saw a blog (thanks to Bugman for finding it!) earlier today asking how to solve the following problem:

Given a linear function $$$ax + b$$$, find the minimum $$$x \geq 0$$$ such that $$$ax + b \in [L, R]\ (\text{mod } M)$$$.

To solve that problem, we can make the following reduction: If $$$gcd(a, M) > 1$$$, we divide everything by the GCD. The $$$x$$$ for which $$$ax + b = L\ (\text{mod } M)$$$ is $$$(L - b) a^{-1}\ (\text{mod } M)$$$. Denote this value by $$$b_0$$$. Then, the minimum $$$x$$$ to get to $$$L + y$$$ is $$$a^{-1} y + b_0\ (\text{mod } M)$$$. This gives us a reduced problem:

Find the minimum value of $$$ay + b \text{ mod } M$$$ over $$$y \leq k$$$.

This seemed pretty hard, but surprisingly I figured out how to do it in $$$\mathcal{O}(\log M)$$$ time! The algorithm is as follows:

In every step, we reduce the modulo from $$$M$$$ to $$$\min(a, M - a) \leq M / 2$$$. This guarantees we do at most $$$\mathcal{O}(\log M)$$$ steps.

To reduce it to $$$a$$$, we consider the first value $$$s$$$ among $$$[0, a)$$$ achieved by $$$ay + b$$$. If $$$b < a$$$, it is $$$b$$$. Otherwise, it is $$$b - M\text{ mod } a$$$. We check in $$$\mathcal{O}(1)$$$ if we reach $$$s$$$ for some $$$y \leq k$$$. If we do, set $$$M$$$ to $$$a$$$, $$$a$$$ to $$$-M \text{ mod } a$$$ and $$$b$$$ to $$$s$$$. Otherwise, output $$$b$$$ as the first $$$a$$$ values are the only values such that the previous value was larger, thus if we never attain them, the first value we attain is the largest we do.

To reduce it to $$$M - a$$$, we consider the first value $$$s = b \text{ mod } M - a$$$ among $$$[0, M - a)$$$ achieved by $$$ay + b$$$. If we reach $$$s$$$ for some $$$y \leq k$$$, set $$$M$$$ to $$$M - a$$$, $$$a$$$ to $$$a \text{ mod } M - a$$$ and $$$b$$$ to $$$s$$$. Otherwise, binary search the smallest value $$$b - t(M - a)$$$ that we attain for some $$$y \leq k$$$ and return it.

code

What I wanted to ask is, is this a known problem, and is there a simpler or perhaps even faster solution to it? The problem seems fairly simple, so I doubt nobody has thought about it before.

Read more »

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

By gabrielwu, history, 15 hours ago, In English

The Montgomery Blair HS Computer Team is proud to present the fourth iteration of the semi-annual Montgomery Blair Informatics Tournament (mBIT), which will be held online from 10:00 AM — 2:00 PM EDT on Saturday, June 12 (6/12/21). If you are interested in competing, please register at http://mbit.mbhs.edu/. The contest will be hosted on our personal servers at http://mbit.live/. All problems were written by the Montgomery Blair Computer Team, including 12tqian, gabrielwu, galen_colin, smax, meiron03, Blastman, alien_lover, czhang2718, and csytrn.

mBIT is split into two divisions: Standard and Advanced. Teams may choose which division to compete in. Standard division problems are roughly USACO Bronze to Silver difficulty, while Advanced division problems range from USACO Silver to Platinum. Most Standard problems could be found on a Div 3 contest or early on in a Div 2 contest. Advanced problems are more comparable to Div 1 (and more difficult Div 2) problems.

mBIT allows teams of up to 4 competitors! Anybody may compete, regardless of their age or country. There will be Amazon gift cards reserved for the top high school teams in both divisions, in addition to the top overall teams in the Advanced division. To qualify for "high school status," all members of your team must be current high school (or middle school) students.

Prizes (per person, subject to change):

  • $50, $25, $25 for the first, second, and third HS teams in Advanced

  • $25, $10, $10 for the first, second, and third overall teams in Advanced that are not among the top three HS teams

  • $25, $10 for the first HS team and first MS team in Standard

  • All prize winners will get a Wolfram|Alpha Pro subscription.

Here are the mBIT problems from our most recent contest last November:

All information, including problems from our other two contests, can be found on our website. Registration will remain open up until the day of the contest.

Message me or email [email protected] if you have any questions! We hope to see you compete!

mBIT is proudly sponsored by the amazing people at Wolfram Research!

Read more »

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

By geekypandey, history, 4 days ago, In English

What is this site?

cf-tracker is a website for monitoring progress on cf.yanyanlongxia.cn in terms on which questions were solved in contests.

There are two types of questions to keep track on:

  • The ones that were solved during the contest.
  • The ones that were not solved during or after the contest [problems to upsolve later].

It also provides feature to filter contests based on division [div1, div2, div3, Educational Rounds], and is pretty damn quick about it.

cf-tracker website

How can one use it?

  • To upsolve problems.
  • To find contests that you haven't participated in before and practice on them.
  • Filter contests based on divisions for practice.

How is this site built?

  • The site is built entirely using Vue.js.
  • It uses codeforces api for fetching information.
  • The contests information is statically stored as a json file, for improving the speed.
  • To update the contests information there is python script written.
  • The site is hosted using Github Pages.

Can I look at the source code?

Sure, the site is completely open-source. You can find it here.

What features are coming next on it?

  • To keep the search and filter bar of the top steady if when you scroll down.
  • Refresh button to get latest data on problems solved by the user.
  • Proper error message for user, in case the codeforces website is down.
  • Improve the UI.
  • Pagination of problems.

Suggestions to improve the website are always welcome. If any issues found please raise it on the github repository.

Thank you! Enjoy the site!

Update(13/5/2021):
  • Multiple handles supported.
Update(14/5/2021):
  • Problem solved count available now for each problem.
  • Refresh button for getting latest user submissions added.

Read more »

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

By thanhchauns2, history, 13 hours ago, In English

Given a map of a dungeon, your task is to take all TWO diamonds in the dungeon.

Find the minimum number of gates you have to open to take all the diamonds.

Note: It can be more than one gate to go into the dungeon from the outside.

You can move up, down, left, right.

About the map:

  • The letter '.' means blank space, you can move on it

  • The letter '*' means blockade, you have to go around it

  • The letter '#' means there's a gate at that place, you need it opened to go through it

  • The letter '$' means the diamond.

Input format:

  • First line is two number N and M — the dungeon has the size N*M. (2 ≤ N,M ≤ 100)

  • N lines following, represent the map of the dungeon.

Output format:

  • A single integer — the minimum number of gates you have to open.

Example input:

5 9

****#****

..#.#..

****.****

$$$#.#.#$$$


Sorry for the input, you can see read the input here : http://ideone.com/EXk0Wh

Example output:

4

Thank you guys, hope you have a great standing in the next contest.

Read more »

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

By honest_critic, 27 hours ago, In English

I was trying to search for Range queries problems for practice and I found that CF problemset doesn't have "Range Query" tag.

Problemset has tags like:

  • schedules — It has just 5 problems
  • chinese remainder theorem — It has 12 problems

And few others which are too specific or rare like meet in middle, expression parsing.

I don't understand why these topics have tag but range query doesn't. Is there any specific reason behind it?

Read more »

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

By chokudai, history, 4 hours ago, In English

We will hold Mynavi Programming Contest 2021(AtCoder Beginner Contest 201).

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

Read more »

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

By hmehta, 14 hours ago, In English

Rookie SRM 5

Rookie SRM 5 is scheduled to start at 07:00 UTC-4 on May 14, 2021

Registration is now open for the Rookie SRM in the Arena or Applet and closes at 06:55 UTC-5. The coding phase will start at 07:05 UTC-5, so make sure that you are all ready to go. Click here to what time it starts in your area.

The Rookie SRM is open to everyone and has some special cash prizes. It will only be **rated** for members who:
- Have never competed in Rated Algorithm Contests OR
- Have competed in equal to or less than 5 rounds OR
- If their current rating is less than **800** rating points.

Prizes:
Topcoder T-shirt for Top 20
*Prizes are only for members who are eligible to be rated

Best of luck!
- the Topcoder Team

Update on SRM 800, RSRM 3, and 4 T-shirts: We are ready to ship out the t-shirts for SRM 800, Rookie SRM 3, and 4, They will be going out next week. Sorry for the delay. Thanks for your patience!

Read more »

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

By _codedreamer_dg_, history, 6 hours ago, In English

Greetings Codeforces Community!

I hope you are healthy and staying indoors. I invite you to participate in CoderFest 1.O in collaboration with PSIT Kanpur, this Saturday, 15th May.

The contest features 6 problems of varying difficulty and is 3 hours long. It will be served with some delicious partially graded problems (IOI-Style) — where you get a score for passing certain test data, along with the details of the failed test cases, if any :slight_smile:

The problems in this round are prepared by @codedreamer_dg, @sethhritik, @hash16.

Contact: [email protected]

Huge thanks to entire CodeChef Team for their invaluable help and their great platform.

Good Luck!

Hope to see you participating!!

Happy Programming!!

PS: Editorial to the problems will be released soon after the contest ends.

Read more »

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

By rotavirus, history, 12 minutes ago, In English

Congratulations, Roman elizarov for being the first master filmed in a youtube advertisement!

Read more »

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