Zlobober's blog

Codeforces Round #376 (Div. 2)
By Zlobober, 8 years ago, translation, In English

Hi everybody!

Tomorrow at 09:35 UTC there will be Codeforces Round #376 that is dedicated for the second division. At the same time there will be a Moscow School Team Olympiad, and, as a nice tradition, we bring you a CodeForces round based on its problems. Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants, but, as usual, we invite first division to participate unofficially in this round.

Problems were prepared by timgaripov, platypus179, wilwell, Flyrise, ipavlov and vintage_Vlad_Makeev under my control. We would like to thank members of jury of the Team Olympiad: Endagorion, Helen Andreeva and GlebsHP, who also works as a coordinator from the CodeForces side. Also we are very grateful to MikeMirzayanov for a Polygon system that makes problem preparation and coordination of many involved people much simpler, and for a great CodeForces community that we are all part of.

We suggest you 6 problems for 2 hours. Good luck!

UPD The contest is over, results are final, thanks for participating! The editorial will be published later

UPD2 I'm sorry for an editorial delay. It's finally available here.

Congratulations to contest winners:

  1. DmitryBelikov
  2. ljsss
  3. kehKeLenge
  4. dilsonguim
  5. UoA_Menma
  • Vote: I like it
  • +226
  • Vote: I do not like it

Comments Comments (223)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it +61 Vote: I do not like it

An automorphic Round (376)

376 * 376 = 141 376

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

Am I the last AC submission ?

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

