Educational Codeforces Round 24

Привет, Codeforces!

29 июня в 18:05 по Москве начнётся Educational Codeforces Round 24.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа 15 минут. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной готовили Михаил awoo Пикляев и Алексей Perforator Рипинен.

Удачи в раунде! Успешных решений!

Также у меня есть сообщение от Harbour.Space University о проводимых в университете курсах машинного обучения:

Сегодня технологии машинного обучения находят практическое применение в самых разных сферах — в продажах, СМИ, PR и маркетинге, банковских технологиях, телекоммуникациях, производстве, науке и многом другом.

Мы рады анонсировать наши курсы промышленного машинного обучения, направленные на изучение структуры и жизненного цикла процессов машинного обучения и охватывающие самые разные темы, связанные с машинным обучением, от постановки задачи и до заключительных проверок качества, в том числе и оценку экономического эффекта.

Курсы проводятся двумя научными сотрудниками из Яндекса, Эмели Драль и Виктором Кантором. Эмели Драль — руководитель отдела предсказательной аналитики, а Виктор Кантор — руководитель группы анализа поведения пользователей в Яндексе.

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

Они делятся с нами своими знаниями в самых разных вопросах, от самых многообещающих приложений в этой сфере на данный момент до применения последних достижений машинного обучения в работе.

UPD: Разбор задач.

Комментарии (76)

Показать архивные | Написать комментарий?

ankububble

7 лет назад, # |

+48

Okay, CF on a hat-trick.

→ Ответить

Sorryforpartyrocking

-45

Is it not rated!

omidazadi

7 лет назад, # ^ |

-14

tkhkhkhkhkhkhkkhkh :|

VLamarca

+135

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

cpaudyal

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

mohitrbhardwaj

+75

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

khatribiru

+107

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 .

Zrj

-37

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

dbhrockzz

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

CaptainDaVinci

← Rev. 2 →

Indeed.

+19

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

Len

Idk, for me it seems totally fine.

hmrockstar

-6

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

code:


// <3 Appy!
#include "bits/stdc++.h"
using namespace std;
typedef unsigned long long ull;
typedef long long int ll;
typedef vector<long long int> vi;
int a[(int)1e6+9], h[(int)1e6+9];
int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    int n, sum = 0, count = 0, m, flag = 0, ans = 0, k, p;
    cin>>n>>p;
    set<pair<int,int> > s;
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        if(x == p)
            flag = 1;
        if(flag == 0)
            h[x] = 1;
        a[x]++;
        if(h[x] == 1)
        {
            if(a[x] == 1)
                s.insert({1,x});
            else
            {
                s.erase(s.find({a[x]-1,x}));
                s.insert({a[x],x});
            }
        }
        while(flag == 1 && !s.empty() && (*(s.begin())).first < a[p])
                s.erase(s.begin());
        if(flag == 1 && s.empty())
        {
            cout<<-1;
            return 0;
        }
    }
    if(s.empty())
    {
        cout<<-1;
        return 0;
    }
    cout<<(*(s.begin())).second;
    return 0;
}

priyanshupkm

← Rev. 3 →

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

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

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

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.

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) .

born.kira

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

madn

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

How to solve B? :/

Tutis

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

Yeah, i did the same

So i think there's a bug in my solution

What if a[i] contains two values?

For example l[]={3, 5, 3, 6}

albeXL

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

Thanks, just got AC

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

OneClickAC

How to solve D?

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

I guess complexity will be O(n²) then.

ignore.

Am I right, then?

I just realised that my solution is different.

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 $\text{[math]}$ * $\text{[math]}$ = $\text{[math]}$

Am I correct?

satyaki3794

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

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

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

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

rishi_07

How to solve E?

Two pointers, to check if segment is divisible, factor the k, and keep count of each prime.

Darui99

+13

The most simple solution is binary search with segment tree of multiplication modulo k

submit: http://codeforces.net/contest/818/submission/28143128

Joxa_P

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 $\text{[math]}$ ,so baisicly I did nothing smart for this accepted,unlike some other E's where there is some beautiful observation.My 28153516

GODOF_Shinobi

Can D be done by 2 pointer? I couldn't implement 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.

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.

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

Vicennial

+10

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

prat33k

+30

Here is the Problem E on Hackerearth created by MazzForces .

MazzForces

-10

fofao_funk

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

awoo

+22

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.

ShowStopper728

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 ?

shubhiks1032

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

kr_abhinav

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.

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

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).

TooNewbie

+12

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

daihan

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.net/contest/818/submission/28144078