Sharon's blog

By Sharon, history, 10 months ago, In English

We got an AI to generate programming problems, after being trained for hundreds of hours on problem 4A. (This is what we used to train it: https://colab.research.google.com/drive/1gWn1uN4cULoDnBJTSGqrUxxao5q3xHeI)

We omitted samples, time limits, and memory limits because they don't make much sense.

Here are the funniest results:

<|title|>
E. Back to the Future
<|time-limit|>
4 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
After escaping from the crashed time machine, Marty McFly was transported to present-time! He landed on the lawn where his damaged car was parked. He was given the coordinates of the car's location x y.
Marty quickly recognized that this car park is located at a distance of 1 meter from the starting position x, and its maximum speed is v. He also noticed that the car's navigation system is malfunctioning. For some inexplicable reason the system tells Marty that the distance between a pair of stationary objects is the sum of the car's speed.
Marty is not able to understand this. Why does the car choose such an arbitrary location. Help Marty.
<|input-specification|>
The first line contains two integers x and y (1 ≤ x, y ≤ 100) — the initial coordinates of Marty's car.
The second line contains a single integer v (0 ≤ v ≤ 100) — the maximum speed of the navigation system.
<|output_specification|>
Print a single integer — the number of stationary objects that will be able to reach the starting position x.

========================

<|title|>
B. Batch Sort
<|time-limit|>
1 second
<|memory-limit|>
256 megabytes
<|problem-text|>
Mikhail and Peter are good friends. They always have a problem to discuss. Masha asked Peter for a graph as a birthday present. Peter gave her the graph. Then he suddenly died. Masha has been trying to construct a graph since, well, he died. She wants to construct a graph like Peter.
Masha has a sequence

========================

<|title|>
E. Marina and a Bit of a Jerkass
<|time-limit|>
1.5 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
While walking down the street Marina saw a huge number of assholes walking in a row. Asshole number i has ai assholes facing him (each of these assholes has a number ai assholes facing him). Marina decided to follow them and start a fight. 
She starts walking with her k-th asshat in a row and nicknames him uppercut. Namely, Marina puts her asshat number i, then nick "umac" and nick "x". When she nick "umac" she also removes all the asshat with number ai who is facing her, she also nick "x" and all the asshat with number ai who is facing her in the end.
Now Marina wants to end up with a new asshat asshat. To do this, she nick "x" and nick "y". When she nick "x" she also removes the asshat with number ai who is facing the current asshat.
Even though Marina wants to end up with a new asshat, she worries that people will think she is crazy if and only if she becomes pregnant. So Marina wants to know what is the smallest number of assholes she has to replace or say that she will be okay with the resulting situation.
<|input-specification|>
The first line contains a single integer n (1 ≤ n ≤ 106) — the number of assholes.
Asshole number i is named ai in the input. It is guaranteed that all the assholes are distinct.
<|output_specification|>
Print a single integer — the minimum number of assholes that Marina can replace or say that she will be okay with the resulting situation.

========================

<|problem-text|>
Let's assume that 
Find .
<|input-specification|>
The first line contains one integer number $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$).
<|output_specification|>
Print one integer number: the sum of the digits of pi.

========================