Most of the schools are open at that time in Iran (and maybe other countries) :(

Missed four consecutive rounds just for the unusual time :(

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

    There would be people who have missed the usual timing rounds because it is "unusual" for them .

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

    It's your choice to live in Islamic country

    People believing in Jesus are free at Sundays

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

      you don't have to be rude !

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

        I didn't want to. Just pointed out how ridicilous is this argument, considering the fact that in most countries Sundays are holidays.

        It's impossible to fit in every schedule. That's why contest time changes. To fit other's schedules.

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

          I don't think " People believing in Jesus " is just pointing out !

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

            Actually I don't care much about what you think

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

              Actually you don't have to be rude at all

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

                If truth is too rude for you go meet with your therapist, you have plenty to talk about.

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

      there are too many christians in the middle east and the islamic countries -_-

      Not racist.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it -25 Vote: I do not like it

        Poor people...

        Also I didn't figure out how is racism relevant here. At my memory religions only fuels it, don't they?

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

      Codeforces should ban all the racist people, whatever their color is.

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

Am I the only one feeling tired of reading comments like "Unusual is the new usual"?

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

    you're not the only one. i can relate to this.

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

downvote me plz

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

I hate this new usual time :(

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

Most of the Middle East universities are open in this time :'(

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

Did anyone notice a sudden increase in contribution points? My contribution went from -30 to -3 in less than 3 days, without any wave of new upvotes.

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

In contest invitation mail Zlobober isn't legendary!

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

The time is very good for Chinese competitor.

But it is a pity that the beginning time of this round is just the ending time of Dalian regional contest.

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

In the registrants list, Div. 1 participants are not marked as unofficial participants. Is that normal?

Update: it's fixed, actually.

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

why div 1 participants are not unofficial ?

Update : fixed

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

    What part of "Unfortunately, this time we weren't able to come up with a good problemset for a first division contestants" do you find hard to understand?

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

The round starts 1.5 hours after Google APAC 1D ends.

Will have to eat quickly, rest in that time and be ready for the round. :D

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

    Oh boy, I literally dieded.

    I almost reached rank 200, but my computer hung at the last second and it costed me 16 points. Shouldn't have submitted the code after the contest, that was freakin painful.

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

Love the timing of recent contests. Usual timing is 2am for me, so am happy to actually be able to participate in a few contests.

But I understand that others may not agree :)

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

I'll join. It's my first time.

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

score distribution?

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

6 problems for 2 hours.Hopefully problem set will be easy at least 3.

Best wishes everyone.

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

10 minutes Late:)

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

Start delayed! How unusual!

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

Score distribution?

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

Why Delayed ?

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

I just don't get what is this problem which happens right in the begin of the contest and can be fixed in 10 minutes !

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

could some one say problem B more clear ? ! i cant understanr it : ( pleaseee ...

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

Problem B, Could He uses both coupons and discount at same time? like if it is 50 pizza, could he use 48 coupon and 1 discount?

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

    Well for B, you can use discount only if you are buying 2 that should solve it :| explanation sucks

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

    If he should buy 3 pizzas, he can buy 2 pizzas with discount and 1 pizza with coupon.

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

My submission for D is in queue for 5 mins. Still waiting.

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

Am I the only one feeling tired of reading comments like "Unusual is the new usual"?

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

i hacked on F with complexity n*n for n=10^5. It failed ! Does the new server support 10^10 ??
Edit: Got it ! My test case wasnt good enough !

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

How to solve C?

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

    Hint: think about DFS

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

    dsu i think

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

      I too thought of dsu, but it kept failing at pretest 5. Any reason why it might not work

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

      Can anyone illustarate smooth dsu solution

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

        build a graph with undirected edges from each l[i] and r[i].now socks at indices l[i] and r[i] must have same color.now use dfs to find the connected components.its just like a normal dfs on undirected graph with edges from l[i] to r[i].each connected component should have same color.after finding components,for each component find the color which exists the most number of times and paint all other socks with this color.this minimizes the required number of paintings.for reference you can see my code.21497227

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

          Damn, I spent about 1.5 hours on this problem and couldnt solve it. How do you guys think up these solutions? I understand it, and it is quite simple, but why does it actually work? "find the color which exists the most number of times and paint all other socks with this color.this minimizes the required number of paintings" — I understand that sometimes you just see the pattern and cant prove it, but how to see this pattern... :( I failed many problems just not being able to see the pattern. How can I improve this skill? Thanks in advance

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

            me too couldn't solve it during contest and i realized it later. I think it all comes with practice.

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

            From my practice experience, whenver I think of a strategy in a scenario I go through steps like this:

            1. Come up with preprocessing ways that helps you analyze the situation.

            2. If it's a game then most of the time it is minimax considering it is the most frequent one that pops up.

            3. Go for greedy, enumerate a few test cases that I think that could be tricky to handle. If greedy still works, then go for it.

            4. If not, see if there is a dynamic programming relation between the states. Go for dp if it is available.

            5. If there is still no solution, then you are probably missing some major observation. Dig deeper into the sample cases for inspirations. Also check if the constraints are small enough for more naive solutions to pass.

            → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +6 Vote: I do not like it

    Build a graph like this : If you have socks l[i], r[i], then add undirected edge from l[i] to r[i]. Now for each connected component in this graph, you must have 1 color. So we can solve each component independently. It's optimal for each component to change colours of all nodes in that component to the colour that appears the most in that component.

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

      I used DFS....as u said.. But someone hacked me.. How? here is my solution solution

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

        for(i = 1 ; i <= N ; i++){ if(visited[i] == 0){ for(j = 1 ; j <= K ; j++) countcolor[j] = 0; _max = 0; ll v = dfs(i); ans += (v-_max); } }

        It works only with a few components count. I guess if theres maximum N and M — min, for instance 1, this would be N*K, while N = 2*10^5 and K = 2*10^5, which is TL, obviously.

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

        you are looping through color array every time.here your worst case will be N*K.instead just use a map and you can clear the map every time you run dfs.

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

          shit.... This simple thing !!! I should have thought of that

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

    Consider socks as nodes and pairs as edges. Now in this graph,paint each component with the color which have highest frequency in that component.

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

      Could you tell me how to find the highest frequency in a independent component ?

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

        Dfs and store in map amount of each color.

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    For input
    5 3 5
    1 1 3 4 5
    1 2
    2 3
    4 5

    You can split all the socks into groups (sets):
    S1 = {sock1, sock2, sock3},
    S2 = {sock4, sock5}

    All the socks in group S1 should be painted in a single color and all the socks in the group S2 should also be painted in a single color (probably, different from the color of S1).

    For the group Si we count the most frequent color among the socks and paint all the rest socks in that group to that color. In my example the socks in the group S1 have following colors:
    S1 = {black, black, red}

    The most frequent color in group S1 is black, so we paint the remaining sock (which is red) to color black. After repainting the set will look like that:
    S1 = {black, black, black}.

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

How to solve F?

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

    Maybe you have to learn how to solve A and B, too early for F ..

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

      It seemed interesting, because for small constraints it works but I got TLE for large ones which means I was doing something really wrong. So I am interested in learning.

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

      Lets not judge just by looking at color of handle :)

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

    I used some prefix array to know in O(1) time how many graphic cards are there with power from i to j.

    Then for each available power of graphics, for example for power 2, i was checking prefix array every 2 (2,4,6,8) and i was increasing max result for this power by (cards in this interval)*(current value/power i was checking(2) ).

    O(nlogn)

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

    Consider every distinct tape as the leading tape and calculate the answer for this using sieve-like technique. Consider tape a[i], then all elements in range i*a[i] to (i+1)*a[i] will be added as i*a[i]. Number of elements between a range can be calculated using a precalculated array since the numbers are less 10^6.

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

please explain C I tried to do it bfs but it doesnt seem to be like that

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

    I did it using bfs, i made disjoint sets, and tried to find out the most repeated color in each disjoint set, and subtracted that value by size of the disjoint set.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -30 Vote: I do not like it 
      #include <stdio.h>
#include <map>
#include <queue>
#include <memory.h>
using namespace std;
int n, m, k;
int color[300000];
map<int, map<int, int> > tree;
map<int, map<int, int> > sorted;
int index[300000];
int index2[300000];
int visited[300000];
int cnt[300000];
int ans, p;

void bfs(int col, int s)
{
    queue<int> q;
    q.push(s);
    int i;
    while(!q.empty())
    {
        int now=q.front();
        visited[now]=col;
        sorted[col][index2[col]++]=now;
        q.pop();
        for(i=0; i<index[now]; i++) if(visited[tree[now][i]]==0) q.push(tree[now][i]);
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &n, &m, &k);
    int i, j;
    for(i=0; i<n; i++) scanf("%d", &color[i]);

    for(i=0; i<m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        tree[l][index[l]++]=r;
        tree[r][index[r]++]=l;
    }
    int cur=1;
    for(i=1; i<=n; i++)
    {
        if(visited[i]==0)
        {
            bfs(cur, i);
            cur++;
        }
    }
    for(i=1; i<cur; i++)
    {
        memset(cnt, 0, sizeof(cnt));
        p=0;
        for(j=0; j<index2[i]; j++)
        {
            printf("%d ",sorted[i][j]);
            cnt[color[sorted[i][j]]]++;
            if(p<cnt[color[sorted[i][j]]]) p=cnt[color[sorted[i][j]]];
        }
        ans+=index2[i]-p;
        printf("\n");
    }
    printf("%d", ans);
}

      this was my code, when i realized that it fails sample test 2 please help me what is wrong?

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

        Can u copy send link to your solution instead of copy code ? This seem inconvenience. sory fo my bad E =)

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    BFS works fine. The input is just not usual. For example, the input li = 10, ri = 42 may be repeated:
    10 42
    ...
    10 42

    this may lead you to insert 42 into adjacency list twice:
    adj[10].push_back(42);
    adj[10].push_back(42);

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

      That's why i prefer map<int, set> for adjacency list.

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

How did people use graph solution for problem C? What if graph is really dense ? It should go out of memory..

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

Was F easy or there are some tricky cases waiting in system testing

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

I will fail b because I declared N to 1e5 and not 2*1e5, horrible mistake but I'm wondering why pretest doesn't cover such case!

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

Very interesting round to me !

I saw a lot of random solutions for F and some greedy for E... It will be a lot of WAs.

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

Can F be solved with a fenwick tree, and summing contents of the intervals between each power? I think that is O(n (log n)^2), is that fast enough?

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

    You could use prefix sum from reverse to get the same and hence reduce a logn factor

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

    Oh wait you can just compute the prefix sum. That makes sense.

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

    my O(n log(n) ln(n)) solution passed. so I guess O(n log^2(n)) is fast enough.

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

How to solve F?

I noticed that the main card should be a prime, or 1.

Then I wrote a sieve and a map to insert a number along with its index (in sorted input) in the map for each of its prime factors.

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

    For each i, iterate over its multiples. If you are currently at x*i, all the numbers in the range [(x-1)*i, x*i) will have to be reduced to (x-1)*i. So, simply add the count of numbers in this range * (x-1)*i to current ans. Repeat for all i, and take max of these.

    Code

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

    why should the main card be prime ?

    Case :

    4

    4 6 12 36

    main card : 4

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

D was really interesting. I got AC it using BIT. First of all, ans can be in range [0, c - 1]. For every successive interval, I found what intervals can lead to correct sorting order(handled by L and R), and what intervals cannot(handled by BIT). I maintained the interval [L, R] that contains the answer, and also BIT stores what index cannot be our answer. Finally, for any L ≤ i ≤ R, if BIT allows this to be an answer, print it. Otherwise answer doesn't exists.

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

    But you got WA on system test 27!!

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

      Yups, did not get AC. Test cases aren't available as of now. So cant tell much about the reason.

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

      Most probably I forgot to add "return 0;" when I check whether L > R. So it would print  - 1 twice.

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

    I didn't notice intervals may split during contest. To mark invalid interval [l, r], I think f[l]++, f[r + 1]-- works.

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

Is the following approach for D right? I implemented this algorithm but it doesn't pass some pretests. Where is the mistake in this solution? Take two adjacent words, find the first position where letters are different. If the first letter is greater then we need to turn the wheel by minimum (c-a[i]) so that it becomes smaller than b[i]; if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. Store the maximum of the minimums and the minimum of the maximum and if the second value is less than the first then print "-1", else print the first value.

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

    I also did similar. However "if the second letter is greater then we can turn the wheel by maximum (c-b[i]) or else a[i] becomes greater. " This is incomplete. There is another case.

    Eg:

    5 -> 6 -> 7 -> 1

    7 -> 1 -> 2 -> 3

    (c = 7)

    As you see you could also rotate it 3 times and still ordered.

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

    i implemented this too, but there's a catch!

    Suppose n=2 ,c=6 1 2 1 3

    (the numbers are 2 and 3)

    Then according to the above logic you can turn max:3 times but if you turn 5 times it again becomes valid. Hope it clears the doubt!

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +11 Vote: I do not like it

    You have missed out cases.
    Let a be the char of the first word and b be that of the second word, at the first point of difference.

    If a < b, the valid range is [0, c-b] U [c+1-a, c].
    If a > b, the valid range is [c+1-a, c-b]

    Then from the valid ranges of all the pairs of adjacent words, you can choose any common value. If there is no point which is common to all the ranges, answer is not possible.

    Also, apart from these, if the second word is a prefix of the first one and is shorter than the first word, answer is not possible.

    Code

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

      Shouldn't the valid range for a<b be [0, c-b] U [c+1-a, c-1]. The problem statement expects an ans in [0, c-1] and the changes in c steps in fact reflect those that can be done 0 steps. Seems the test cases are weak.

      Code

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

        It doesn't matter since if [c] is available then [c%c=0] is also available, and the smallest solution always get chose first.

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

I used DSU for DIV2 C but I am getting TLE on pretest 6.http://mirror.codeforces.com/contest/731/submission/21488359

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

I solved the C problem with DFS, but I got TLE... How to optimize my code? http://mirror.codeforces.com/contest/731/submission/21484127 Or is it just recursive vs queue? XD

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

    If the graph is empty, your codes is O(N2), because of this:

    memset(colNow,0,sizeof colNow);
    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem isn't in dfs i think. But in 

    memset(colNow,0,sizeof col)

    Think when there are many connected components, it will get tle.

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

    In the worst case memset would be called 2*10^5 times , which is basically O(N^2) . Use a map instead .

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

    you can save the vertices that you go to them in dfs ,in a vector and after dfs make the colnow of them equal zero or dfs again and do it

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

kudos to the author for such a nice contest!

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

What's the idea for solving E ?

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

    What I did was this.

    Let DP[1][i] be the max score which can be obtained by Petya, if in his next turn he has to choose a prefix of length at least i and let DP[0][i] denote the same for Gena.
    Let S[j] denote prefix sum till j, i.e. arr[1]+arr[2]+arr[3]+...arr[j]
    Petya tries to get the maximum value possible and Gena tries to get the lowest value possible.

    DP[1][i] = max(S[j] + DP[0][j+1]), j>=i
    DP[0][i] = min(-S[j] + DP[1][j+1]), j>=i

    The answer is given by DP[1][2] (1-indexing is used).

    Code

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

    Dynamic Programming on prefix sum array

    check this:

    http://mirror.codeforces.com/contest/731/submission/21488865

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

      your solution is pretty good,it's easy for me to understand

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

    Let S[i] be the sum of the numbers from 1 to i.

    Let D[i] be the optimal maximum difference for the current player if the leftmost sticker contains the sum of the numbers from 1 to i.

    Then D[i] = max{S[j] — D[j]} for i < j <= N.

    But since S[j] — D[j] is independent of i, we can just keep track of the maximum S[j] — D[j] and update it at every loop, leading to O(N) solution.

    code: http://mirror.codeforces.com/contest/731/submission/21495276

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

      How you are taking account of the two persons , please elaborate?

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

        The best play for one person in a certain configuration is the same as the best play for the other.

        "Then D[i] = max{S[j] — D[j]} for i < j <= N"

        S[j] is what you get from choosing up until the sticker j

        D[j] is the best play on the configuration j

        So you choose the best play possible for every situation.

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

As I see, problem F easier than problem D & E, problem B easier to WA then problem F :)) funny contest

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

