By BledDest, history, 5 months ago, In English,

Hello Codeforces!

On June 29, 18:05 MSK Educational Codeforces Round 24 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours 15 minutes to solve them.

The problems were prepared by Mikhail PikMike Piklyaev, Alexey Perforator Ripinen and me.

Good luck to all participants!

I also have a message from Harbour.Space University about the ML course held at the university:

Nowadays machine learning technologies are widely used in practice in various applied fields such as retail, mass media, PR and marketing, banking, telecommunications, manufacturing, science and many other areas.

We are pleased to announce our Industrial Machine Learning course, aimed to teach the structure and the life cycle of the machine learning process and covers topics ranging from the problem statement to final quality assessment as well as estimation of the economic effect.

This course is taught by two Data Scientists from Yandex, Emeli Dral and Victor Kantor. Emeli Dral is the Head of Predictive Analysis, whereas Victor Kantor is the Head of User Behaviour Analysis Group at Yandex.

http://in.harbour.space/data-science/industrial-machine-learning/

They share with us their knowledge on everything from the most promising applications of data science today to applying the latest advancements in machine learning to your work.

UPD: The editorial can be found here.

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

»
5 months ago, # |
  Vote: I like it +48 Vote: I do not like it

Okay, CF on a hat-trick.

»
5 months ago, # |
  Vote: I like it -45 Vote: I do not like it

Is it not rated!

»
5 months ago, # |
  Vote: I like it +135 Vote: I do not like it

If they find a bug in the jury's solution does it mean that the contest becomes rated?

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

I would honestly not be surprised if at the end of this round they say it's rated.

»
5 months ago, # |
  Vote: I like it +75 Vote: I do not like it

I love educational rounds because they are announced unrated prior to the contest.

»
5 months ago, # |
  Vote: I like it -57 Vote: I do not like it

now we will presume all the rounds as unrated.....:D

»
5 months ago, # |
  Vote: I like it +107 Vote: I do not like it

BledDest's Educational Round from 18 to 23 are awesome. I learned something new on every round. Congratulation for your contribution to consecutive 7 Rounds in a row .

»
5 months ago, # |
  Vote: I like it -37 Vote: I do not like it

Less Enthusiasm to finish all 7 problems since it is unrated :|

»
5 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Read Statements of Problem 1,2 and 4. Most Unclear Problem Statements and Test Case Explanation.

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

    Yes, I am having a hard time figuring out what the question wants, this is really frustrating!

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Exactly. In first question, first of all they should mention that students who get diplomas cannot get certificates and vice versa. Also it should be diplomas OR certificates instead of AND. 2nd and 4th are even more unclear than the first

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Idk, for me it seems totally fine.

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Why am i getting TLE on 7th testcase on D. I think time complexity of this code is O(nlogn)