<|title|>
E. A Twisty Movement
<|time-limit|>
1 second
<|memory-limit|>
256 megabytes
<|problem-text|>
A dragon symbolizes wisdom and wealth. On Lunar New Year's Day, people will invoke the dragon once to represent wealth.
A flock of eels symbolizes wisdom and wealth. On Lunar New Year's Day, people will invoke the dragon once to represent wisdom.
A tiger symbolizes innocence and strength. On Lunar New Year's Day, people will invoke the tiger once to represent strength.
None of the eels is a virgin, so when the dragon says "Lala la la la," she should immediately turn her back to the dragon.
The dragon will say "AaA" (Arabic root of  - 1) if he saw some of her shining red spots on the Day. Aa means Red spot.
You will be given q events of one of the following types:
Namely, let's say the position of the eels at the moment of time 0. Let's say that the location of the i-th eel is considered to be a rectangle with vertices at the points (0, 0), (100, 0), (100, ∞). The Dragon will say that the i-th eel is at the point with coordinates (xi, 0). Then he will then say that he will move to this point with speed v1, and will move to the point with coordinates (0, ∞). The Dragon will say that a beautiful girl named Lala appears at this point with speed v2. From the position of the eels at the moment of time 0, he will then say that he will fly to the point with coordinates (xi, yi).
The speed of the dragon is equal to the distance he has traveled in the corresponding direction. The moment of time 0 will be integer. It is guaranteed that the dragon will not be angry and will fly to exactly the point with the coordinates ( - 1, 0), where he will hide.
Lala is a very friendly dragon, so she will gladly fly to any point with integer coordinates, even 0. However, she hates close calls, so if the dragon calls her while flying to some point with integer coordinates she will promptly turn him

========================

<|title|>
Vasya's Revenge
<|time-limit|>
1 second
<|memory-limit|>
256 megabytes
<|problem-text|>
Vasya likes to play his own version of the game. He plays a board on a table. Players move in turns, the player who can move first moves first.
The board has n rows numbered from left to right. The cells of the board are numbered from left to right, and the rows are numbered from left to bottom. Each cell is represented by a number from 1 to n, inclusive.
Vasya is playing a game. There are m characters on the board, each character is either "A", "E", or "U". The board has a left cell (the character "A") and a right cell (the character "E") (not necessarily distinct).
In his turn, Vasya moves to the cell (x, y) and plays a card. He can play a card from the cell (x, y) to the cell (x, y + 1).
You have to make as few cards as possible in your turn. You can put a card anywhere on the board, but it can't be placed on the cell (x, y).
Vasya is allowed to play cards from the board without paying a cost, but he is not allowed to play cards from the board on the table.
Consider that there are m cards in the deck. Vasya has an empty hand. Vasya can't play any cards from the deck.
Vasya's hand contains only two cards, the first card is card "E", the second card is card "U". Vasya can play any of his cards (he can't play any other card).
Vasya's opponent is playing a game. Here is how the game is played.
In the game, Vasya plays two cards. First Vasya plays a card with the character (n, w). Then Vasya plays a card with the character (m, w). Vasya's opponent plays a card with the character (k, m). Vasya can play the first card at any cell (x, y). Vasya can't play the second card.
Vasya's opponent has an empty hand. Vasya can play any card from the opponent's hand. 
Your task is to determine whether Vasya's opponent can play any cards from the opponent's hand.
<|input-specification|>
The first line contains a single integer m (1 ≤ m ≤ 105) — the number of cards in Vasya's opponent's hand. The second line contains m integers x, y (1 ≤ x, y ≤ 106), where x and y are the cell numbers on the left and the right side of the board.
The third line contains a single integer w (1 ≤ w ≤ 106) — the number of cards in Vasya's opponent's hand. The fourth line contains w integers x1, y1 (1 ≤ x1, y1 ≤ 106), where x1 and y1 are the cell numbers on the top and the bottom of the board.
<|output_specification|>
Print "YES", if Vasya's opponent can play any cards from the opponent's hand. Otherwise, print "NO".

The most "solvable" problems:

<|title|>
A. Palindrome
<|time-limit|>
2 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
You are given a string $$$t_1, t_2, \dots, t_n$$$, consisting of lowercase Latin letters.
A substring of some string $$$s$$$ is called a palindrome if it reads the same from left to right and from right to left.
For example, the strings "asdf" and "klm" are palindromes, while the strings "abb" and "iq" are not.
If $$$t_i = t_{i+1}$$$ and $$$r_i = t_{i+2}$$$ then the string $$$s$$$ is a palindrome, but the string $$$t_j = q_{i+1}$$$ is not a palindrome.
For example, the strings "aaa", "arctg", "arudg" are not palindromes, while the strings "abacaba", "jjw". and "xzy" are.
Your task is to calculate the number of non-empty substrings of $$$t_i$$$ that are palindromes.
<|input-specification|>
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 500$$$) — the length of the string $$$t_i$$$.
The second line contains the string $$$t_i$$$ itself, consisting of $$$n$$$ lowercase Latin letters.
<|output_specification|>
Print a single integer — the number of non-empty substrings of $$$t_i$$$ that are palindromes.

