Hi everyone! IOI 2019 is almost finished and another unsuccessful/unlucky performance from me. Nevertheless, we still had a lot of opportunities to entertain ourselves (random example: pretending like a foreigner and mocking with Azerbaijani guides).

However, the most important event during the IOI (even more important than the actual contest :P) was converting our dull time in Azerbaijan Carpet Museum to pleasant one. We "shamelessly" hacked into an information device to interact with the Windows OS!

It's a common trick but that's how we did it: The device was showing some information and it had a touch screen. I immediately realized that it's Windows. Then we chose some text (we were lucky that the information was plain text) and hold the screen (that means right-click). After going to the properties menu (I don't know why it existed xD) the blue "?" symbol made us smile as it opened the internet explorer. The rest is, you know.

I wanted to continue the challenge of Golovanov399 and solved a problem using a fake account of my friend (and, yes, I write brackets in python xD).

Well, that's all from me. I'm a little sad about the thing I couldn't solve the problem shoes but anyways.

Congratulations to all the winners!

Hello, community! I wonder how plagiarism detectors are coded? I think CodeForces only checks for exactly same codes. Maybe it's time for community to help our admins to implement a good and reliable plagiarism detector. Actually, I have some ideas!

First of all, following idea does not work for problems with very little amount of code like Div2A or Div2B problems (even some harder ones).

The actual point is saving the order of main operations written in the code. By using the word main, I mean we need to ignore lines such as declaring variables or libraries. For example, let's take a code from this post.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 3e5 + 5;
vector<int> g[N];
int arr[N];
bool good[N];
int freq[N];

int main()
{
  ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++)
  {
    cin >> arr[i];
  }
  for(int j = 1; j <= m; j++)
  {
    int u, v;
    cin >> u >> v;
    g[v].push_back(u);
    if(v == arr[n])
      good[u] = 1;
  }
  int bad = 0;
  int have = 0;
  for(int i = n - 1; i >= 1; i--)
  {
    if(good[arr[i]] && freq[arr[i]] == bad)
    {
      have++;
    }
    else
    {
      bad++;
      for(auto &x: g[arr[i]])
        freq[x]++;
    }
  }
  cout << have;
  return 0;
}

For this code, our script generates this list:

input
loop {
  input
}
loop {
  input
  vector_pushback_operation
  if {
    equal_operation
  }
}
loop {
  if {
    inc_operation
  } else {
    inc_operation
    loop {
      inc_operation
    }
  }
}
output

Of course, this is a just rough idea and it must be improved to make a good detector. But guess what! These simple and ridiculous lines are EXACTLY SAME for all codes in the link aforementioned. I have some other ideas to improve this, but first, of course, your opinions are important for us.

So, what do you think? What are your suggestions? Will admins use our help? =))

Hello CodeForces. Today, I was solving AtCoder's 700 point problem and faced with an unfamiliar situation. After some analysis, surprisingly, I found that C++ reads the lines from the back.

For example, see this code: https://ideone.com/VHnIIj

I call the function "add1" before "add2" but it seems that the code reads it in reversed order.

I googled it and couldn't find any proper information about that. Can someone share his/her thoughts, please?

Edit; Thank you all for the response. It's clear to me now.

Hello CodeForces. I'm interested in BOI 2018 and looked into their site for information. As my country is not a Baltic country, I want to know if some countries can participate unofficially. Seems there is no any contact information on the link. Can one help us to get contact with BOI 2018 organizers? I already wrote to BOI 2017 organizer and got a reply that he is no longer organizer of the contest.

Hello Codeforces! Some months ago I wrote tutorial about basics of recurrent sequences. This blog, my second tutorial is about mine another favorite topic — Invariants and Monovariants. These are useful concepts which will help you solving problems, especially, constructive ones. Even if you are not familiar with this topics, I'm sure that you solved problems with use of invariants and monovariants without knowing it, continue reading, you will understand my point :) There will be hard problems which are based on old IMO problems, so I will try my best to explain solutions of examples.

So, what are Invariants and Monovariants? An invariant is a quantity that doesn't change. A monovariant is a quantity that changes monotically (that is, non-decreasing or non-increasing). Seems simple, yes?

Let's start with a few easy examples which you will better understand its point. I suggest you to try solving problems by your own before reading solution.

Hello, Codeforces. This year, our government has decided to fund us to participate in a few competitive programming camps for IOI style training. Therefore, we do need a list of training camps which are planned to be hold this year. If you have some info, please, share with us.

Alice and Bob are bored from playing Nim, so they modified that game — ArbiNim has been created just now. Rules of game is very simple:

1. There are k piles of stones such that there are a_i stones in i'th pile.

2. Alice and Bob are making moves alternatively, as Bob is gentlemen Alice starts first.