Hopefully become Expert:)

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

I think problem C can be interpreted in 2 ways.
1. Counting cost of colouring of both left and right pieces of i-th pair of socks as 2.(Counting colouring of each left and right sock seperately)
2. Counting cost of colouring of both left and right pieces of i-th pair of socks as 1.

During the contest, I have implemented assuming case:1, which failed on pretest 3.
After the contest, I see that I was supposed to assume the other case.

Here are my submissions with only difference being which assumption was considered among the above.
Assumption-1 : 21492459 Failed
Assumption-2 : 21493466 Accepted

Should have got this clarified during the contest :(

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

    You never have to color both the right and left sock though..

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

can someone identify the mistake in my submission for "C", i keep getting WA on 6.

code = http://mirror.codeforces.com/contest/731/submission/21492734

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

    Hope that comment helps.

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

      i tried a testcase with repeated indeces , it is giving correct output for that .

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

        Your code gives negative answer. That means the expression (size - maxi) sometimes is negative, that is sometimes size becomes smaller than maxi. You can try thinking backwards and work out an example when this is true.

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

    You use variable 'i' in two loops that are nested.

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

    It would anyways TLE , it is O(N*K)

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

Rating Updated!

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

Got TLE for C at test case 33 mysolution . I tried with DSU. Could somebody help?

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

    there's a small thing that needs to be considered .i think you are clearing the count array every time you run dfs.instead use a map and clear it.

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

Finally I'm Cyan !!, and I solved 3 problems from the first submission.
Self confidence is rising here !
thank you Zlobober very much for the nice contest

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

No hacks this time :-)

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