==============

<|title|>
E. Primes and Multiplication
<|time-limit|>
2 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
Seyyed an integer sequence s1, s2, ..., sn of length n and m queries on it. Each query is represented by two integers li, ri (1 ≤ li ≤ ri ≤ n) and a integer x (0 ≤ x ≤ 1018). 
After each query you need to calculate the maximum value of an expression which can be found in the sequence s. In this problem expression means the remainder of division of number x by number s.
<|input-specification|>
The first line of the input contains integer n (1 ≤ n ≤ 105) — the length of the sequence s.
The second line contains n integers s1, s2, ..., sn (0 ≤ si ≤ 1018).
<|output_specification|>
Print m lines. For each query, print the maximum value of an expression that can be found in the sequence s after the corresponding query.

==============

<|title|>
A. Three Friends
<|time-limit|>
2 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
Three friends, Alan, Bob and Carol are good friends. That's why, if someone is not nice to Bob, he likes it. If someone is not nice to Carol, she hates it. And if someone is not nice to Alan, she hates it. 
You are given a list of the preferences of each friend. Determine if Bob is going to be upset by the news. If he is going to be upset, find the number of those friends who are going to be upset. Bob is going to be upset if only these friends are nice to him. Otherwise, no one is upset.
<|input-specification|>
The first line contains a single integer n (3 ≤ n ≤ 5·105) — the number of friends.
<|output_specification|>
Print the list of friends who are going to be upset by the news. If Bob is going to be upset, print -1.

==============

<|title|>
C. Number representation
<|time-limit|>
4 seconds
<|memory-limit|>
256 megabytes
<|problem-text|>
You are given a sequence of integers a1, a2, ..., an.
Your task is to perform the following operation k times: take any two different subsequences (of unequal length) in the given order and swap their contents. After each operation, you need to calculate the total number of times the sequence is modified.
<|input-specification|>
The first line contains one integer n (1 ≤ n ≤ 105) — the length of the sequence. The second line contains n integers a1, a2, ..., an (|ai| ≤ 109).
<|output_specification|>
Print n numbers — the modified sequence after k swaps.

We hope you enjoyed. If you run out of problem ideas and need to write a contest, I suggest you use this method of generating problems.

Read more »

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

By Sharon, history, 13 months ago, In English

While waiting for my late teammate blockingthesky (please spam him and tell him to get over here) to start a virtual participation of a Gym, I was trying to select a good problem set to run. I accidentally selected SEERC 2017, and my other teammate shamed me for selecting a bad contest. Someone else in the room suggested the idea of having upvotes and downvotes for a contest so you can see how people feel about the quality of the problems. This will help select good contests for virtual participation.

If you guys liked SEERC, you should harass I_Love_AuroraGarden in PMs.

How do you guys feel about this idea?

Read more »

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

By Sharon, history, 13 months ago, In English

Since the practice is tomorrow, I'm drawing a list of teams attending it.

I already know everyone, so there is no need to comment with their names.

North America

Count Country University Member 1 Member 2 Member 3 Team Rating
1 USA University of Central Florida SecondThread AuroraGarden Ahmad [2415]
2 USA University of Central Florida blockingthesky I_Love_AuroraGarden Sharon [2116]
3 USA University of Central Florida jwozniak BiIIy warez80 [2060]
4 USA University of Central Florida Derino Xylenox UnknownOne [2054]
5 USA University of Central Florida peach Dylan_Lyon surajsingireddy [2016]
6 USA University of Central Florida TheLurkingStarman flapjackie Ellie_K [1840]
7 USA University of Central Florida brettfazio gouh9qn Zangyiwu [1752]

Update: Scoring distribution has been released! 1-1-1-1-1-1-1-1-1-1