3. In each move, player selects one of non-empty piles and takes some of stones from that pile and throws away. From remaining stones (if there are) in selected pile, player takes any number of stones again and distributes them arbitrarily to non-empty piles.

4. The player who takes last stone wins.

Bob can be gentlemen and give some opportunities to his opponent Alice the optimal mover, but as we know, he is merciless in games, he will play optimal also!

Your task is determining winner of game, GAME ON!

P.S. If you know source of problem or some judge to submit, please mention it.

Hello Codeforces. I'm trying to solve this geometry problem, but seems I stuck :\ Please help me. Here is the statement:

Given N squares with integer coordinates on plane such that sides of each square is parallel to x/y axis. None of the squares are intersecting. Find how many squares we can see from (0, 0) coordinate. We can see square from O point when there are two different A and B points such that triangle OAB has no any intersection/touch point with other squares. 1 ≤ N ≤ 1000, squares are given to input with its left bottom side coordinates X, Y and its length of side L. (1 ≤ X, Y, L ≤ 10000).

Here is the original statement but only in Russian: http://informatika.edu.az/tasks.php?action=detail&id=150〈=ru

I draw picture of first sample for convenience, input is:

3
2 6 3
1 4 1
3 4 1

Obviously, we can see two little squares and drawn lines have no intersection points with these little squares so we can also see big square, therefore answer is 3.

Thanks in advance.

Let's discuss problems.

How to solve 2, 3, 6, 7, 11?

Hello everybody! Here is a problem which I can't find solution, help me please if you can. So, statement is simple:

Given n ≤ 40 and non-negative integer r < 2ⁿ. Find all integers k from 0 to 2ⁿ - 1 such that

Here is a link for problem if you want to submit: https://www.e-olymp.com/en/problems/322

Thanks in advance!

Hello Codeforces community! I decided to write tutorial about recurrent sequences, tutorial is about very basics of that topic. If you have little combinatorics knowledge, you will understand this tutorial easily. This is my first tutorial, so this can be easy for you and there can be mistakes. Probably all Div1 users knows all things in this tutorial :) Hope this tutorial will help you. If you have any questions/suggestions please write in comments.

Recurrent Sequences — Application of combinatorics in DP

Let’s start with a problem to this topic.

Problem. In how many different ways you can write 8 (+) and 5 (-) signs consecutively such that no two (-) signs are adjacent are adjacent.

Solution of problem is easy. Let’s write (+) signs after 9 ms:

m + m + m + m + m + m + m + m + m

Now let's change 5 of ms to (-) sign. Actually, problem has been solved, no 2 (-) signs are consecutive. So, answer is (because there are 9 ms and we have to choose 5 of them). Generally, if we have k (+) signs and r (-) signs, we can make sequences such that no two (-) signs are consecutive.

Problem. There are 10 signs are written on the board consecutively. How many different sequences we can create if some of them are (+) and some of them are (-) signs such that no two (-) signs are adjacent.

Let's think all situations:

With formula we found in previous problem answer is:

Generalized version of problem: If we have x signs which some of them are (+) and some of them are (-) signs, how many sequences we can create such that no two (-) signs are adjacent.

So, answer for this problem is

Let's write some few terms of S(n):

, , , , S(3) = 5, S(4) = 8, S(5) = 13 etc.

It remembered you something? Yes, Fibonacci numbers! Let's prove they are really Fibonacci numbers:

There are some proofs with Binet's formula, but we will prove this by strong induction:

We verified some first terms. Assume it is true for  - 1, 0, 1, .., n and we want to show that it is true for n + 1:

Problem. In how many different ways rabbit can go 10th step if it can jump 1 or 2 steps?

Well, we can solve this problem by analyzing some cases, but it will be hard way for calculating answer. So, let's think a little different. We can go 10th step from 9th step or 8th step, then answer for going 10th step is sum of answers for 9th step and 8th step. If F(n) is answer for going n'th step, we can calculate it by this recursive formula: F(n) = F(n - 1) + F(n - 2) with base cases F(1) = 1 and F(2) = 2.

Problem. (Hanoi towers) As you can see below there are 8 discs and 3 sticks. We can change places of discs with some rules: Only one disk can be moved at a time. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack. No disk may be placed on top of a smaller disk. Find minimum moves to move all discs to 3rd (left) stick.

For solving this problem, let's think little cases firstly. If we had 1 discs, we could solve problem in 1 step. If we had 2 discs, first we put little disc to middle stick, then big disc to left stick, then little disc to left stick, so in 3 moves we could do it. There is a gif for doing this for 3 discs:

So, if we have n discs, we can solve problem like this:

• Move (n-1) smaller than biggest discs to middle stick (*)

• Move biggest disc to 3rd (left) stick (**)

