savinov's blog

Codeforces Round #285
By savinov, 10 years ago, translation, In English

Hi, Codeforces!

Codeforces Round #285 will be held at 12 January, 12.00 MSK. Problems are authored by me, Evgeny Savinov. This is my first round at Codeforces. I hope that this isn't the last one.

I want to thank sokian and Golovanov399 for help in preparing and testing round, Zlobober for invaluable help in preparing round, AlexFetisov for testing round, Delinur for translating problem statements in English, and of course, MikeMirzayanov for great systems Codeforces and Polygon.

By the way, today(11 January) is MikeMirzayanov's birthday. Happy birthday, Mike!

The round will be for both divisions. Information about score distribution will be posted just before the round starts.

UPD1: Scoring system will be dynamic. Problems will be arranged in ascending expected difficulty order.

UPD2: The editorial can be found here. I'm sorry for the delay.

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

Comments Comments (108)
| Write comment?
»
10 years ago, # |
← Rev. 11   Vote: I like it -32 Vote: I do not like it

It's time is too early in our (Iranian students) timezone because we have to go to school.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    I think you already are.

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why this http://mirror.codeforces.com/contests/501,504

501,504??

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -34 Vote: I do not like it

85 is a holy number for Iranians :D

→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +55 Vote: I do not like it

Wow ... Mike's Birthday ... That's amazing ... :]


#include <iostream>
using namespace std;

int main ()
{
        cout << "Happy Birthday Mike ! \\:D/" << endl << "Thanks For Everything !!! :D" << endl;
        return 0;
}
→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Happy birthday MikeMirzayanov.

BTW it seems like tomorrow will be a busy day. Topcoder SRM 645 will take place 5 hours after the end of this round.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

Happy birthday MikeMirzayanov.

→ Reply
»
10 years ago, # |
  Vote: I like it -57 Vote: I do not like it

dis like me pls

→ Reply
»
10 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Information about score distribution will be posted just before the round starts.

Why for almost all contests score distribution reveled just before the contest? What happens if author(s) revel it early?

→ Reply
»
10 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Weird timing. Cannot participate due to classes. BTW Happy Birhtday MIKE!!

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

thanks :)

→ Reply
»
10 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Happy Birthday dear MikeMirzayanov.

Best wishes, from iran, Hamed

→ Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

The first round in 2015 :)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here in Venezuela Contest will take place at 4:30 a.m T_T i hope my alarm can wake me T_T

→ Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

new year starts , i want to enjoy it as much as possible....:)

→ Reply
»
10 years ago, # |
  Vote: I like it -22 Vote: I do not like it

Are the problems easy or hard?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

missed contest because of class :(

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

Hey savinov !
You can use this tag "Happy Birthday Mike ":)

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Score distribution?

→ Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I'm so happy that I catch the contest. It was a hurry that I went home from the school.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In Codeforces rounds, when two or more separate contests are going to be held, the contests numbers are given by separating with comma. How to detect which contest number belongs to which one? e.g.: Today, two separate contests are scheduled for two divisions in round #285 and the contest link is: http://mirror.codeforces.com/contests/501,504. Now, my question is which division belongs to 501? is there any general way to know this for any round before its started? I think, MikeMirzayanov could say the exact answer.Thanks in advance.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe it was scheduled to be a div2 only contest, and a contest was scheduled after it, and then it was made for both division?

    just a guess.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you may check the URL of list of registered lists.

    → Reply