Read more »

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

By Sharon, history, 20 months ago, In English

DISCLAIMER: DO NOT READ THIS POST IF YOU ARE IN PORTUGAL FOR WORLD FINALS OR LIVE IN THE EUROPEAN UNION

Attention World Finalists:

As you may know, Article 13 has been voted on by the European Union and all memes are now illegal. It is imperative that when you travel to Portugal you must LEAVE YOUR MEMES AT HOME, or they will be deleted at airport security and you will be arrested.

The contents of this post must be viewed at your own risk.

European-SFW mode:
Normal mode:

Read more »

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

By Sharon, history, 23 months ago, In English

I am removing my contest proposal from Codeforces.

Note: This is a serious blog post. Also, the opinions presented in this blog are my own and not of my friend BiIIy who wrote the contest with me.

Today I have removed my contest proposal from Codeforces. I should probably have done this a long time ago. The proposal was made in February, but the problems were written and finished by March, and that is when I opened the contest proposal for review and messaged KAN. It is currently December and no progress or development has been made regarding my contest proposal since, so I will be removing it.

I have multiple reasons for removing my contest proposal:

  • I have no motivation to host an online contest anymore.

  • I am involved in problem setting with two other high school programming contests in my university, and I write, host, and judge another contest for local high schools.

  • I have forgotten that I “was in the queue” for writing a Codeforces contest anyway.

  • Codeforces is not motivated to work with me.

  • Codeforces does not communicate.

Codeforces is one of the biggest, most important, and most influential platforms in competitive programming so I think it should be held to a high standard. My main motivation writing this blog post is to let other aspiring problem setters know of my experience, and so that Codeforces will look for ways to improve their system for the new year. Specifically, I request Codeforces to be more transparent and honest with those of us waiting in line.

My experience with problem setting for Codeforces is as follows:

  • Some time in February, Billy and I decide that we want to host a Codeforces contest.

  • Between then and the end of March, we write five problems that we think would make a good Div2 round. When we finished the set, we opened the contest for review and I messaged KAN.

  • In May I decide I can write a better B problem so, since I’ve had no response yet, I wrote it and added it to the contest.

  • Sometime in July this guy writes a blog, I comment on it (click on the link and see context), which attracts the attention of Codechef, and they ask me to send them my problems to them. I do, and they reply quickly with some criticism of the problems. However, at the time I was abroad and school season began, so I decide to give up on writing a contest for the time being.

  • That guy with the blog was able to host a contest. I assume that is because he had a Div1 contest ready, which may be in higher demand. This is OK… But time continues to pass without any kind of communication from Codeforces. As I was already uninterested in hosting anymore, this is probably when I should have removed my proposal.

  • October 28th, KAN writes back. This is the only thing I hear from them.

  • November 7th, I get a comment on (just) one of the problems from 300iq. (image) (For context: in this problem I describe a mincost maxflow solution. I do not think that the feedback I received is useful feedback) I am still not sure what that comment means. No matter, I won’t hear from him again.

Fast forward to today.

I hope to bring these issues to light so that we can have conversation. Currently there are very few posts on this website that provide information regarding contest writing. It is possible that Codeforces simply gives priority to already trusted problem setters and will only use new problem setters as a last resort. I believe Codeforces should not waste our time. It should not take you months to comment on 5 simple problems, provided to you in the most abridged form (as you ask), unless you literally have hundreds of competitions in the queue. If that were the case, Codeforces should make an announcement – “Hey everyone, there are hundreds of contest proposals and it is impossible for our small team to review them all. We will not be looking for any new contest proposals for….” some estimated time.

When I used to try and look up information about Codeforces contest setting, such as what should my expectations be? how long does it take? etc. I could not find anything. Hopefully now, when some other problem setter wishes to learn what I wanted to know they will find this blog.

I will make some suggestions for Codeforces, I hope the team reads these and comments. Ultimately, it is their decision what action to take regarding my complaint. Every reasoning for my arguments is based on assumption. I could not possibly know what happens behind the scenes because Codeforces does not communicate. Therefore, some of these suggestions may be invalid.