http://mirror.codeforces.com/contest/731/submission/21485811 WA in test case 66 :( Can anyone help ?

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

    Someone please point out the bug ... unable to find it ....

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

      In the last loop in main(), the upper bound for i should be m instead of n.

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

Why does this TLE for F ?

http://mirror.codeforces.com/contest/731/submission/21494655

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

    I also unintentionally did the same mistake...Since the values of array may not be distinct. So, we should avoid calculation for same elements , otherwise if we calculate for value say, 1 or 2, for many times, then this will lead to O(n*n)...I had sorted array, then was trying to escape repetition, but forgot to do that while coding,, finally, which causes TLE :( .

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

How do you solve problem B? I wrote "something" which passed the pretests but it doesn't work it some cases. What's the normal solution for this problem?

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

    Iterate from left to right . If arr[i] is even we can use coupons and we are done . But if arr[i] is odd , arr[i+1] should exist and should be positive . If not print NO else do arr[i+1] -= 1 .

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

      Thanks, that's so easy and obvious...I actually thought the same but then was misled by some example which I treated incorrectly.

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

anyone can find my code bug for problem C ????? I'm using DSU , calculating all socks needed minus the largest number of colors for every parent. http://mirror.codeforces.com/contest/731/submission/21491376

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

    What does the function join() return?

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

    You are coloring everything with the maximal color, not the color with maximal number in map( because pairs are sorted by the first element, not the second).

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

:'( F gave TLE on 26th test passed just by fast I/O Yeah Life is unfair!

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

I don't know why, but I found Problem B very tough (I solved it somehow though :P). Can anyone suggest a simple solution?

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

    Here is mine:

    • For i = 0...n-2 (skips the last) ---> if a[i] > 2 then a[i] %= 2 ---> after that, if a[i] == 1 and a[i + 1] == 1 then reduce both of them.

    The result is 'YES' if sum of remain elements in a is 0. Otherwise, it is 'NO'. Hope this helps.

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

    Break the array wherever 0 is present. Find sum of each part. Answer is YES if sum of each part is even.

    Code

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

There is something mystery in this contest for my case. My code for solving problem C returns 2 for Test 5, which is correct, on my computer. But when I upload the code, it became 3, which is wrong answer.

Because it's correct on my computer so that I have no idea where it went wrong. Please take a look: http://mirror.codeforces.com/contest/731/submission/21493963

Many thanks. P/S: Picture proof.

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

Nice round.. I think problem F was overrated ... it should have been a C or a D. however it was an interesting round. thanks

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

3 points from getting blue :C Anyways, can someone please tell me the solution for problem F?

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

    Let f(x) denote the number of integers that are  ≥ x. Then, if we fix a number i as leader, the total sum will be f(i) + f(2i) + f(3i) + ....

    We can precompute f(i) for all i ≤ 200000 by using the same method as sieving primes. The time complexity is .

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

      Interesting, I didn't think about that.

      If you don't precompute f(i) you can use binary search to find it, making the complexity O(n*logn*logn) but without the need to worry about precomputation.

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

      Very nice solution, thank you.

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

      Interesting solution :)

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

      I don't understand even if you precompute f(i) for all i<=200000, then also you have to sum it for i, 2i, 3i, ... (200000/i) elements. Why isn't it O(n^2). Here's my solution along the lines suggested by you, it's getting time limit exceeded and the reason I could think of is the above. Am I missing something.

      http://mirror.codeforces.com/contest/731/submission/21516249

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

        Make sure you don't visit the multiples that you have already visited and it should get accepted. You took care of the case with repeated ones but look at the one you got TLE'd (repeated twos)

        Edit: it is worth noting the reason why this is O(nlogn).

        If you don't visit the same number twice, it takes at most N+N/2+N/3+...+N/N.

        That's the same as N(1+1/2+1/3+...+1/N). That sum is bounded by ln (look for the integral of 1/x from 1 to n) so the complexity is O(n*logn).

        → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    deleted

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