• Move (n-1) smaller than biggest discs to 3rd (left) stick (***)

We can't move biggest disc without taking other. If 3rd (left) stick is not empty, we can't put biggest on it. So, using this 2 facts it is the best strategy to solve problem. Let H(n) be answer for n discs. Then we can do (*) and (***) in H(n - 1) steps and (**) in 1 step. So, we can calculate H(n) by this recursive formula: .

So, we can solve this problem in O(n) easily. But, what about if n is very big, like n ≤ 10¹⁸, for this constraint we have to make faster algorithm. Let's write first few terms of H(n):

H(1) = 1, H(2) = 2 * H(1) + 1 = 3, H(3) = 2 * H(2) + 1 = 7, H(4) = 2 * H(3) + 1 = 15 etc.

It is not hard so see H(n) = 2ⁿ - 1, so let's prove it by induction:

1. We show it is correct for first few terms

2. Assume that H(n - 1) = 2^n - 1 - 1 and show H(n) = 2ⁿ - 1

Prove is done!

Problem. There is a park station such just Cadillac, Continental and Porsche (yeah, very expensive station) can park there. Cadillac and Continental are big cars, so they need 2 "car place" to park and Porsche needs 1 "car place" to park. If there are n "car places" in park station find out in how many different ways cars can park at station. (It is not important to park all types of cars).

Let P(n) be answer for n "car places". If Porsche parks at first "car place", answer for remaining (n-1) places is P(n - 1). If Cadillac parks at first two "car places", answer for remaining (n-2) places is P(n - 2) , same thing for Continental. So our recurrence relation is:

P(n) = P(n - 1) + 2 * P(n - 2) and bases cases are P(1) = 1 and P(2) = 3 (easy to show).

Challenge Problem. Write code which solves previous problem for n ≤ 10¹⁸ constraint.

Challenge Problem. n runners will do a race. Some runners can pass finish line at the same time, for example, 6th runner finished race 1st, 2nd and 5th runners finished race 2nd and other 3rd. How many different results of race can be there?

P.S. Finally, I finished this tutorial :) Writing tutorial is really hard. I'm really sorry for some mistakes, please write if you have question.

Hello, Codeforces!

There is a problem I couldn't solve which is from Turkish olympiad (Yeni Sistemli Kollege Olympiad in Informatics 2016 Semi-Final).

I have link of the problem, but you have to register into site to see problem: http://www.koduesi.com/en/Arena/Practice/14/1142

Here is statement of problem if you don't want to register:

It seems very standart problem, but I couldn't find it. Thanks in advance!

Hello Codeforces, I need your help.

Given rectangular table A with n rows and m columns. This table has n × m cells, numbered sequentially with positive integers from top to bottom, from left to right. A[i][j] is a cell of rectangular table A at the cross of i-th row and j-th column. For the given value of x the sympathetic table is a table A with values in the cells equal to x in power of number of the corresponding cell. More formally A[i][j] = x^{(i−1)∗m + j}.

Given q queries of rectangular borders x1, x2, y1, y2 and modulo p, the answer for such query is the sum of numbers in corresponding rectangle by modulo.

More formally, find:

For example, the sympathetic table A, 3 by 4 for a given x looks like:

Constraints:

1 ≤ n, m, x, p ≤ 10⁹

1 ≤ q ≤ 10⁴

1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m.

I spent much time for that problem, but I couldn't solve, please help me. Thanks in advance :)

Hello again Codeforces. I was looking ratings, and selected some organization for example IIIT Allahabad (selected this because there are many users, so there are more than 1 page). First page is okay, but when I try to enter page 2, it enters here, main ratings page 2 instead of page 2 of IIIT Allahabad organization. Is this happens to you too?

Hello, I was looking standings of Round #402 (Div 1), in page 3 I saw last guy (biGinNer), with 0 points, I just clicked his submission for first problem but it is just shows Pretests Passed. I checked solution, it got AC. Same for problem B (submission here). I just don't understand why this happened, is it bug?

Sorry for bad English.

There are N chords on circle. We know chords start degree and end degree. Find how many parts circle divided. Start of the coordinate system is located in center of the circle. 3 chords don't intersect at one point. Note: I made algorithm for that problem, but i couldn't write what i want. My algorithm: ans=n+1+(count of intersects of chords with each other). See image from link below. http://codeforces.com/predownloaded/83/53/83534d0e0c3e1c27cf0fb769066847d61e0660a1.png

Help me to solve this problem : Find minimal k which sum of k's digit's square equals to N where N<=5000. For example: if N=100 then k=68 || if N=345 then k=277999.

Note: I think this problem is DP, but i couldn't do it.

Have to find LCM of first N numbers where N<=1000. Help me please