My suggestions are as follows:

  1. Codeforces should be more transparent. Some people write poor contests. Their problems may be poorly thought out, vague, uncreative, obvious, or they may have an anime protagonist. In these cases, Codeforces should reply immediately with the issue.

  2. Codeforces may, at some point in time, have too many proposals from novice problem setters. It is perfectly reasonable for Codeforces to be honest and turn away some of these problem setters. It’s like hiring for a job: you have no obligation to hire somebody unqualified. However, it is the company’s ethical and respectful obligation to reply to them promptly and reject the contest proposal. It is a proposal after all.

  3. If Codeforces has too many contest proposals in the queue, they should make an announcement. Something that will let people know that their contest may take longer than usual to be reviewed.

  4. Codeforces should have two separate queues. One for Div1+Div2, and one for Div2 (maybe one for Div3, if Codeforces wishes to allow people to write problems for these in the future). Once you open your contest for review, you should be able to see your position in the queue. This way you can see how long you may have to wait.

  5. When a contest is finally assigned a person to review it, that person should review it promptly. Two months to review five problems, as has happened to me, is absurd. Even then, I only got very vague feedback on a single problem! Concerns, criticism, and compliments (if applicable) should be given to each problem, so that if work needs to be done, the problem setter can get started.

There may be more issues with the system. I wouldn’t know. It took me nine months and I only made it this far.

I have two purposes writing this blog. One is that I hope that Codeforces will look for ways to improve the contest writing system the coming year, and two is to enlighten some other novice problem setters who are still waiting in line for their chance to write their first Codeforces contest by sharing my experiences. The second reason is why I am making a public blog post rather than just PMing Mike, and by making a blog I think it is more likely to attract attention to the issue at hand. By no means is my intention to publicly shame anyone mentioned in this blog.

To reiterate, I do not wish to hold a Codeforces contest anymore, so I am not asking for Codeforces to review my problems. I do ask that Codeforces does not use my problems in a contest without my permission, and that the content of the problems be kept confidential. I may return to contest writing for Codeforces in the future, but not unless changes are made. (At this rate you could have a child before you can have a contest). If you are a new problem setter I would recommend considering Codechef, they respond much faster.

Lastly, it is undeniable that Codeforces is a fantastic competitive programming platform. It is one of the best things to happen to competitive programming period, and it does wonders to the community. I personally owe a huge portion of my programming skill to this website, and I want to see its success continue. It is by far the website I use most frequently in competitive programming. The work that MikeMirzayanov and the team does is admirable, and Codeforces makes tremendous progress every year as the contest programming scene grows. I have great respect for the Codeforces team and I hope that this criticism is not taken negatively. Like I said before, Codeforces should seek to meet a high standard, and it should be more communicative with aspiring problem writers. Otherwise, why even give the ability to propose a contest to all Experts+?

I hope to see a response from the team which will address some of these issues, and that Codeforces will work to make a better experience for contest writers in the coming year.

Read more »

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

By Sharon, history, 2 years ago, In English

The Introduction

