TheScrasse's blog

By TheScrasse, history, 11 days ago, In English

As promised, here are some (nested) hints for Codeforces Round #682 (Div. 2).

1438A - Specific Tastes of Andre

Hint 1

1438B - Valerii Against Everyone

Hint 1

1438C - Engineer Artem

Hint 1

1438D - Powerful Ksenia

Hint 1

I wasn't able to solve E and F. If you did, you may want to add your hints in the comments.

Also, please send a feedback if the hints are unclear or if they spoil the solution too much.

Read more »

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

By TheScrasse, history, 3 weeks ago, In English

Hello everyone,

inspired by Looking for a Challenge, I was thinking about publishing periodically (maybe every month) a selection of about 10 problems of various difficulties (from 1500 to 2400) from the Codeforces problemset, with hints and a detailed explanation of the solution. I will try to:

  • choose "good" problems: avoid putting too many ad-hoc problems, avoid putting problems that require lengthy data structures;
  • write the tutorial as accurately as possible: of course I won't copy-paste the official editorial, instead I will try to follow the thinking process "problem -> solution".

Do you think this is a good idea? (or is it "yet another editorial"?) How should I publish the problems? (pdf? blog on codeforces?) Do you have any suggestions?

UPD1: I would like to put problems that you've not solved yet. If you're interested, please compile this form with your Codeforces handle. By using the Codeforces API, I will minimize problems that you've already solved.

UPD2: after reading the comments, I thought for a long time about what to do and I asked myself if my idea makes sense. In particular:

  • selection of good problems: most problems in recent contests are good, most good problems are in recent contests.
  • editorials: sometimes the order of the ideas can appear confusing but, if the problem isn't much harder than your current level, you should come up with the solution by using the editorial + the comment section + solutions by other people.

So I'm not sure about the usefulness of writing new editorials to past problems.

Instead, I will write nested hints (of the problems that I have solved) after the end of each contest, and I will try to publish them immediately after the contest: I think they are much more useful, in fact they are often asked in the comment section.

Read more »

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

By TheScrasse, history, 4 months ago, In English

Hello,
I'm just curious to know if you have ever failed a system test, and what was the problem in your code.
I have failed a system test twice.

1) 1312C - Adding Powers, submission 72808639 (wrong answer on test 44)
Here is part of my code:

cin >> t;
while (t--) {
    s = 0;
    // [...]
    while (s != 0) {
        c = 0;
        // [...]
    }
    if (c == 2) {
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}

What's the reason of my wrong answer? If at the end of a testcase c is equal to 2 and in the next testcase s == 0, I don't enter the second while loop and c remains equal to 2! Instead, I should have reset c before entering the second while.
In fact, my solution got wa on the test

2
2 9
0 18
4 100
0 0 0 0

In the second testcase, output should have been YES, but my code printed NO because the sum s of the given integers was equal to 0 and c remained equal to 2.

2) 1334D - Minimum Euler Cycle, submission 76160539 (wrong answer on test 19)
My code was really messy, I still don't know what's the reason of the wrong answer.

And you? Have you ever failed a system test (or have you been hacked) because of some silly reason?

Read more »

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

By TheScrasse, history, 5 months ago, In English

Hi everyone,

many people are a bit disappointed because, for example, while the most difficult problems of Div. 3 contests are still interesting for Div. 2, Div. 3 contests are unrated for higher divisions. The same argument is valid for Div. 2 and Div. 4 contests.

An idea could be make contests rated for everyone, but that's not the best solution because, to reach a $$$\geq 1900$$$ rating, solving Div. 3 and Div. 4 problems very fast would be enough.

An improvement could be make contests partially rated for higher divisions, that is, the rating variation is multiplied by a $$$k$$$ factor ($$$0 \leq k \leq 1$$$) that depends on the target division of the contest and on the initial rating of the contestant (i. e. the relevance of that contest for that contestant). An example: there's a Div. 2 contest, then $$$k$$$ could be $$$1$$$ for a $$$1900$$$ rated contestant, $$$0.8$$$ for a $$$2100$$$ rated contestant, $$$0.5$$$ for a $$$2200$$$ rated contestant, etc.

Read more »

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

By TheScrasse, history, 6 months ago, In English

Hello,
I noticed that I often overcomplicate problems, hence my codes are often very long and I lose precious time during contests.
Some examples:
70077990 I wrote a sliding window minimum, but it wasn't necessary since $$$O(n^2)$$$ is fast enough with those constraints.
79841706 I found a solution that required too much memory. My "optimization" is 90 lines long. That problem can be solved in 30 lines.
79880987 I used a dfs and a 0-1 bfs (120 lines), a single bfs was enough.
Overall, I find difficult to improve a solution that seems already feasible.
Could you give some advice about how to stop overcomplicating problems?

Read more »

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

By TheScrasse, history, 6 months ago, In English

I can't submit solutions to any problem. This error appears: HTTP Status 403 – Forbidden
UPD: nvm, now I can submit, but there is a long queue

Read more »

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

By TheScrasse, history, 7 months ago, In English

Hello, I think 1343E - Weights Distributing wasn't a very difficult task, and now it's been solved by almost 2000 people. So, why is it worth 2400 points on the Problemset? How is the difficulty of a problem calculated?

Read more »

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

By TheScrasse, history, 7 months ago, In English

Hello everyone,
I have just tried to execute this code:

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"

long long n;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    ifstream cin("output.txt");
    ofstream cout("output.txt");

    cout << 0 << endl;
    while (cin >> n) {
        cout << n + 1 << endl;
    }

    return 0;
}

(note ifstream cin("output.txt");)
The output is

0

Shouldn't this code enter an infinite loop? cin >> n should be always true because the code has written a new line on output.txt.

Read more »

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

By TheScrasse, history, 8 months ago, In English

Hi everyone, I have just tried to solve the problem 161D.
If I use a matrix dp[50010][510], I get a tle verdict, even if the time complexity of the solution is $$$O(nk)$$$, $$$nk < 10^8$$$ and the constant factors are quite small. But if I use a matrix dp[510][50010] and I swap the indices, I get ac with a time of 498 ms (much less than the time limit).
Why does it happen?
Thanks

Submission with tle verdict: 73781168
Submission with ac verdict: 73781989

Read more »

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