»
10 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Oh no, dynamic scoring(((

→ Reply
»
10 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Why????????

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You should had registered to contest using 'register' link in contest list. Not everybody always participates, so system should know who wants to generate rooms.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in first 10 minutes i was 5th...

But now I'm 260th...

Why I can't never solve C???? :(

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    In first 10 minutes I was 3) And now 349 :(

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      And also now you are 1200 :)

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Yes( I write 250/p instead of p/250 :( It's very very sad(

        → Reply
»
10 years ago, # |
  Vote: I like it +158 Vote: I do not like it

It's a very bad idea to give numbers in decimal in D :(

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was the aproach to task C?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Since the graph is guaranteed to be acyclic, it is a forest and hence it has a leaf. Find one such leaf v. Its neighbor-XOR-sum is the XOR of a single number (the label of its sole neighbor u), so we know there is an edge between v and u. Now decrement u's degree count and XOR u's neighbor-XOR-sum by v (this means removing v from the forest), rinse and repeat.

    To avoid O(n2) time, store the leaves in a stack/queue. After a first pass through the vertices, you will only add at most one vertex at any given time (if u above has degree two, u itself is added to the stack).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The moment, when you thought that in input vertices can be shuffled.

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It is similar to topological sorting

    → Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve problem D/B ( Div2/Div1 ) . thanx in advance :)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    http://en.wikipedia.org/wiki/Factorial_number_system

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've used a similar approach.

      However, I could only transform the permutation into a factoradic sequence in a quick way, but not vice versa.

      Any good approaches? Thanks much!

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        What first comes to mind is a data structure that can find the k-th smallest element stored in it. I used a binary indexed tree in composition with binary search. From what I see after skimming some of the solutions that was a common approach. The total time complexity is .

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        You can use binary search.

        → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      My submission 9414663 used this factorial number system but TLE'd. Is there an implementation that could make my program faster or is it because I used Python (which is slow)?

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        list.remove is O(n).

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        You used decimal in your math.factorial(x) line. The trick is to avoid conversion to the decimal system and compute everything in factoradic directly.

        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        Guess how long it takes to compute math.factorial(200000), and repeat this 200000 times.

        Yes, your algorithm runs in at least time. You have to find a faster algorithm.

        On the other hand, my solution got TLE too in Python, so yes, you also need to move to a faster language.

        → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Hi,

I find the English version of problem C's description is confusing: " XOR sum of the numbers of vertices adjacent to v ..."

I can only understand it, after look at the Russian version: "XOR-сумма номеров вершин, смежных с v ..."

Seems like google translate did bad job :D

PS: I am out of this round, so I comment here. Good luck for your final rank!

EDITED: The statement should be: " XOR sum of the indexes of vertices adjacent to v ..."

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    The XOR sum of numbers a1, a2, ..., an is simply a1 ^ a2 ^ ...  ^ an; everything XORed together.

    Although yes, "the XOR sum of the numbers of vertices adjacent to v" might be better phrased as "the XOR sum of the labels of vertices adjacent to v".

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can somebody please explain to me the second test case for C problem? Thanks in advance.

2
1 1
1 0

Note: (From problem statement) ...were the first integer is the number of vertices adjacent to vertex v, and the second integer is the XOR sum of the numbers of vertices adjacent to v...

No idea what second integer means. I do not understand why if both vertex have the same adjacent vertex number then the second number is different.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There are 2 verticles (0 and 1) with the only edge between them, so for zero verticle degree=1 and xor of 1 is equal to 1, for the second — degree=1 and xor of 0 is equal to 0.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    There is an edge between vertex 0 and vertex 1.

    so for vertex 0, degree = 1, and XOR sum = 1 (vertex 1 is the only adjacent vertex)

    for vertex 1, degree = 1, and XOR sum = 0 (vertex 0 is the only adjacent vertex)

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    second integer means the XOR sum of the numbers on the adjacent vertexes, not the number of adjacent vertexes.

    For example, if a vertex 0 is adjacent to vertex 1, vertex 2, and vertex 4, then the second integer for vertex 0 is "1 ^ 2 ^ 4 = 7"

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "were the first integer is the number of vertices adjacent to vertex v"

    "the number of vertices" means the amount of vertices, connected to this vertex.

    I think it's a shortage of the translation.

    → Reply
»
10 years ago, # |
  Vote: I like it +198 Vote: I do not like it

Am I the only one that thinks that number of interesting problems in that contest equals 0 :/? Though E was interesting a bit, but also pretty tedious to code, but I didn't find anything interesting in BCD, especially D which was "change decimal to binary and do some Gauss", pls. Sorry to say that.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +163 Vote: I do not like it

    I have the same opinion.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    I found problem Div1-A/Div2-C pretty interesting and funny (maybe because our skills differ too much).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +87 Vote: I do not like it

      I was finding it interesting for quite a while — until I noticed it was a forest ;)

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Wow, when writing that comment I expected lots of minuses, because that's what hating posts usually get, but people seem to agree with me :P.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      Well, usually when I see some downvoted hating post, it sounds like "I got TL on B, why did you set such a small limit? And I also got WA on C because of overflow, why there are no overflow cases in pretests? And I totally screwed up today, so this contest is awful".

      And today I tried this round, because I've missed live edition; after that I opened comments, saw your message and thought "yeah, he is completely right...". This is the difference between that "usually" and this case.

      → Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

What was the approach for Div 1 C?

Only observation that I could make is following.

For a fixed index i, let us say there exists an index j s.t. if we can make the entire array an valid palindrome by shuffling values of array from index range [i, j], then we can also do the same for any range [i, k] where k > j. This idea can be used to do binary search over j.

But I had doubts about how to check whether shuffling of current range [i, j] can make the entire array palindrome or not?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This, actually, was my exact observation as well. And I have the same question; though I believe I worked out one of the two possible cases..

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 5   Vote: I like it +13 Vote: I do not like it

      it can be done without bin_search:

      i = 1
j = 1
while(i <= n) {
 while(i > j || !is_it_a_good_range(i,j)) {
  ++j;
  update_set_with_bad_numbers(j);
  update_set_with_bad_numbers(n+1-j);
 }
 update_set_with_bad_numbers(i);
 update_set_with_bad_numbers(n+1-i);
 ++i;
}

      How can we check given range? For every position 'p' in our range:

      1) we increase count[t[p]]

      2) if n+1-p is outside this range, we decrease count[t[n+1-p]] (unless 'p' is a middle position in whole array)

      In std::set let's have numbers such that count[a] is odd or negative (I call them "bad" numbers). A range is good if everything is ok outside range and:

      1) our set is empty, or

      2) our set has one number and count[this number] is positive odd number (it is possible only for odd n)

      → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    If you observe more, you would found that there are only twe basic range. Let a[1+k] != a[n-k] and for every i < k, a[1+i] == a[n-i]. So the two basic range is [1+k, g] and [h, n-k]. so you don't need to binary and just iterte over g and h.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't understand. For a string 22134 We can rearrange range [0, 2], but not [0, 3]...

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      You are rearranging a segment, but the entire string should become a palindrome.

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