On March 32nd of this year I created a blog post to share some new coding techniques that are quite easy to code and serve as very powerful optimizations (Context: https://codeforces.com/blog/entry/58667).

Now of course I know I single-handedly transformed the competitive programming meta as problems had to be done according to new standards now that it is possible to make O(N) code work O(1). Super fast. However, I have to share an upsetting discovery that I made. This blog post might be too sad for you, so discretion is advised. I have added certain checkpoints within this post where you can take a break if you get too sad and you may resume reading later. I have also added some cute pictures of animals to help out with your sadness.

The Story

It all started yesterday, when I used my usual O(1) trick to O(N) trick on problem E2 from the last contest (It seems that Mirzayanov has not adapted his problem statements to the trick, so his problems were quite easy. However maybe since this was a Div3 contest that was his intention). Now, it is easy to see that O(1) solution will easily pass within 3 seconds.

However, it did not: https://codeforces.com/contest/1005/submission/40208578

How is it possible to get a Time Limit Exceeded in O(1)? Clearly wrong answer, runtime error, memory limit whatever. These are all possibilities, but TLE? It makes no sense. Especially since the intended solution described in the editorial is O(N), and O(1) is so much faster. I even used Jolty Scanner, which literally makes TLE verdict impossible.

Anyway I dismissed this verdict. Maybe it was an issue with the servers being overloaded causing the judge to be slower. I said to myself I'll just submit the same code later, and it will surely work. So I went to the well known forum called reddit and started browsing the "programmerhumor" subreddit, where only the most super serious programmers have their most super serious discussions... Which may turn out to be the worst mistake I have ever made in my life.

A user (whose username will be omitted in order to protect him) answered the question I had in mind without me ever posting it, as if by divine providence. He made the preposterous claim that O(1) time is linear.

Because graphing y = 1 is a line.

Now surely that is ridiculous, right? y = 1 couldn't possibly be a line. y = n is a line, but not y = 1. y = 1 has to be a point. Otherwise, that means my O(N) to O(1) trick is wrong, because O(1) is O(N). And I cannot be wrong. In fact, I've never been wrong before, even about things I don't know. People would come ask me, "Sharon, does this cute girl love me?" and in my head I'm like, "How would I know, I don't even know who she is and I've never talked to her." But I would respond with either yes or no, and whatever I said ended up becoming true. Anyway the point is this reddit user is clearly wrong.

But the thought could not escape my mind. What if he was right? Then it made sense that I got TLE on that earlier problem. So I researched it using math and science to make the scariest of all discoveries. I went on my graphing calculator and...

I'm sure you understand the consequences of this and some of you are crying right now...

SADNESS BREAK

O(1) is O(N) + Apology + Consequence

I would now like to apologize for spreading false information... Though I was a victim of this as much as you were. I know you are all disappointed with me. I know you are all angry with me. But I can assure you that none of you are more disappointed and angry with me than I am with myself. This discovery has affected me at a deeply personal level, and I had to share it with Codeforces out of a burning desire to make things right in the world.

Now the fact that O(1) is equal to O(N), rather than it being the other way around, will have some dire consequences on computer science as a whole. It means we can't do things quite as fast as we could before, but if you stick around I have a solution for you later. However, there a problem that is potentially more problematic which could cause problems.

Consider the equation:

O(1) = O(N) //divide both sides by O( )

1 = N

Now consider the age old problem in computer science:

P =? NP //plug in value for N

P =? 1P

P = P

This pretty much confirms the P = NP problem. Every problem can now be solved in polynomial time. This is very problematic!!! Maybe you are thinking "Sweet, now I can solve TSP in O(N^2) or even O(N)!" I say maybe, but now people can hack your passwords in O(N)! Time to delete Facebook everyone.

For those who are very attached to their Facebook you can have a:

SADNESS BREAK

Anyway we must move onto biometric locks for our online accounts. Now I would like to present another trick, perhaps the best trick and solution that will fix the problem of not being able to code in O(1) anymore. Coders and codermen, I present to you:

The Binary Search Trick (The Compensation)

This blog post has been long and very mathematical, and this will be the last part, I promise. This trick will solve all the newly raised issues. Yes, we cannot solve in O(1) anymore. But we can get very very close. The fastest time we can use to compute something is O(logN). Everyone knows binary search works by dividing the range in half every time, which achieves a log base 2 of N runtime. Here is a typical binary search code, courtesy of geeksforgeeks:

// Returns index of x if it is present in arr[], 
    // else return -1
    int binarySearch(int arr[], int x)
    {
        int l = 0, r = arr.length - 1;
        while (l <= r)
        {
            int m = l + (r-l)/2; //THIS LINE IS THE MOST IMPORTANT!!!!!! NOTICE DIVISION BY 2
 
            // Check if x is present at mid
            if (arr[m] == x)
                return m;
 
            // If x greater, ignore left half
            if (arr[m] < x)
                l = m + 1;
 
            // If x is smaller, ignore right half
            else
                r = m - 1;
        }
 
        // if we reach here, then element was 
        // not present
        return -1;
    }

Take a look at line labelled as important above. What do you think would happen if instead of dividing by 2, we would divide instead by 3, or 5, or 1000, or 10000000, or 999999999999999999999999999999999999999999999999999999999999999999999999999999?

That is correct. It will terminate faster. In order to prove it we return to the graphing calculator.

Notice how the amount of operations gets smaller for large N for logarithms of a higher base. This is pretty much all the proof we need to show that binary search can be improved upon. We don't write the base of a logarithm in Big O notation, which leads many rookie programmers to ignore the fact that large base logs run faster in practice than smaller bases. So yes, maybe O(1) is O(N), so we can't code in O(1) anymore. But we can get very close to true O(1) computation by using the binary search trick and dividing by a large number.

This blog post was longer than I intended it to be, but I am glad we managed to finish it on a bright note of hope for computer scientists worldwide. Thank you Codeforces. You have been an incredible community and I wish you all high rating. Ask me questions if you have any. I would love to answer them. I love algorithm analysis and I know I do an incredible job at it, and I would love to keep this discussion going so that we may learn from intellectual discourse.

-Sharon

Read more »

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

By Sharon, history, 3 years ago, In English

It is currently 12:00AM, March 32nd. I was digging through the deep web and I found out about a couple tricks that legendary grandmasters have been using on this website for ages, though it was kept secret from the rest of humanity. These tricks are too dangerous for dangerous people to know (Kim Jong Un if you are reading this please stop). However, I am personally sick of the inequality and I think it is time to let the world know the secrets to make your programs run super fast.

Trick 1: The O(N) to O(1) trick.

Consider this problem. The bounds are clearly too large for an O(N) solution (looping from L to R). However, what if I told you that you could easily modify your O(N) code to make it O(1)?

Consider this piece of code:

long sum = 0;
for(long i = 0; i < N; i++){
   sum += i;
}

We can clearly see that for large N, such as 10^18, the program will take a long time to run. BUT!!! We can turn every linear time algorithm into constant time by considering the maximum value of N (which is always given by problemsetters in the description in Codeforces). Here is the SAME code, but in constant time.

long sum = 0;
for(long i = 0; i < 1000000000000000000L; i++){
   sum += i;
}

Now with your new knowledge, you can solve the problem above.

Trick 2: Thread.Sleep, a trick for the Java folks that are sick and tired of C++'s supremacy.

Now, you are reading this trick and thinking I am crazy. Sharon, how is it possible? Do you even know how to program? Thread.Sleep() slows your program down... It literally stops the program for the amount of time that you specify.

Now, I don't blame you for getting confused. I was too, originally. Until I found out you can manipulate the laws of the universe using this function to make your program run faster, like magic!

Here is what I mean. Have you ever considered passing a negative integer as an argument to that method? I bet you have not. What do you think it does? Well, we can follow simple logical reasoning. When we plug in a positive integer, the program stops for that amount of time. Therefore, when we plug in a negative number, the program should stop for a negative amount of time. In order to do that, it must start earlier, therefore faster, so the whole program runs faster!

Here is an example program:

import java.util.*;

public class R468A {

	public static void main(String[] args) {
		Thread.Sleep(-99999999999999999999999999999999999999999999999999999999999999999999999999999999999999);
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		if(a > b){
			int temp = b;
			b = a;
			a = temp;
		}
		long ans = 0;
		long t1 = 0;
		long t2 = 0;
		
		while(a < b){
			//System.out.println(a+" "+b);
			t1++;
			a++;
			ans += t1;
			if(a == b) break;
			b--;
			t2++;
			ans += t2;
		}
		System.out.println(ans);
	}
}


When you run this program, you will see that it terminates nearly instantly. This is the true power of the Thread.Sleep trick.

Anyway, I hope you enjoy my tutorial and that it will provide you with many AC solutions and high rating. I will be on the lookout for more weird tricks and I will make sure to share them as I find any.

Read more »

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