Spent an hour and 2 wrong submissions on C because I thought you had to color socks dynamically every day and not just all of them at once beforehand. :D

Good thing I went and solved F before realizing how easy C actually was.

Just wondering, how to solve C if you can color socks dynamically?

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

anyone knows why my solution for c fails? http://mirror.codeforces.com/contest/731/submission/21498239

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

Can someone explain the solution to Problem D?

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

    Here is my approach:

    For each block i (0<=i<n-1), compare them in lexigographical order. It should fall under one of these cases: (Let j be the position where a[i] and a[i+1] differs)

    1. a[i] is a prefix of a[i+1] — Great! We don't have to do anything, a[i] < a[i+1] is always true.

    2. a[i+1] is a prefix of a[i] — Great! Now we are screwed! The door is always locked.

    3. a[i] is currently lexigographical smaller thatn a[i+1] — Then calculate when will a[i] and a[i+1] go through the cyclic shift at j. During the period where a[i+1] has gone through the cycle and a[i] haven't, a[i+1] will be smaller than a[i].

    4. the reverse of case 3 — We will also calculate the cyclic shift time. This time, only the period where a[i] has gone through the cyclic and a[i] haven't will allow us to open the door.

    You can see that there will be intervals where you can open (or not open) the doors. Now all you have to do is check for the earliest moment where you can open the door.

    (You can use the range fill technique to invalidate a time interval. See my code here http://mirror.codeforces.com/contest/731/submission/21498917 )

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

      Can u please elaborate the last part of your solution. Means how you are using the chk[] array to check for intervals where we can shift the lock ??

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

        Let's say we are counting the amount of intervals at a certain point. The most naive solution is to increament each of the points within the interval by one — but this takes O(n) time to mark each interval.

        Instead, we can increase the start of the interval by one, and the point near to its' end of it by one, and calculate the prefix sum after we have mark all intervals, and this will tell us how many intervals lie on a certain point. Why does this work? Consider each interval individually, the prefix sum will cause all points on interval [left,right] increase by one, yet since [right+1] has a value -1, therefore it gets canceled and the interval [right,n) remains uneffected.

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

mfw practicing and see F only have the "brute force" tag.

Dude What

nvm they fixed it. =]

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