code:
  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Your Code complexity is not nlogn.

    I implemented the same idea as yours but efficiently without the while loop, you can view my solution here : 28150986

    UPD : The explanation is wrong, the cause of TLE is something else. See this

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

      well i think this soln is similar to mine and got AC 28144801

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      The while loop will erase elements atmost n times, coz i am always erasing previously inserted elements, so the time complexity is nlongn for insertion + nlogn for erasing n elements! Total time complexity: nlogn

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

        I am really sorry.

        You are right your code complexity is nlogn.

        I think what you are missing is to reinitialise flag = 0. Once your flag is set to it never becomes 0 again causing the while loop to run in every loop after that, hence causing TLE.

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

          Actually, i don't think reinitialise of flag is required. Once flag is is set while should run for every iteration. The point is while will never run more than n times, so won't cause any problem, even there is no need of flag in while's condition. 28156733 (submission without flag in while's condition) .

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

          Actually flag is not causing the TLE, the problem is after erasing the color, whe should update its hash in h[] array, coz it can't be part of ans anymore.

          AC code: 28157043

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WTF, I got AC in C and D, but didn't manage to do it in B...

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

    How to solve B? :/

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      a[l[i]]=(l[i + 1] — l[i] + n) % n; check if everything is ok.

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

        Yeah, i did the same

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

          So i think there's a bug in my solution

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

          What if a[i] contains two values?

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

          maybe the final permutation contains a 0???..that happened to me

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I used a map to ensure that each index gets one value only. If two index try to get the same value I return -1

      Finally, we try to assign each unassigned index an unassigned value. We can do this fast enough.

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

      Thanks, just got AC

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

    a[l[i]] should be the distance between l[i] and l[i + 1], and a should form permutation.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

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

    For every color contain if it can be B and its current cnt. When increasing cnt sompare it with cnt[A].

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      I guess complexity will be O(n2) then.

      • »
        »
        »
        »
        5 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        ignore.

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

        I mean considering that I have an array of say 10 elements and out of them 5 have value equal to A.

        The other 5 are different (unique) elements.

        So I will have to keep on comparing them with A`s indexes.

        This will become * =

        Am I correct?

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

          Yes, if for each B, you iterate through the whole array.

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

            So, is there any way to do in O(nlog(n))

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

              Yes, put the counts of all the possible Bs in priority queue and keep invalidating them as soon as possible. See my code.

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

        Here's my code: It's O(n + #colors).

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E?

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

E is kind a to easy for E,rather level of Div 1 B.It's just two pointer,and you could easlly hash with prime factors of numbers because number of prime factors of n is ,so baisicly I did nothing smart for this accepted,unlike some other E's where there is some beautiful observation.My 28153516

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Can D be done by 2 pointer? I couldn't implement it.

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    What is you 2 pointer approach? I tried it solving by always keeping set of possible answer for all positions, if at any position set is empty, print -1.

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

      For every color available store their indices and then compare them with indices of Alice's car find who will win how many times and if Alice's car looses then Bob can win by choosing that color.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I tried solving E using 2-pointers but was getting TLE on 16.

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

    D can be done in O(N).
    Code-28146537

»
5 months ago, # |
Rev. 2   Vote: I like it +30 Vote: I do not like it

Here is the Problem E on Hackerearth created by _AJ_ .

  • »
    »
    5 months ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    .

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    This problem's name is a very, very big irony.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    Oh, wow, I guess we were not that creative. Sorry, none of authors and testers heard about this one and we weren't able to google anything.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got WA at test 4 in both B and D I tried all possible test cases especially in D and I did't figure out what is wrong with my code ?

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

How to solve C? I used Cumulative sum trick for each direction.

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

    That's exactly what I did too. Plus you also need to consider that the same sofa would also be counted in two directions. For example, in cumulative sum,for say a sofa with coordinates 1 1 1 2 , the cumulative sum in up and down direction will also account for the same sofa you are querying for, but not in the left or right direction.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good round but I couldn't solve problem C...any help??Thanks in advance

  • »
    »
    5 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    C is just careful case-work if I'm not wrong.Use four arrays to store for every sofa its min x in 1st,max x in 2nd,min y in 3rd and max y in 4th.Sort all of them using counting sort,i.e you could count number of those whose value is z.Now use prefix sum,i.e count how many sofa s are there with min x less then some value r for every r<n.Now for every sofa use opposite value to count number of sofas in each direction,when we want to know number of sofas on left for sofa i,we use max x_{i} and yust use prefix sum we calculated.That's O(n).

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Problem E was very nice, can be done with simple algorithms. Thanks for such problems :)

»
5 months ago, # |
Rev. 3   Vote: I like it -14 Vote: I do not like it

problem A can be solvable using binary search . Equation is k*x+x<=n/2. Now search on x. Here x is number of diplomas. Here is my AC code : http://codeforces.com/contest/818/submission/28144078

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hack for A?

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

When you find a hack in your solution!

»
5 months ago, # |
Rev. 2   Vote: I like it +65 Vote: I do not like it

When you think you've used the same (maybe sub-optimal) algorithm as everyone, but the only solution you're able to hack is your own. :(

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Is really F so easy ?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell what is wrong in 28167345

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

    Integer overflow. You are storing values in long data types but they can exceed the maximum permissible limit.

    eg. If you have an array of length 100 in which all elements are 2, s[99] will supposedly store 2^100 which will overflow.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i am not able to understand the question B permutation game how many ever times i try to read it.i cant understand the test case explanation also..can some1 please help me regarding this??..thannk you

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I get All links to Educational Round?

»
4 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Good that's informative blog ! Songspk

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got judgement failed in problem G constantly.

How to solve it(?

Here is my submission -> 28719413

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great articles submitted. thanks for helping information. Naa Songs

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

mo_el

use this to solve problem A

include <bits/stdc++.h>

int n, x ; int a[330]; set < int > myset; int main() { cin >> n >> x; for(int i=0; i<n; i++) cin >> a[i]; for(int i=0; i<n; i++) myset.insert(a[i]); int ans = 0; for(int i=0; i<x; i++) { if (!myset.count(i)) { ans++; } } cout << ans << endl; }

»
2 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Your are submitted all time great articles. thanks for helping information Naa Songs