I guess we can say that the Div. 2 3rd place account I_have_many_girlfriends (which was likely a Div. 2 account) is a cheater (because he has many girlfriends) :P

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +45 Vote: I do not like it

    Which would not be very surprising because one cannot have many girlfriends without cheating on them.

    → Reply
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think there is problem about Div1.D and E's time limit. After solved C, I found that the basic solutions for both problems are possible to get TLE. An solution O(n^3 / 64) for C and an solution O(mlogn^2) for E. But the O(n^3 / 64) for C get Ac and O(mlogn^2) for E get TLE. So unfair to someone just as me choose E to solve~

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    My solution needs time, solutions with bigger complexity shouldn't pass.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +133 Vote: I do not like it

Just learnt how reading bignums and asking about j-th bit looks in Java ;

BigInteger x = new BigInteger(in.next());
x.testBit(j);

And in C++?????

Great idea to give them in decimal, that task was surely equally hard to Java and C++ coders.

→ Reply
»
10 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Whenever the system testing is fast, the rating updates are slow! :D Whenever the system testing is slow, the rating updates are fast!

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

epic bug =\ this code passed 7 tests ...

set<int>::iterator it = s.lower_bound(x);
s.erase(it);
upd(*it);
→ Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it -16 Vote: I do not like it

thanks savinov :)
your contest has nice problem :)

→ Reply
»
10 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Approach for problem B.

(Explanation from adurysk)

Finding order of a permutation in a factorial representation
You can represent the order of any permutation like this. If a[0...n-1] is the given array, let la[0...n-1] be another array in which la[i] stores number of j such that j > i and a[j] < a[i] now the order of permutation a[0...n-1] will be la[0] * (n-1)! + la[1] * (n-2)! + la[2] * (n-3)! +.....you can see that la[i] < n — i similarly you can calculate the array lb[i] for the permutation b[0...n-1] now sum these two to get lc[i] = la[i] + lb[i] now at some index lc[i] can be greater than n — i, you can avoid this by shifting the carry to the index i — 1 and reconstruct the array c.

Getting permutation C from the lc array.
This part should be pretty easy. Go from left to right. Let us consider the situation in the beginning. At index 0, our value lc[0] denotes that precisely lc[0] numbers are less than our number at current index. So we can directly say that current number will be lc[0] + 1. So if we go to next index, we need to remember this assignment done at index 0. For that we can maintain a set of remaining numbers in permutation of size n. Now we need to find lc[i]^th the number in this set. This way we can extend the approach for any index i > 0.

We can use BIT for maintaining the required set.

Note: By set, I mean a mathematical notation of set, Don't confuse it with set in STL.

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what is the intuition behind adding lc[i]=la[i]+lb[i]? even if we add these then it will contain n+1 numbers right?

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What was the approach for Div 1 D?

→ Reply
»
10 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Wow, dreamoon_love_AA back to red in no time. Congrats!

→ Reply
»
10 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Does anyone have properly commented solution to div1 B (it would be nice if codeforces allowed us to sort searches by the "comment concentration" of code)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    When competitive programming, people aren't bothered to put comments.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In almost all solutions of Div.2 D / Div.1 B I see magical operation x -= x & (-x) on integer x. Maybe someone can tell what is the meaning of it? And by the way, what is the data structure used? Where can I learn more about it? For me it doesn't look exactly like a segment tree.

→ Reply
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What are the detailed aproaches to all questions by the writer?

→ Reply
»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Why no congratulations on the winners like in other rounds? :(

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codechef is busy doing Hackercup, I guess. :P Server is down.

→ Reply