I liked how none of the problems used complex data structure and algorithms.

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

quite surprised about the AC number of each problem.
I think E is quite easy, the idea is easy and very easy coding.
D is a little complicated to code, but the idea isn't hard.

F is hard for me, I didn't figure out a way by myself even after contest.

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

I hope for an editorial for this contest, as well as for Technocup.

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

plz upload the editorial!!!

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

I Can't get What is wrong on my solution... Solution I get Pretest Passed at 1:59.. but failed to pass Main test at Test22.

Please Let me know Why my solution is not working on this test case like 19999 10001 10002 10003 10004 ...

I solved The Problem F bruteforce. 1. sort input 2. from the small number to large number in the input, vec[1...n], Iterated if the mainpower key is v[i], if v[j] % v[i] == 0, pass. or not, v[j] -= v[j]%v[i] ( to make secondary power) 3. print the answer

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it 
    200000
100001 100002 ... 101000 200000 200000 ... 200000

    The answer is 200000 * 199000

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

    You should say, "I submitted The Problem F bruteforce" instead of saying, "I solved The Problem F bruteforce", since all of your submissions for F got WA!

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

i think there maybe some mistakes of problem F. the two same codes, the first code, define maxn=1000100,it AC;21510847. the second code, define maxn=200100,it WR on31;21510692.

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

21506585 — > What is my off by one error? :(

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

Could anyone comment the Problem E example 2?

input: 1 -7 -2 3
a)
turn 1: A takes 1 -7 -2, puts -8
turn 2: B takes -8 3
totals: A - B = (1 -7 -2) - (-8 + 3) = -3
b)
turn 1: A takes 1 -7, puts -6
turn 2: B takes -6 -2 3
totals: A - B = (1 -7) - (-6 -2 + 3) = -1

Why (a) is corrent answer? (b) is better than (a)!
→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    B is not playing optimally in b)

    turn 1: A takes 1 -7, puts -6

    turn 2: B takes -6 -2, puts -8

    turn 3: A takes -8 3, puts -5

    A's score: -6 + -5 = -11

    B's score: -8

    diff = -11 — -8 = -3

    Sometimes you can force a turn on others and thus reducing their scores. >=]

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    Could you dig a bit more please?
Why -8 in (1) is considered "optimal" but -21000 in (2) is not?
input 1: 1 -7 -2 3
input 2: -6000 -5000 -4000 -3000 -2000 -1000
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      optimal moves for input2:

      turn 1: A takes [1,5], S= -20000. turn 2: B takes [1,2], S= -21000.

      Difference in score= +1000

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

When will the editorials be up!?

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

Where is the tutorial?

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

@Zlobober Please add tutorial to the box names [→ Contest materials] on the righ_bottom of web-pages of the problems. Thank you.

→ Reply